武汉理工大学 信息工程学院 数据结构ch 树和二叉树遍历二叉树.pptx

《武汉理工大学 信息工程学院 数据结构ch 树和二叉树遍历二叉树.pptx》由会员分享，可在线阅读，更多相关《武汉理工大学 信息工程学院 数据结构ch 树和二叉树遍历二叉树.pptx（16页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、6.3 遍历二叉树二叉树的遍历方法先序遍历：先访问根结点,然后分别先序遍历左子树、右子树。中序遍历：先中序遍历左子树，然后访问根结点，最后中序遍历右子树。后序遍历：先后序遍历左、右子树，然后访问根结点。按层次遍历：从上到下、从左到右访问各结点。DLRLDR、LRD、DLRRDL、RLD、DRL第1页/共16页ADBCD L RAD L RD L RBDCD L R先序遍历序列：A B D C先序遍历:第2页/共16页ADBCL D RBL D RL D RADCL D R中序遍历序列：B D A C中序遍历:第3页/共16页ADBC L R DL R DL R DADCL R D后序遍历序列：

2、D B C A后序遍历:B第4页/共16页-+/a*b-efcd先序遍历：中序遍历：后序遍历：层次遍历：-+a*b-c d/e f-+a*b-cd/ef-+a*b-c d/e f-+a*b-c d/e f第5页/共16页void preorder(JD*bt)if(bt!=NULL)printf(%dt,bt-data);preorder(bt-lchild);preorder(bt-rchild);主程序Pre(T)返回返回pre(T R);返回返回pre(T R);ACBDTBprintf(B);pre(T L);BTAprintf(A);pre(T L);ATDprintf(D);pre

3、(T L);DTCprintf(C);pre(T L);C返回T左是空返回pre(T R);T左是空返回T右是空返回T左是空返回T右是空返回pre(T R);先序序列：A B D C第6页/共16页非递归算法实现中序遍历ABCDEFGpiP-A(1)ABCDEFGpiP-AP-B(2)ABCDEFGpiP-AP-BP-C(3)p=NULLABCDEFGiP-AP-B访问：C(4)第7页/共16页pABCDEFGiP-A访问：C B(5)ABCDEFGiP-AP-D访问：C Bp(6)ABCDEFGiP-AP-DP-E访问：C Bp(7)ABCDEFGiP-AP-D访问：C B Ep(8)第8页

4、/共16页ABCDEFGiP-AP-DP-G访问：C B EP=NULL(9)ABCDEFGiP-A访问：C B E G Dp(11)ABCDEFGiP-AP-F访问：C B E G Dp(12)ABCDEFGiP-AP-D访问：C B E Gp(10)第9页/共16页ABCDEFGiP-A访问：C B E G D Fp=NULL(13)ABCDEFGi访问：C B E G D F Ap(14)ABCDEFGi访问：C B E G D F Ap=NULL(15)后序遍历非递归算法第10页/共16页l遍历算法应用按先序遍历序列建立二叉树的二叉链表，已知先序序列为：A B C D E G F AB

5、CDEFG A B C D E F G 二叉树的建立演示第11页/共16页用队列实现层次遍历可使用一个顺序存储的队列q100,存放还没有处理的子树的根结点的地址。注意,队首和队尾指针分别指向队首结点和下次进队结点的存放位置。1)首先把根节点入队。2)然后访问队头的一个结点，再把该结点非空的左右子树入队。3)如果队列不空，重复2)。第12页/共16页示例代码第13页/共16页作业当用栈非递归实现树的先序遍历时，写出遍历右边所表示的树的全过程。像讲义中那样，写出遍历每一步栈中的数据。不是写具体的实现代码。ABCDEFG第14页/共16页实验报告按先序遍历序列建立二叉树的二叉链表，已知先序序列为(表示空格)：ABCDEGF。并写一个函数treenodes()统计该二叉树的节点个数。如果有可能，写一个输出函数treeprint()用树形结构打印出该二叉树。注意实验报告中不必写完整代码。写树结构定义，已有函数声明，treenodes()和treeprint()的代码，实现过程，心得体会。第15页/共16页感谢您的观看！第16页/共16页