例题-从上往下打印二叉树

题目描述

从上往下打印出二叉树的每个节点，同层节点从左至右打印。

原理

从题面可得题意为层次遍历，层次遍历的核心思想为：每次出队一个元素，就将该元素的孩子节点加入队列中，直至队列中元素个数为0时，出队的顺序就是该二叉树的层次遍历结果

给出一个二叉树

1. 初始状态下，队列中只保留根节点的元素
   
2. 当A出队时，将A的孩子节点加入队列中
   
3. 重复2的动作，直至所有遍历完

代码实现

class TreeNode {
public:
	int data;
	TreeNode* lchild = nullptr;
	TreeNode* rchild = nullptr;
	TreeNode(int data) :data(data) {};
	~TreeNode() {};
};

class Tree 
{
public:
    void Tree::Level(TreeNode* node) 
    {          //层次遍历
    	if (node == nullptr)
    		return;
    	queue<TreeNode*> q;
    	q.push(node);
    	while (!q.empty()) 
    	{
    		TreeNode* node = q.front();
    		q.pop();
    		cout << node->data << " ";
    		if (node->lchild) q.push(node->lchild);
    		if (node->rchild) q.push(node->rchild);
	    }
    }
};

例子1

输入为

[5,4,#,3,#,2,#,1]

输出为

[5,4,3,2,1]

例子2

输入为

[1,#,3,#,#,4]

输出为

[1,3,4]