本文主要是介绍剑指offer之按层打印树节点,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
1 问题
按层打印树节点,比如我们有树如下
23 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
这篇关于剑指offer之按层打印树节点的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!