剑指offer之按层打印树节点

简介: 剑指offer之按层打印树节点

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

 

相关文章
|
8月前
|
算法
【递归搜索回溯专栏】专题二:二叉树中的深搜----求根节点到叶节点数字之和
【递归搜索回溯专栏】专题二:二叉树中的深搜----求根节点到叶节点数字之和
52 0
|
8月前
leetcode代码记录(完全二叉树的节点个数
leetcode代码记录(完全二叉树的节点个数
39 1
|
8月前
|
存储
【剑指offer】- 按之字形顺序打印二叉树-45/67
【剑指offer】- 按之字形顺序打印二叉树-45/67
|
8月前
|
存储
【剑指offer】-把二叉树打印成多行-43/67
【剑指offer】-把二叉树打印成多行-43/67
【剑指offer】-从上往下打印二叉树-22/67
【剑指offer】-从上往下打印二叉树-22/67
剑指offer(C++)-JZ77:按之字形顺序打印二叉树(数据结构-树)
剑指offer(C++)-JZ77:按之字形顺序打印二叉树(数据结构-树)
|
算法 C++
剑指offer(C++)-JZ86:在二叉树中找到两个节点的最近公共祖先(数据结构-树)
剑指offer(C++)-JZ86:在二叉树中找到两个节点的最近公共祖先(数据结构-树)
代码随想录刷题|LeetCode 24. 两两交换链表中的节点 19.删除链表的倒数第N个节点 160. 链表相交 142.环形链表II
代码随想录刷题|LeetCode 24. 两两交换链表中的节点 19.删除链表的倒数第N个节点 160. 链表相交 142.环形链表II
代码随想录刷题|LeetCode 24. 两两交换链表中的节点 19.删除链表的倒数第N个节点 160. 链表相交 142.环形链表II
|
Java C++
删除链表的节点(剑指offer 18)
给定单向链表的头指针和一个要删除的节点的值,定义一个函数删除该节点。 返回删除后的链表的头节点。