数据结构基本知识二叉树遍历

数据结构基本知识二叉树遍历树()是n(n0)个结点的有限集T，其中：有且仅有一个特定的结点，称为树的根()当n>1时，其余结点可分为m(m>0)个互不相交的有限集T12,……，其中每一个集合本身又是一棵树，称为根的子树()。回顾上节课主要内容二叉树是n(n0)个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成。顺序存储结构按满二叉树的结点层次编号，依次存放二叉树中的数据元素链式存储结构使用二叉链表存储，通过指针指向左右子树。;{;*,*},*;;lchilddatarchildACBED树ABCDE二叉树A^^BC^D^^E^A^^BC^D^^E^A^^BC^D^^E^对应存储存储解释解释遍历——按一定规律走遍树的各个结点，且使每一结点仅被访问一次，即找一个完整而有规律的走法，以得到树中所有结点的一个线性排列。常用方法先序遍历：先访问根结点,然后分别先序遍历左子树、先序遍历右子树。中序遍历：先中序遍历左子树，然后访问根结点，最后中序遍历右子树。后序遍历：先后序遍历左、后序遍历右子树，然后访问根结点5.2二叉树的遍历二叉树是n(n0)个结点的有限集，它或为空树(0)，或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成。ADBC根左右A根左右根左右>B>>D>>C根左右先序遍历序列：ABDC先序遍历:ABDC先序遍历:算法过程描述如下：1.若二叉树为空，则返回①访问根结点②先序遍历左子树③先序遍历右子树(T){(){("%3c">);(>);(>);}}{;*,*},*;1.(T)2.{()3.{("%3c">);4.(>L);5.(>R);6.}7.}主程序Pre(T)返回返回pre(TR);返回返回pre(TR);ACBDTBprintf(B);pre(TL);BTAprintf(A);pre(TL);ATDprintf(D);pre(TL);DTCprintf(C);pre(TL);C返回T>左是空返回pre(TR);T>左是空返回T>右是空返回T>左是空返回T>右是空返回pre(TR);先序序列：ABDC例：对如下二叉树进行前序遍历的结果为ABDCEFFCADEGBABDECFFCADBEG左根右B左根右左根右>A>>D>>C左根右中序遍历序列：BDAC中序遍历:ADBCBDAC中序遍历:算法过程描述如下：1.若二叉树为空，则返回①中序遍历左子树②访问根结点③中序遍历右子树(T){(){

}}(>);("%3c">);(>);{;*,*},*;例：对如下二叉树进行中序遍历的结果为ABDCEFFCADEGBDBEAFCACBDFEGADBC左右根左右根左右根>A>>D>>C左右根后序遍历序列：DBCA后序遍历:BDBCA后序遍历:算法过程描述如下：1.若二叉树为空，则返回①后序遍历左子树②后序遍历右子树③访问根结点(T){(){

}}(>);(>);("%2c">);例：对如下二叉树进行后序遍历的结果为ABDCEFFCADEGBDEBFCAABDCGEF-+/a*b-efcd先序遍历：中序遍历：后序遍历：-+a*b-cd/ef-+a*b-cd/ef-+a*b-cd/ef例1：已知一棵二叉树的先序序列为，中序序列为，试构造该二叉树。基本思想：在先序序列中找根，在中序序列中分左右。先序序列为：中序序列为：CEDABDEBCAECBDA练习先序序列为：ABDECFHG中序序列为：DBEAHFCG构造一棵二叉树。答案DEGFBCAH例2：已知一棵二叉树的后序序列为，中序序列为，试构造该二叉树。基本思想：在后序序列中找根，在中序序列中分左右。后序序列为：中序序列为：DABCEDEBCAECBDA练习后序序列为：DEBHFGCA中序序列为：DBEAHFCG构造一棵二叉树。答案DEGFBCAH(1)先序遍历的非递归算法令p指向根结点。若p不为空，访问p所指结点，并将p压入栈中。若p为空，转4。将p所指结点的左孩子压入栈，转2。从栈中弹出栈顶结点，令p指向所弹出结点的右孩子；转2。ABCDEFGpiP->A(1)访问：AABCDEFGpiP->AP->B(2)访问：ABABCDEFGpiP->AP->BP->C(3)访问：ABCABCDEFGpiP->AP->B(4)访问：ABCABCDEFGiP->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(10)ABCDEFGiP->A访问：ABCDEGFp(13)ABCDEFGi访问：ABCDEGFp=NULL(14)(2)中序遍历的非递归算法令p指向根结点。若p不为空，将p压入栈中。若p为空，转4。将p所指结点的左孩子压入栈，转2。从栈中弹出栈顶结点，访问所弹出结点，令p指向所弹出结点的右孩子；转2。ABCDEFGpiP->A(1)ABCDEFGpiP->AP->B(2)ABCDEFGpiP->AP->BP->C(3)p=NULLABCDEFGiP->AP->B访问：C(4)pABCDEFGiP->A访问：CB(5)ABCDEFGiP->AP->D访问：CBp(6)ABCDEFGiP->AP->DP->E访问：CBp(7)ABCDEFGiP->AP->D访问：CBEp(8)ABCDEFGiP->AP->DP->G访问：CBEP=NULL(9)ABCDEFGiP->A访问：CBEGDp(11)ABCDEFGiP->AP->F访问：CBEGDp(12)ABCDEFGiP->AP->D访问：CBEGp(10)ABCDEFGiP->A访问：CBEGDFp=NULL(13)ABCDEFGi访问：CBEGDFAp(14)遍历算法应用按先序遍历序列建立二叉树的二叉链表，已知先序序列为：ABCDEGF求二叉树深度算法ABCDEFG统计二叉树中叶子结点个数算法4.树和森林的遍历树的遍历先根（序）遍历：先访问树的根结点，然后依次先根遍历根的每棵子树后根（序）遍历：先依次后根遍历每棵子树，然后访问根结点按层次遍历：先访问第一层上的结点，然后依次遍历第二层，……第n层的结点ABCDEFGHIJKLMNO先序遍历：后序遍历：层次遍历：ABEFIG