《数据结构基本知识二叉树遍历》由会员分享，可在线阅读，更多相关《数据结构基本知识二叉树遍历（44页珍藏版）》请在金锄头文库上搜索。
1、第5章第2节计算机科学系张红军河南省政法管理干部学院河南省政法管理干部学院1.树的定义及性质v树(tree)是n(n0)个结点的有限集T，其中：l有且仅有一个一个特定的结点，称为树的根根(root)l当n1时，其余结点其余结点可分为m(m0)个互不相互不相交交的有限集T1,T2,Tm，其中每一个集合本身又是一棵树，称为根的子树子树(subtree)。回顾上节课主要内容回顾上节课主要内容2.二叉树的定义及性质v二叉树是n(n0)个结点的有限集，它或为空树或为空树(n =0)，或由一个根结点或由一个根结点和两棵分别称为左子树左子树和右子树右子树的互不相交的二叉树构成。河南省政法管理干部学院河南省政
2、法管理干部学院3.二叉树的存储结构顺序存储结构v按满二叉树的结点层次编号，依次存放二叉树中的数据元素链式存储结构v使用二叉链表存储，通过指针指向左右子树。typedef char ElemType;typedef struct BiTNode ElemType data; struct BiTNode *lchild, *rchildBiTNode, *BiTree;BiTree bt;lchild data rchild 河南省政法管理干部学院河南省政法管理干部学院4.树与二叉树转换ACBED树ABCDE二叉树 A B C D E A B C D E A B C D E 对应存储存储解释解释
3、河南省政法管理干部学院河南省政法管理干部学院遍历按一定规律走遍树的各个结点，且使每一结点仅被访问一次，即找一个完整而有规律的走法，以得到树中所有结点的一个线性排列。常用方法v先序遍历：先访问根结点,然后分别先序遍历左子树、先序遍历右子树。v中序遍历：先中序遍历左子树，然后访问根结点，最后中序遍历右子树。v后序遍历：先后序遍历左、后序遍历右子树，然后访问根结点5.2 二叉树的遍历 二叉树是n(n0)个结点的有限集，它或为空树或为空树(n=0)，或由一个根结点或由一个根结点和两棵分别称为左左子树子树和右子树右子树的互不相交的二叉树构成。河南省政法管理干部学院河南省政法管理干部学院ADBC根根 左左
4、 右右A根根 左左 右右根根 左左 右右BDC根根 左左 右右先序遍历序列：先序遍历序列：A B D C先序遍历:ABDC河南省政法管理干部学院河南省政法管理干部学院河南省政法管理干部学院河南省政法管理干部学院先序遍历:算法过程描述如下：1.若二叉树为空，则返回2.否则依次执行 访问根结点 先序遍历左子树 先序遍历右子树void PreOrder(BiTree T) if(T!=NULL) printf(%3c,T-data); PreOrder(T-lchild); PreOrder(T-rchild); typedef struct BiTNode ElemType data; struc
5、t BiTNode *lchild, *rchildBiTNode, *BiTree;河南省政法管理干部学院河南省政法管理干部学院1. void pre(BiTree T)2. if(T!=NULL)3. printf(%3c,T-data);4. pre(T-L);5. pre(T-R);6. 7. 主程序主程序Pre( T )返回返回pre(T R);返回返回pre(T R);ACBDTBprintf(B);pre(T L);BTAprintf(A);pre(T L);ATDprintf(D);pre(T L);DTCprintf(C);pre(T L);C返回T左是空返回pre(T R)
6、;T左是空返回T右是空返回T左是空返回T右是空返回pre(T R);先序序列：A B D C河南省政法管理干部学院河南省政法管理干部学院例：对如下二叉树进行前序遍历的结果为例：对如下二叉树进行前序遍历的结果为ABDCEFFCADEGBA B D E C FF C A D B E G河南省政法管理干部学院河南省政法管理干部学院左左 根根 右右B左左 根根 右右左左 根根 右右ADC左左 根根 右右中序遍历序列：中序遍历序列：B D A C中序遍历:ADBCBDAC河南省政法管理干部学院河南省政法管理干部学院河南省政法管理干部学院河南省政法管理干部学院中序遍历:算法过程描述如下：1.若二叉树为空，
7、则返回2.否则依次执行中序遍历左子树访问根结点中序遍历右子树void InOrder(BiTree T) if(T!=NULL) InOrder(T-lchild);printf(%3c,T-data);InOrder(T-rchild);typedef struct BiTNode ElemType data; struct BiTNode *lchild, *rchildBiTNode, *BiTree;河南省政法管理干部学院河南省政法管理干部学院例：对如下二叉树进行中序遍历的结果为例：对如下二叉树进行中序遍历的结果为ABDCEFFCADEGBD B E A F CA C B D F E
8、G河南省政法管理干部学院河南省政法管理干部学院ADBC左左 右右 根根左左 右右 根根左左 右右 根根ADC左左 右右 根根后序遍历序列：后序遍历序列： D B C A后序遍历:BDBCA河南省政法管理干部学院河南省政法管理干部学院河南省政法管理干部学院河南省政法管理干部学院后序遍历:算法过程描述如下：1.若二叉树为空，则返回2.否则依次执行后序遍历左子树后序遍历右子树访问根结点void PostOrder(BiTree T)if(T!=NULL) PostOrder(T-lchild);PostOrder(T-rchild);printf(%2c,T-data);河南省政法管理干部学院河南省
9、政法管理干部学院例：对如下二叉树进行后序遍历的结果为例：对如下二叉树进行后序遍历的结果为ABDCEFFCADEGBD E B F C AA B D C G E F河南省政法管理干部学院河南省政法管理干部学院-+/a*b-efcd先序遍历：中序遍历：后序遍历：- + a * b - c d/ e f-+a*b-cd/ef-+a*b-c d/e f河南省政法管理干部学院河南省政法管理干部学院例例1：已知一棵二叉树的先序序列为：已知一棵二叉树的先序序列为CEDBA，中序序列为中序序列为DEBAC，试构造该二叉树。，试构造该二叉树。 基本思想：基本思想： 在先序序列中找根，在中序序列中分左右。在先序序
10、列中找根，在中序序列中分左右。DEBA先序序列为：先序序列为：中序序列为：中序序列为：CEDABDEBCAECBABDA河南省政法管理干部学院河南省政法管理干部学院练习练习先序序列为：先序序列为：A B D E C F H G中序序列为：中序序列为：D B E A H F C G构造一棵二叉树。构造一棵二叉树。答案答案河南省政法管理干部学院河南省政法管理干部学院DEGFBCAH河南省政法管理干部学院河南省政法管理干部学院例例2：已知一棵二叉树的后序序列为：已知一棵二叉树的后序序列为DABEC，中序序列为中序序列为DEBAC，试构造该二叉树。，试构造该二叉树。 基本思想：基本思想： 在后序序列中
11、找根，在中序序列中分左右。在后序序列中找根，在中序序列中分左右。DEBA后序序列为：后序序列为：中序序列为：中序序列为：DABCEDEBCAECBABDA河南省政法管理干部学院河南省政法管理干部学院练习练习后序序列为：后序序列为：D E B H F G C A中序序列为：中序序列为：D B E A H F C G构造一棵二叉树。构造一棵二叉树。答案答案河南省政法管理干部学院河南省政法管理干部学院DEGFBCAH河南省政法管理干部学院河南省政法管理干部学院2.二叉树遍历的非递归算法河南省政法管理干部学院河南省政法管理干部学院2.二叉树遍历的非递归算法河南省政法管理干部学院河南省政法管理干部学院2
12、.二叉树遍历的非递归算法河南省政法管理干部学院河南省政法管理干部学院2.二叉树遍历的非递归算法河南省政法管理干部学院河南省政法管理干部学院2.二叉树先序遍历的非递归算法(1)先序遍历的非递归算法先序遍历的非递归算法1.令p指向根结点。2.若p不为空，访问访问p所指结点所指结点，并将p压入栈中。3. 若p为空，转4。3.将p所指结点的左孩子压入栈，转2。4.从栈中弹出栈顶结点，令p指向所弹出结点的右孩子；转2。河南省政法管理干部学院河南省政法管理干部学院2.二叉树先序遍历的非递归算法ABCDEFGpiP-A(1)访问：AABCDEFGpiP-AP-B(2)访问：ABABCDEFGpiP-AP-B
13、P-C(3)访问：ABCABCDEFGpiP-AP-B(4)访问：ABC河南省政法管理干部学院河南省政法管理干部学院ABCDEFGiP-AP-DP-E访问：ABCDEp(7)p=NULLABCDEFGiP-A(5)访问：ABCp=NULLABCDEFGiP-AP-D(6)访问：ABCDABCDEFGiP-AP-D访问：ABCDEp(8)河南省政法管理干部学院河南省政法管理干部学院ABCDEFGiP-AP-F访问：ABCDEGFp(12)ABCDEFGiP-AP-DP-G访问：ABCDEGp(9)ABCDEFGiP-A访问：ABCDEGp(11)ABCDEFGiP-AP-D访问：ABCDEGp(
14、10)河南省政法管理干部学院河南省政法管理干部学院ABCDEFGiP-A访问：ABCDEGFp(13)ABCDEFGi访问： ABCDEGFp=NULL(14)河南省政法管理干部学院河南省政法管理干部学院2.二叉树先序遍历的非递归算法(2)中序遍历的非递归算法中序遍历的非递归算法1.令p指向根结点。2.若p不为空，将p压入栈中。3. 若p为空，转4。3.将p所指结点的左孩子压入栈，转2。4.从栈中弹出栈顶结点，访问所弹出结点访问所弹出结点，令p指向所弹出结点的右孩子；转2。河南省政法管理干部学院河南省政法管理干部学院2.二叉树中序遍历的非递归算法ABCDEFGpiP-A(1)ABCDEFGpi
15、P-AP-B(2)ABCDEFGpiP-AP-BP-C(3)p=NULLABCDEFGiP-AP-B访问：C(4)河南省政法管理干部学院河南省政法管理干部学院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)河南省政法管理干部学院河南省政法管理干部学院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)ABCDEFGi
16、P-AP-D访问：C B E Gp(10)河南省政法管理干部学院河南省政法管理干部学院ABCDEFGiP-A访问：C B E G D Fp=NULL(13)ABCDEFGi访问：C B E G D F Ap(14)河南省政法管理干部学院河南省政法管理干部学院v遍历算法应用l按先序遍历序列建立二叉树的二叉链表，已知先序序列为： A B C D E G F l求二叉树深度算法ABCDEFGl统计二叉树中叶子结点个数算法河南省政法管理干部学院河南省政法管理干部学院3.二叉树的层次遍历河南省政法管理干部学院河南省政法管理干部学院4. 树和森林的遍历树的遍历v先根（序）遍历：先访问树的根结点，然后依次先
17、根遍历根的每棵子树v后根（序）遍历：先依次后根遍历每棵子树，然后访问根结点v按层次遍历：先访问第一层上的结点，然后依次遍历第二层，第n层的结点河南省政法管理干部学院河南省政法管理干部学院ABCDEFGHIJKLMNO先序遍历：后序遍历：层次遍历：ABE F I GCDHJ KL NOME I F G B C J K N O L M H D AAB C DE F GH I J KL MNO河南省政法管理干部学院河南省政法管理干部学院4. 树和森林的遍历 森林的遍历先根（序）遍历：1.先访问第一颗树的根结点2.先根遍历第一颗树中根结点的子树森林3.先根遍历除去第一颗树之后剩余树构成的森林后根（序）遍历1.后跟遍历第一颗树的根结点的子树森林2.访问第一颗树的根结点3.后跟遍历除去第一颗树之后剩余树构成的森林
