二叉树的层序遍历

时间:2021-09-23 11:23:11

  输出不太对,只考虑了完全二叉树的情况。。。

  代码:

#include <iostream>
#include <queue>
#include <vector>
#include <math.h>
 
typedef struct BaseNode* tree;
 
struct BaseNode {
	int val;
	BaseNode* left;
	BaseNode* right;

	BaseNode() {};
	BaseNode(int v) : val(v), left(nullptr), right(nullptr)
	{
	}
};
 
void insert(tree & root, int & v)
{
	std::cin >> v;
	if (v == 0)
		root = nullptr;
	else
	{
		root = new BaseNode(v);
		insert(root->left, v);
		insert(root->right, v);
	}
}
 
void sequence(tree root)
{
	std::queue<tree> nodes;
	std::vector<int> nums;
	tree rptr = root;

	nodes.push(rptr);
	while (!nodes.empty())
	{
		rptr = nodes.front();
		nodes.pop();
 
		if (rptr)
		{
			nums.push_back(rptr->val);
			nodes.push(rptr->left);
			nodes.push(rptr->right);
		}
	}

	for (int i = 0; i < int(log(nums.size() + 1)); i++)
	{
		for (int j = 0; j < nums.size() - i; j++)
			std::cout << " ";
		for (int j = (i < 2 ? i : i + 1); j <= 2 * i; j++)
			std::cout << nums[j] << " ";
		std::cout << std::endl;
	}

}
 
 
int main()
{
	tree root;
	int v;

	insert(root, v);
	sequence(root);

	return 0;
}