视频网站架构,网站建设企业实践总结,做网站从何开始,新版wordpress如何添加标签面试题23#xff1a;从上往下打印二叉树 题目#xff1a;从上往下打印出二叉树的每个结点#xff0c;同一层的结点按照从左到右的顺序打印。例如输入图4.5中的二叉树#xff0c;则依次打印出8、6、10、5、7、9、11。
二叉树结点的定义如下#xff1a;
struct BinaryTree…面试题23从上往下打印二叉树 题目从上往下打印出二叉树的每个结点同一层的结点按照从左到右的顺序打印。例如输入图4.5中的二叉树则依次打印出8、6、10、5、7、9、11。
二叉树结点的定义如下
struct BinaryTreeNode
{int value;BinaryTreeNode *lchild;BinaryTreeNode *rchild;
};思路: 每一次打印一个结点的时候如果该结点有子结点则把该结点的子结点放到一个队列的末尾。接下来到队列的头部取出最早进入队列的结点重复前面的打印操作直至队列中所有的结点都被打印出来为止。
代码如下:
void PrintFromTopToBottom(BinaryTreeNode *pTreeRoot)
{if (!pTreeRoot) return;dequeBinaryTreeNode * dequeTreeNode;dequeTreeNode.push_back(pTreeRoot);while (dequeTreeNode.size()){BinaryTreeNode *pNode dequeTreeNode.front();dequeTreeNode.pop_front();cout pNode-value ;if (pNode-lchild) dequeTreeNode.push_back(pNode-lchild);if (pNode-rchild) dequeTreeNode.push_back(pNode-rchild);}
}本题考点 ● 考查思维能力。按层从上到下遍历二叉树这对很多应聘者是个新概念要在短时间内想明白遍历的过程不是一件容易的事情。应聘者通过具体的例子找出其中的规律并想到基于队列的算法是解决这个问题的关键所在。 ● 考查应聘者对二叉树及队列的理解。
