二叉树的分层遍历

给定一棵二叉树,要求从上到下从左到右分层输出该二叉树的节点值。

bitree.png

一、递归法

二叉树本身就带有递归属性,通常我们可以用递归方法解决。假设要访问第k层节点,那么其实可以转换成分别访问“以该二叉树根节点的左右子节点为根节点的两棵子树”中层次为k-1的节点(root所在的层看作是第0层)。 此方法理论上需要求出二叉树的深度,实际上访问到二叉树某一层次失败的时候返回就可以了。具体见代码:

#include <iostream>
#include <malloc.h>
using namespace std;
struct Node
{
    struct Node *lchild;//左孩子指针
    struct Node *rchild;//右孩子指针
    int data;           //节点数值
};
//创建结点
Node* createTreeNode(int data)
{
    Node *n=(Node *)malloc(sizeof(Node));
    n->data = data;
    n->lchild = NULL;
    n->rchild = NULL;
    return n;
}
//遍历第level层的所有结点
int printNodeAtLevel(Node *root, int level)
{
    if(root == NULL || level < 0)
    {
        return 0;
    }
    if(level == 0)
    {
        cout << root -> data << " ";
        return 1;
    }
    return printNodeAtLevel(root -> lchild, level - 1) + printNodeAtLevel(root -> rchild, level - 1);
}
//遍历所有层
void levelTraverse(Node *root)
{
    for(int level = 0; ; level++)
    {
        if(!printNodeAtLevel(root, level))
        {
            break;
        }
    }
}
int main()
{
    Node* n1 = createTreeNode(1);
    Node* n2 = createTreeNode(2);
    Node* n3 = createTreeNode(3);
    Node* n4 = createTreeNode(4);
    Node* n5 = createTreeNode(5);
    Node* n6 = createTreeNode(6);
    Node* n7 = createTreeNode(7);
    Node* n8 = createTreeNode(8);
    n1->lchild = n2;
    n1->rchild = n3;
    n2->lchild = n4;
    n2->rchild = n5;
    n3->rchild = n6;
    n6->lchild = n7;
    n6->rchild = n8;
    levelTraverse(n1);
    return 0;
}

运行结果:

1 2 3 4 5 6 7 8 

缺点:递归法往往需要重复计算,效率不高。 上面的递归遍历,对每一层的访问都需要从根节点开始,直到访问完所有的层次,造成效率极低。

二、使用数组和两个游标的非递归方法

在访问k层的时候,我们只需要知道k-1层的信息就足够了,所以在访问第k层的时候,要是能够知道k-1层的节点信息,就不再需要从根节点开始遍历了。

根据上述分析,可以从根节点出发,依次将每一层的根节点从左往右压入一个数组,并并用一个游标cur记录当前访问的节点,另一个游标last指示当前层次的最后一个节点的下一个位置,以cur===last作为当前层次访问结束的条件,在访问某一层的同时将该层的所有节点的子节点压入数组,在访问完某一层之后,检查是否还有新的层次可以访问,直到检查完所有的层次(不再有新的节点可以访问)

#include <iostream>
#include <malloc.h>
#include <vector>
using namespace std;
struct Node
{
    struct Node *lchild;//左孩子指针
    struct Node *rchild;//右孩子指针
    int data;           //节点数值
};
//创建结点
Node* createTreeNode(int data)
{
    Node *n=(Node *)malloc(sizeof(Node));
    n->data = data;
    n->lchild = NULL;
    n->rchild = NULL;
    return n;
}
//分层遍历
void levelTraverse(Node *root)
{
    if(root == NULL)
    {
        return;
    }
    vector<Node *> vec;
    vec.push_back(root);
    int cur = 0;
    int last = vec.size();
    while(cur < (int)vec.size())
    {
        //定位last为当前行最后一个节点的下一个位置,即下行的首位置
        last = vec.size();
        while(cur < last)   //cur位于当前行时
        {
            cout << vec[cur] -> data << " ";
            if(vec[cur] -> lchild)
            {
                vec.push_back(vec[cur] -> lchild);
            }
            if(vec[cur] -> rchild)
            {
                vec.push_back(vec[cur] -> rchild);
            }
            cur++;//cur后移
        }
        cout << endl;//当cur与last相等时,说明该层访问结束,换行
    }
}
int main()
{
    Node* n1 = createTreeNode(1);
    Node* n2 = createTreeNode(2);
    Node* n3 = createTreeNode(3);
    Node* n4 = createTreeNode(4);
    Node* n5 = createTreeNode(5);
    Node* n6 = createTreeNode(6);
    Node* n7 = createTreeNode(7);
    Node* n8 = createTreeNode(8);
    n1->lchild = n2;
    n1->rchild = n3;
    n2->lchild = n4;
    n2->rchild = n5;
    n3->rchild = n6;
    n6->lchild = n7;
    n6->rchild = n8;
    levelTraverse(n1);
    return 0;
}

运行结果:

1
2 3 
4 5 6
7 8

缺点: 这种方法需要一个vector一直存储所有节点,空间效率较差。

原文发布于微信公众号 - 海天一树(gh_de7b45c40e8b)

原文发表时间:2018-03-11

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Java学习123

【数据结构】ArrayList原理及实现学习总结

8805
来自专栏用户画像

7.7.5 最佳归并树

文件经过置换-选择排序之后,得到的是长度不等的初始归并段。下面讨论如何组织初始归并段的归并顺序,使I/O访问次数最少。

791
来自专栏用户3030674的专栏

Java 工具类—日期获得,随机数,系统命令,数据类型转换

1461
来自专栏大闲人柴毛毛

贪心算法(五)——迪杰斯特拉算法

问题描述 给一个有向无环带权图,并给一个起点,求出该原点到所有顶点的最短路径。 ? 数据结构 dis: Map<String,Integer> dis; ...

4069
来自专栏云霄雨霁

数据结构----二叉堆和优先权队列

1630
来自专栏用户画像

6.2.2 折半查找

折半查找,又称二分查找,它适用于有序的顺序表。基本思路是:首先将给定值key与表中中间位置元素的关键字比较,若相等,则查找成功,返回该元素的存储位置;若不等,则...

671
来自专栏TechBox

数据结构与算法之线性表前言线性表

1925
来自专栏Android机动车

数据结构学习笔记——线性表(中)

线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素,这组存储单元可以是连续的,也可以是不连续的。这就意味着,这些数据元素可以存在内存未被占用的...

913
来自专栏电光石火

HashSet/HashMap详解

HashMap和HashSet是Java Collection接口两个重要的成员,其中HashMap是Map接口常用的实现类,HashSet是Set接口常用...

23410
来自专栏Java帮帮-微信公众号-技术文章全总结

HashSet 源码分析【面试+工作】

在工作中,经常有这样的需求,需要判断某个ID是否在某个组的管理之下等,就需要查询该组下的ID放到一个集合中,且集合中元素不能有重复,之后判断该集合是否包含我们的...

1233

扫码关注云+社区

领取腾讯云代金券