1、河南省政法管理干部学院河南省政法管理干部学院数据结构基本知识二叉树遍历河南省政法管理干部学院河南省政法管理干部学院3.二叉树的存储结构顺序存储结构v按满二叉树的结点层次编号，依次存放二叉树中的数据元素链式存储结构v使用二叉链表存储，通过指针指向左右子树。typedef char ElemType;typedef struct BiTNode ElemType data;struct BiTNode*lchild,*rchildBiTNode,*BiTree;BiTree bt;lchild data rchild 河南省政法管理干部学院河南省政法管理干部学院 4.树与二叉树转换ACBED树AB
2、CDE二叉树 A B C D E A B C D E A B C D E 对应存储存储解释解释河南省政法管理干部学院河南省政法管理干部学院 遍历按一定规律走遍树的各个结点，且使每一结点仅被访问一次，即找一个完整而有规律的走法，以得到树中所有结点的一个线性排列。常用方法v 先序遍历：先访问根结点,然后分别先序遍历左子树、先序遍历右子树。v 中序遍历：先中序遍历左子树，然后访问根结点，最后中序遍历右子树。v 后序遍历：先后序遍历左、后序遍历右子树，然后访问根结点5.2 二叉树的遍历 二叉树是n(n0)个结点的有限集，它或为空树或为空树(n=0)，或由一个根结点或由一个根结点和两棵分别称为左子左子树
3、树和右子树右子树的互不相交的二叉树构成。河南省政法管理干部学院河南省政法管理干部学院ADBC根根 左左 右右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-rchil
4、d);typedef struct BiTNode ElemType data;struct 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);DTCpri
5、ntf(C);pre(T L);C返回T左是空返回pre(T R);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河南省政法管理干部学院河南省政法管理干部学院河南省政法管理干部学院河
6、南省政法管理干部学院中序遍历:算法过程描述如下：1.若二叉树为空，则返回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;河南省政法管理干部学院河南省政法管理干部学院例：对如下二叉树进行中序遍历的结果为例：对如下二叉树进行中序遍历的结果为ABDCEFFCA
7、DEGBD B E A F CA C B D F E G河南省政法管理干部学院河南省政法管理干部学院ADBC左左 右右 根根左左 右右 根根左左 右右 根根ADC左左 右右 根根后序遍历序列：后序遍历序列：D B C A后序遍历:BDBCA河南省政法管理干部学院河南省政法管理干部学院河南省政法管理干部学院河南省政法管理干部学院后序遍历:算法过程描述如下：1.若二叉树为空，则返回2.否则依次执行后序遍历左子树后序遍历右子树访问根结点void PostOrder(BiTree T)if(T!=NULL)PostOrder(T-lchild);PostOrder(T-rchild);printf(%
8、2c,T-data);河南省政法管理干部学院河南省政法管理干部学院例：对如下二叉树进行后序遍历的结果为例：对如下二叉树进行后序遍历的结果为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，试构造该二叉树。，试构造该二叉树。基本思想：基本思想：在先序序列中找
9、根，在中序序列中分左右。在先序序列中找根，在中序序列中分左右。DEBA先序序列为：先序序列为：中序序列为：中序序列为：CEDABDEBCAECBABDA河南省政法管理干部学院河南省政法管理干部学院练习练习先序序列为：先序序列为：A B D E C F H G中序序列为：中序序列为：D B E A H F C G构造一棵二叉树。构造一棵二叉树。答案答案河南省政法管理干部学院河南省政法管理干部学院DEGFBCAH河南省政法管理干部学院河南省政法管理干部学院例例2：已知一棵二叉树的后序序列为：已知一棵二叉树的后序序列为DABEC，中序序列为中序序列为DEBAC，试构造该二叉树。，试构造该二叉树。基本
10、思想：基本思想：在后序序列中找根，在中序序列中分左右。在后序序列中找根，在中序序列中分左右。DEBA后序序列为：后序序列为：中序序列为：中序序列为：DABCEDEBCAECBABDA河南省政法管理干部学院河南省政法管理干部学院练习练习后序序列为：后序序列为：D E B H F G C A中序序列为：中序序列为：D B E A H F C G构造一棵二叉树。构造一棵二叉树。答案答案河南省政法管理干部学院河南省政法管理干部学院DEGFBCAH河南省政法管理干部学院河南省政法管理干部学院2.二叉树遍历的非递归算法河南省政法管理干部学院河南省政法管理干部学院2.二叉树遍历的非递归算法河南省政法管理干部
11、学院河南省政法管理干部学院2.二叉树遍历的非递归算法河南省政法管理干部学院河南省政法管理干部学院2.二叉树遍历的非递归算法河南省政法管理干部学院河南省政法管理干部学院2.二叉树先序遍历的非递归算法(1)先序遍历的非递归算法先序遍历的非递归算法令p指向根结点。若p不为空，访问访问p所指结点所指结点，并将p压入栈中。若p为空，转4。将p所指结点的左孩子压入栈，转2。1.从栈中弹出栈顶结点，令p指向所弹出结点的右孩子；转2。河南省政法管理干部学院河南省政法管理干部学院2.二叉树先序遍历的非递归算法ABCDEFGpiP-A(1)访问：AABCDEFGpiP-AP-B(2)访问：ABABCDEFGpiP
12、-AP-BP-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访问：ABC
13、DEGp(10)河南省政法管理干部学院河南省政法管理干部学院ABCDEFGiP-A访问：ABCDEGFp(13)ABCDEFGi访问：ABCDEGFp=NULL(14)河南省政法管理干部学院河南省政法管理干部学院2.二叉树先序遍历的非递归算法(2)中序遍历的非递归算法中序遍历的非递归算法令p指向根结点。若p不为空，将p压入栈中。若p为空，转4。将p所指结点的左孩子压入栈，转2。1.从栈中弹出栈顶结点，访问所弹出结点访问所弹出结点，令p指向所弹出结点的右孩子；转2。河南省政法管理干部学院河南省政法管理干部学院2.二叉树中序遍历的非递归算法ABCDEFGpiP-A(1)ABCDEFGpiP-AP-
14、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)ABCDEFGiP-AP-
15、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 先根（序）遍历：先访问树的根结点，然后依次先根遍历根的
16、每棵子树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.树和森林的遍历 森林的遍历 先根（序）遍历：v 先访问第一颗树的根结点v 先根遍历第一颗树中根结点的子树森林v 先根遍历除去第一颗树之后剩余树构成的森林 后根（序）遍历v 后跟遍历第一颗树的根结点的子树森林v 访问第一颗树的根结点1.后跟遍历除去第一颗树之后剩余树构成的森林河南省政法管理干部学院河南省政法管理干部学院此课件下载可自行编辑修改，仅供参考！此课件下载可自行编辑修改，仅供参考！感谢您的支持，我们努力做得更好！谢谢感谢您的支持，我们努力做得更好！谢谢
