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

-----二叉树的遍历-------

------------------先序遍历-----------------------

遍历过程

①访问根节点。

②线序遍历其左子树。

③线序遍历其右子树。

/*这里的遍历顺序是 A B D F E C G H I*/
void
PreOrderTraversal(BinTree BT) // { if(BT) //判断二叉树是否为空 { printf("%d",BT->Date); // 过了一个了 PreOderTraversal(BT->left); //递归调用了该函数。 检查左边。 PreOderTraversal(BT->right); } } //递归其实也像是一棵树,向下走当向下走不成的时候向上走一步,走另一个分支。

 中序遍历,和后序遍历都是只是对。  那里的执行程序printf(“%d”,BT->Date);分别换到中间和   换到后面而已。

中序遍历可以用这个锻炼递归的思路形成,D B E F E A C G  H C I 

后序遍历一个比一个难度高。。。。。。。

这三种便利方法不是太相同但是大部分是相同的。

------------在这三种遍历的不同之中最能体会到   递归调用的实质-----

 

 

上面说了,树的三种遍历。但是都是递归的,在咱们刚刚开始的时候都说过了如果用递归的话,占用的内存太大。导致程序容易崩溃。刚好咱们前面学了   栈   所以应该就能想到 我们利用栈 将递归函数变成非递归函数。   Are you ready?

 中序遍历。。。。。。。

void InOrderTraversal(BinTree BT)  
{
    BinTree T=BT;                 //创建一个临时变量
    stack s=creatstack(MaxSize);   //调用创建 堆栈的 函数
    while(T||!IsEmpty)        
    {
        while(T)       //一直向左并且将沿途的 节点压入堆栈.
        {
            Push(S,T);     
            T=T->Right;
        }
        if(!IsEmpty(s))
        {
            T=Pop(s);     //节点弹出堆栈
            printf("%d",T->Date);    //(访问)打印节点
            T=T->Right;  //转向右子树
        }
    }
}

下面附上先序。

/*只是将 标记的地方互换之后  就可以了。*/
void InOrderTraversal(BinTree BT)  
{
    BinTree T=BT;                 //创建一个临时变量
    stack s=creatstack(MaxSize);   //调用创建 堆栈的 函数
    while(T||!IsEmpty)        
    {
        while(T)       //一直向左并且将沿途的 节点压入堆栈.
        {
            printf("%d",T->Date);    //(访问)打印节点      ///*******
            T=T->Right;
        }
        if(!IsEmpty(s))
        {
            T=Pop(s);     //节点弹出堆栈
            Push(S,T);                            //**************
            T=T->Right;  //转向右子树
        }
    }
}

下面开始   二叉树的    层次遍历。

二叉树是一种二维结构,然而我们在遍历的时候就必须一个一个的去遍历,这样的话就需要每一个元素都有顺序,就需要把二位的结构变成一维的结构。这就是二叉树甚至多叉树进行遍历时需要处理的关键。

一层一层   一个一个  从上到下   从左到右,进行遍历。  首先从根节点开始将A放进去,然后抛出去A,然他的两个儿子进去,然后抛出B让她的两个儿子进去(first In first out)  然后 抛出去C然后让她的两个儿子进来。然后抛出去D,让他的两个儿子进来(发现没儿子,那就不用进来了。。。。。)就这样下去就遍历完了。

    --颤抖吧---感受一下代码---哈哈----

/*层序基本过程:先从节点入队,然后:

 

① 从队列中取出一个元素;
  ②访问该元素所指的节点;
  ③若该元素所指的节点非空则按照从左到右的顺序放到队列中(FIFO)。

//层序遍历简单易懂(如果队列函数好些的话,以后就可以用测序遍历了。)
void LevelOrderTraversal(BinTree BT)
{
    Queue Q;
    BinTree T;
    if(!BT)      //如果是空树的话直接返回
        return ;
    AddQ(Q,BT);  //将  根节点放到队列里面去。
    while(!IsEmptyQ(Q))    //判断队列是否为空
    {
        T=DeleteQ(Q);    //从队列里面抛出去一个元素
        printf("%d\n",T->Date);  //  打印 所抛出去的元素。
        if(T->Left)               //如果有左儿子
            AddQ(Q,T->Left);     //左儿子进去
        if(T->right)            //如果有右儿子的话右儿子进去。
            AddQ(Q,T->Right);
    }
}

 

 

 

 

 

转载于:https://www.cnblogs.com/A-FM/p/5142221.html

相关文章:

  • Highcharts tooltip显示数量和百分比
  • Listen第二个参数的意义
  • 发布mvc报错:403.14-Forbidden Web 服务器被配置为不列出此目录的内容
  • 在Unity中实现一个简单的消息管理器
  • 重要的方法
  • Docker入门最佳实践
  • webpack 4.x 搭建项目脚手架
  • python学习第十二课
  • 用事件修饰符来修改事件
  • PHP慢慢长路之问题与解决方法(2)——用navicat导出数据库出错问题解决
  • DevOps/TestOps概念
  • 高级特性(8)- JavaBean构件
  • openpyxl read excel
  • Android通讯录管理(获取联系人、通话记录、短信消息)(二)
  • h5开发坑点小总结
  • 【Leetcode】101. 对称二叉树
  • 9月CHINA-PUB-OPENDAY技术沙龙——IPHONE
  • 77. Combinations
  • Fundebug计费标准解释:事件数是如何定义的?
  • Golang-长连接-状态推送
  • idea + plantuml 画流程图
  • If…else
  • JAVA并发编程--1.基础概念
  • mysql 5.6 原生Online DDL解析
  • Promise面试题2实现异步串行执行
  • PyCharm搭建GO开发环境(GO语言学习第1课)
  • 仿天猫超市收藏抛物线动画工具库
  • 问:在指定的JSON数据中(最外层是数组)根据指定条件拿到匹配到的结果
  • 小试R空间处理新库sf
  • 移动端解决方案学习记录
  • RDS-Mysql 物理备份恢复到本地数据库上
  • 树莓派用上kodexplorer也能玩成私有网盘
  • #!/usr/bin/python与#!/usr/bin/env python的区别
  • #Linux(帮助手册)
  • (附源码)springboot宠物医疗服务网站 毕业设计688413
  • (规划)24届春招和25届暑假实习路线准备规划
  • (七)Knockout 创建自定义绑定
  • (转)h264中avc和flv数据的解析
  • (转)详解PHP处理密码的几种方式
  • ***php进行支付宝开发中return_url和notify_url的区别分析
  • .NET 4 并行(多核)“.NET研究”编程系列之二 从Task开始
  • .net MySql
  • .Net 中Partitioner static与dynamic的性能对比
  • @ConfigurationProperties注解对数据的自动封装
  • @Transient注解
  • @vue/cli脚手架
  • [ 2222 ]http://e.eqxiu.com/s/wJMf15Ku
  • [ CTF ]【天格】战队WriteUp- 2022年第三届“网鼎杯”网络安全大赛(青龙组)
  • [ 英语 ] 马斯克抱水槽“入主”推特总部中那句 Let that sink in 到底是什么梗?
  • [ 云计算 | AWS 实践 ] Java 如何重命名 Amazon S3 中的文件和文件夹
  • [28期] lamp兄弟连28期学员手册,请大家务必看一下
  • [AIGC] Java 和 Kotlin 的区别
  • [BIZ] - 1.金融交易系统特点
  • [BZOJ5250][九省联考2018]秘密袭击(DP)
  • [C/C++]数据结构 深入挖掘环形链表问题