当前位置： 首页 > news >正文

层次遍历二叉树（编程之美3.10）

news 来源：原创 2024/5/4 10:01:54

问题（假定根节点位于第0层）

1. 层次遍历二叉树（每层换行分开）

2. 层次遍历二叉树指定的某层

例如

上图中

1.

1
2 3
4 5 6
7 8

2.

第三层
7 8

可以看出得出第二问的解，第一问迎刃而解了，所以从问题二下手

 

分析与解

1. 层次遍历二叉树指定的某层

可以得出这样的一个结论：遍历二叉树的第k层，相当于遍历二叉树根节点的左右子树的第k-1层。这样一直遍历下去，直到k=0时，输出节点即可。

参考代码

int PrintNodeAtLevel(BiTree root, int level)
{
    if(!root || level < 0)
        return 0;
    else if(level == 0)
    {
        cout << root->data << endl;
        return 1;
    }
    else
        return PrintNodeAtLevel(root->left, level - 1) + PrintNodeAtLevel(root->right, level - 1);
}

完整执行代码

#include<iostream>
using namespace std;
typedef struct BiTNode
{
    int data;
    BiTNode *left;
    BiTNode *right;
}BiTNode, *BiTree;

void createTree(BiTree &root)
{
    BiTree left1 = new(BiTNode);
    BiTree right1 = new(BiTNode);
    
    left1->data = 1;
    left1->left = NULL;
    left1->right = NULL;
    right1->data = 2;
    right1->left = NULL;
    right1->right = NULL;

    root->left = left1;
    root->right = right1;


    BiTree left2 = new(BiTNode);
    left2->data = 3;
    left2->left = NULL;
    left2->right = NULL;
    BiTree right2 = new(BiTNode);
    right2->data = 4;
    right2->left = NULL;
    right2->right = NULL;
    left1->left = left2;
    left1->right = right2;

    BiTree left3 = new(BiTNode);
    left3->data = 5;
    left3->left = NULL;
    left3->right = NULL;
    BiTree right3 = new(BiTNode);
    right3->data = 6;
    right3->left = NULL;
    right3->right = NULL;
    left2->left = left3;
    left2->right = right3;
}

void deleteTree(BiTree root)
{
    if(root)
    {
        deleteTree(root->left);
        deleteTree(root->right);
        delete(root);
        root = NULL;
    }
}

int PrintNodeAtLevel(BiTree root, int level)
{
    if(!root || level < 0)
        return 0;
    else if(level == 0)
    {
        cout << root->data << endl;
        return 1;
    }
    else
        return PrintNodeAtLevel(root->left, level - 1) + PrintNodeAtLevel(root->right, level - 1);
}

int main()
{
    BiTree root = new(BiTNode);
    root->data = 0;
    root->right = root->left = NULL;
    createTree(root);    
    cout << "Level 0:" << endl;
    PrintNodeAtLevel(root, 0);
    cout << "-------------------" << endl;
    cout << "Level 1:" << endl;
    PrintNodeAtLevel(root, 1);
    cout << "-------------------" << endl;
    cout << "Level 2:" << endl;
    PrintNodeAtLevel(root, 2);
    cout << "-------------------" << endl;
    cout << "Level 3:" << endl;
    PrintNodeAtLevel(root, 3);
    cout << "-------------------" << endl;
    deleteTree(root);
}
View Code

执行结果

 

2. 层次遍历二叉树

解法1——根据求得的层次，遍历每一层

参考代码

void TranverseTree(BiTree root)
{
    for(int i = 0; i < Height(root); ++i)
    {
        PrintNodeAtLevel(root, i);
        cout << "_____________________________" << endl;
    }
}

完整执行程序

#include<iostream>
using namespace std;
typedef struct BiTNode
{
    int data;
    BiTNode *left;
    BiTNode *right;
}BiTNode, *BiTree;

int maxDis = 0;

void createTree(BiTree &root)
{
    BiTree left1 = new(BiTNode);
    BiTree right1 = new(BiTNode);
    
    left1->data = 1;
    left1->left = NULL;
    left1->right = NULL;
    right1->data = 2;
    right1->left = NULL;
    right1->right = NULL;

    root->left = left1;
    root->right = right1;


    BiTree left2 = new(BiTNode);
    left2->data = 3;
    left2->left = NULL;
    left2->right = NULL;
    BiTree right2 = new(BiTNode);
    right2->data = 4;
    right2->left = NULL;
    right2->right = NULL;
    left1->left = left2;
    left1->right = right2;

    BiTree left3 = new(BiTNode);
    left3->data = 5;
    left3->left = NULL;
    left3->right = NULL;
    BiTree right3 = new(BiTNode);
    right3->data = 6;
    right3->left = NULL;
    right3->right = NULL;
    left2->left = left3;
    left2->right = right3;
}

void deleteTree(BiTree root)
{
    if(root)
    {
        deleteTree(root->left);
        deleteTree(root->right);
        delete(root);
        root = NULL;
    }
}

int PrintNodeAtLevel(BiTree root, int level)
{
    if(!root || level < 0)
        return 0;
    else if(level == 0)
    {
        cout << root->data << endl;
        return 1;
    }
    else
        return PrintNodeAtLevel(root->left, level - 1) + PrintNodeAtLevel(root->right, level - 1);
}

int Height(BiTree root)
{
    if(root == NULL)
        return 0;
    else
        return Height(root->left) > Height(root->right) ? Height(root->left)+1 : Height(root->right) + 1;
}

void TranverseTree(BiTree root)
{
    for(int i = 0; i < Height(root); ++i)
    {
        PrintNodeAtLevel(root, i);
        cout << "_____________________________" << endl;
    }
}

int main()
{
    BiTree root = new(BiTNode);
    root->data = 0;
    root->right = root->left = NULL;
    createTree(root);    
    TranverseTree(root);
    deleteTree(root);
}
View Code

执行结果

 

解法2——无需求得层次，根据遍历每层的返回信息确定遍历

参考代码

void TranverseTree(BiTree root)
{
    for(int i = 0; ; ++i)
    {
        if(!PrintNodeAtLevel(root, i))
            break;
        cout << "_____________________________" << endl;
    }
}

完整执行代码

#include<iostream>
using namespace std;
typedef struct BiTNode
{
    int data;
    BiTNode *left;
    BiTNode *right;
}BiTNode, *BiTree;

int maxDis = 0;

void createTree(BiTree &root)
{
    BiTree left1 = new(BiTNode);
    BiTree right1 = new(BiTNode);
    
    left1->data = 1;
    left1->left = NULL;
    left1->right = NULL;
    right1->data = 2;
    right1->left = NULL;
    right1->right = NULL;

    root->left = left1;
    root->right = right1;


    BiTree left2 = new(BiTNode);
    left2->data = 3;
    left2->left = NULL;
    left2->right = NULL;
    BiTree right2 = new(BiTNode);
    right2->data = 4;
    right2->left = NULL;
    right2->right = NULL;
    left1->left = left2;
    left1->right = right2;

    BiTree left3 = new(BiTNode);
    left3->data = 5;
    left3->left = NULL;
    left3->right = NULL;
    BiTree right3 = new(BiTNode);
    right3->data = 6;
    right3->left = NULL;
    right3->right = NULL;
    left2->left = left3;
    left2->right = right3;
}

void deleteTree(BiTree root)
{
    if(root)
    {
        deleteTree(root->left);
        deleteTree(root->right);
        delete(root);
        root = NULL;
    }
}

int PrintNodeAtLevel(BiTree root, int level)
{
    if(!root || level < 0)
        return 0;
    else if(level == 0)
    {
        cout << root->data << endl;
        return 1;
    }
    else
        return PrintNodeAtLevel(root->left, level - 1) + PrintNodeAtLevel(root->right, level - 1);
}

void TranverseTree(BiTree root)
{
    for(int i = 0; ; ++i)
    {
        if(!PrintNodeAtLevel(root, i))
            break;
        cout << "_____________________________" << endl;
    }
}

int main()
{
    BiTree root = new(BiTNode);
    root->data = 0;
    root->right = root->left = NULL;
    createTree(root);    
    TranverseTree(root);
    deleteTree(root);
}
View Code

执行结果

 

解法3——无需求每次都从根说起，一次遍历成功

可以看出，解法1、2每次都需要从根说起，还可以不从跟谈起，一次遍历所有的节点，不过这需要额外的存储空间

思路

定义两个指针：cur、last.cur指向目前该访问的节点位置，last指向目前队列中最后一个元素的后一个位置

遍历每一层时，遍历每一个元素是cur往后移动，同时把cur指向的左右孩子加入到队列中，当cur==last时说明该层已经遍历完事了。

参考代码

void TranverseTree(BiTree root)
{
    vector<BiTree> vec;
    vec.push_back(root);
    int cur =0, last = 1;
    while(cur < vec.size())
    {
        last = vec.size();
        while(cur < last)
        {
            cout << vec[cur]->data << " ";
            if(vec[cur]->left)
                vec.push_back(vec[cur]->left);
            if(vec[cur]->right)
                vec.push_back(vec[cur]->right);
            ++cur;
        }
        cout << endl;
    }
}

完整执行代码

#include <iostream>
#include <vector>
using namespace std;
typedef struct BiTNode
{
    int data;
    BiTNode *left;
    BiTNode *right;
}BiTNode, *BiTree;

int maxDis = 0;

void createTree(BiTree &root)
{
    BiTree left1 = new(BiTNode);
    BiTree right1 = new(BiTNode);
    
    left1->data = 1;
    left1->left = NULL;
    left1->right = NULL;
    right1->data = 2;
    right1->left = NULL;
    right1->right = NULL;

    root->left = left1;
    root->right = right1;


    BiTree left2 = new(BiTNode);
    left2->data = 3;
    left2->left = NULL;
    left2->right = NULL;
    BiTree right2 = new(BiTNode);
    right2->data = 4;
    right2->left = NULL;
    right2->right = NULL;
    left1->left = left2;
    left1->right = right2;

    BiTree left3 = new(BiTNode);
    left3->data = 5;
    left3->left = NULL;
    left3->right = NULL;
    BiTree right3 = new(BiTNode);
    right3->data = 6;
    right3->left = NULL;
    right3->right = NULL;
    left2->left = left3;
    left2->right = right3;
}

void deleteTree(BiTree root)
{
    if(root)
    {
        deleteTree(root->left);
        deleteTree(root->right);
        delete(root);
        root = NULL;
    }
}

void TranverseTree(BiTree root)
{
    vector<BiTree> vec;
    vec.push_back(root);
    int cur =0, last = 1;
    while(cur < vec.size())
    {
        last = vec.size();
        while(cur < last)
        {
            cout << vec[cur]->data << " ";
            if(vec[cur]->left)
                vec.push_back(vec[cur]->left);
            if(vec[cur]->right)
                vec.push_back(vec[cur]->right);
            ++cur;
        }
        cout << endl;
    }
}

int main()
{
    BiTree root = new(BiTNode);
    root->data = 0;
    root->right = root->left = NULL;
    createTree(root);    
    TranverseTree(root);
    deleteTree(root);
}
View Code

执行结果

C语言写的

void LevelTraverse(BinaryTreeNode *root)
{
    if(root == NULL)
        return;
    BinaryTreeNode* a[MAXSIZE];
    a[0] = root;
    int beg = 0;     //表示该层的第一个元素
    int end = 0;     //表示该层的最后一个元素
    int pos_end = 0; //表示目前访问的元素存放的位置
    while(beg <= end)
    {
        if(a[beg]->m_pLeft != NULL)
            a[++pos_end] = a[beg]->m_pLeft;
        if(a[beg]->m_pRight != NULL)
            a[++pos_end] = a[beg]->m_pRight;
        cout << a[beg]->m_nValue << " ";
        ++beg;
        if(beg > end)
        {
            end = pos_end;
            cout << endl;
        }
    }
}

之字形打印

例子：例子中打印

1
2 3
6 5 4
7

 

参考

#include <iostream>
#include <vector>
using namespace std;
struct TreeNode 
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int v) : val(v), left(NULL), right(NULL){};
};
void LevelTranverse(TreeNode *root)
{
    if (root == NULL)
        return;
    vector<TreeNode *> vec;
    vec.push_back(root);
    int beg = 0; 
    int end = vec.size();
    bool L2R = false;
    while (beg != end)
    {
        if (L2R)
        {
            for(; beg != end; ++beg)
            {
                cout << vec[beg]->val << " ";
                if (vec[beg]->left != NULL)
                    vec.push_back(vec[beg]->left);
                if (vec[beg]->right != NULL)
                    vec.push_back(vec[beg]->right);
            }
        }
        else
        {
            for(int j = beg, k = end-1; k >= beg; ++j, --k)
            {
                cout << vec[k]->val << " ";
                if (vec[j]->left != NULL)
                    vec.push_back(vec[j]->left);
                if (vec[j]->right != NULL)
                    vec.push_back(vec[j]->right);
            }
            beg = end;
        }
        end = vec.size();
        L2R ^= true;
        cout << "\n--------------" << endl;
    }
}

    
int main()
{
    TreeNode *root = new TreeNode(0);    
    TreeNode *p1 = new TreeNode(1);    
    TreeNode *p2 = new TreeNode(2);    
    root->left = p1;
    root->right = p2;
    TreeNode *p3 = new TreeNode(3);    
    TreeNode *p4 = new TreeNode(4);    
    p1->left = p3;
    p1->right = p4;
    TreeNode *p5 = new TreeNode(5);    
    TreeNode *p6 = new TreeNode(6);    
    p2->left = p5;
    p2->right = p6;
    TreeNode *p7 = new TreeNode(7);    
    TreeNode *p8 = new TreeNode(8);    
    p3->left = p7;
    p3->right = p8;
    TreeNode *p9 = new TreeNode(9);    
    p4->right = p9;
    LevelTranverse(root);
}

 

转载于:https://www.cnblogs.com/kaituorensheng/p/3558645.html

相关文章：

  • 算法起步之Prim算法
  • 我比谁都相信努力奋斗的意义
  • jsp页面中从forEach里向action里面传递其中的一个对象
  • CentOS版本选择说明
  • 读书笔记——《设计心理学2：如何管理复杂》教你应付复杂
  • 用户故事(User Story)
  • TQ2440开发板移植UBOOT-2010.06总结(3)
  • ext button 属性
  • IE，URL中文读取
  • python进阶一_简介，安装与环境部署
  • 判断投递失败原因方法
  • css入门
  • ToString()格式化输出
  • WPF中的属性触发器Trigger Property
  • PL/SQL中文乱码解决方法
  • 【Under-the-hood-ReactJS-Part0】React源码解读
  • 4月23日世界读书日 网络营销论坛推荐《正在爆发的营销革命》
  • conda常用的命令
  • Dubbo 整合 Pinpoint 做分布式服务请求跟踪
  • Facebook AccountKit 接入的坑点
  • flutter的key在widget list的作用以及必要性
  • Javascript基础之Array数组API
  • Js基础知识（一） - 变量
  • rabbitmq延迟消息示例
  • SSH 免密登录
  • 大数据与云计算学习：数据分析（二）
  • 分享一份非常强势的Android面试题
  • 技术攻略】php设计模式(一)：简介及创建型模式
  • 深入 Nginx 之配置篇
  • 使用 5W1H 写出高可读的 Git Commit Message
  • 一起来学SpringBoot | 第十篇：使用Spring Cache集成Redis
  • 由插件封装引出的一丢丢思考
  • 栈实现走出迷宫（C++）
  • #define与typedef区别
  • #NOIP 2014#Day.2 T3 解方程
  • (12)Hive调优——count distinct去重优化
  • (14)Hive调优——合并小文件
  • （6）添加vue-cookie
  • (Bean工厂的后处理器入门)学习Spring的第七天
  • （C语言）共用体union的用法举例
  • （JS基础）String 类型
  • （solr系列:一）使用tomcat部署solr服务
  • （分享）一个图片添加水印的小demo的页面，可自定义样式
  • （附源码）springboot学生选课系统 毕业设计 612555
  • (附源码)计算机毕业设计ssm-Java网名推荐系统
  • （论文阅读31/100）Stacked hourglass networks for human pose estimation
  • （十一）手动添加用户和文件的特殊权限
  • （四）【Jmeter】 JMeter的界面布局与组件概述
  • （转）大道至简，职场上做人做事做管理
  • . Flume面试题
  • .bat批处理出现中文乱码的情况
  • .equals()到底是什么意思？
  • .NET 自定义中间件 判断是否存在 AllowAnonymousAttribute 特性 来判断是否需要身份验证
  • .NET框架
  • .NET实现之(自动更新)