1 问题
按层打印树节点,比如我们有树如下
2 3 5 1 4 2 3
这样打印:2 3 5 1 4 2 3
2 分析
队列:先进后出,这里我们先打印2,然后再打印3和5,我们这里可以使用队列,我们先把2入队列,然后我们需要弹出这2节点,先打印队列最前面的节点,然后再把这个节点的的左右节点都入队列,然后再弹出最前面的节点,也就是3了,打印出来了就要弹出这个节点,我们希望下次弹出来最前面的节点才是我们需要打印的,然后再一次把这个弹出的节点左右节点分别入队列,以次类推,然后循环的条件是队列为空。
3 代码实现
#include <iostream> #include <queue> using namespace std; typedef struct Node { int value; struct Node* left; struct Node* right; } Node; void layer_print(Node *head) { if (head == NULL) { std::cout << "head is NULL" << std::endl; return; } std::queue<Node *> queue; queue.push(head); while(queue.size()) { Node *node = queue.front(); std::cout << node->value << std::endl; queue.pop(); if (node->left) queue.push(node->left); if (node->right) queue.push(node->right); } } int main() { /* 2 * 3 5 * 1 4 2 3 * */ Node head1, node1, node2, node3, node4, node5, node6; Node head2, node7, node8; head1.value = 2; node1.value = 3; node2.value = 5; node3.value = 1; node4.value = 4; node5.value = 2; node6.value = 3; head1.left = &node1; head1.right = &node2; node1.left = &node3; node1.right = &node4; node2.left = &node5; node2.right = &node6; node3.left = NULL; node3.right = NULL; node4.left = NULL; node4.right = NULL; node5.left = NULL; node5.right = NULL; node6.left = NULL; node6.right = NULL; layer_print(&head1); return 0; }
4 运行结果
2 3 5 1 4 2 3