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

数据结构基本知识二叉树遍历第一页，共44页。1.树的定义及性质树(tree)是n(n0)个结点的有限集T，其中：有且仅有一个特定的结点，称为树的根(root)当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,……Tm，其中每一个集合本身又是一棵树，称为根的子树(subtree)。回顾上节课主要内容2.二叉树的定义及性质二叉树是n(n0)个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成。第二页，共44页。3.二叉树的存储结构顺序存储结构按满二叉树的结点层次编号，依次存放二叉树中的数据元素链式存储结构使用二叉链表存储，通过指针指向左右子树。typedefcharElemType;typedefstructBiTNode{

ElemTypedata;structBiTNode*lchild,*rchild}BiTNode,*BiTree;BiTreebt;lchilddatarchild

第三页，共44页。4.树与二叉树转换ACBED树ABCDE二叉树A^^BC^D^^E^A^^BC^D^^E^A^^BC^D^^E^对应存储存储解释解释第四页，共44页。遍历——按一定规律走遍树的各个结点，且使每一结点仅被访问一次，即找一个完整而有规律的走法，以得到树中所有结点的一个线性排列。常用方法先序遍历：先访问根结点,然后分别先序遍历左子树、先序遍历右子树。中序遍历：先中序遍历左子树，然后访问根结点，最后中序遍历右子树。后序遍历：先后序遍历左、后序遍历右子树，然后访问根结点5.2二叉树的遍历

二叉树是n(n0)个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成。第五页，共44页。ADBC根左右A根左右根左右>B>>D>>C根左右先序遍历序列：ABDC先序遍历:ABDC第六页，共44页。第七页，共44页。先序遍历:算法过程描述如下：1.若二叉树为空，则返回2.否则依次执行①访问根结点②先序遍历左子树

③先序遍历右子树voidPreOrder(BiTreeT){if(T!=NULL){

printf("%3c",T->data);

PreOrder(T->lchild);

PreOrder(T->rchild);}}typedefstructBiTNode{

ElemTypedata;structBiTNode*lchild,*rchild}BiTNode,*BiTree;第八页，共44页。1.voidpre(BiTreeT)2.{if(T!=NULL)3.{printf("%3c",T->data);4.pre(T->L);5.pre(T->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第九页，共44页。例：对如下二叉树进行前序遍历的结果为ABDCEFFCADEGBABDECFFCADBEG第十页，共44页。左根右B左根右左根右>A>>D>>C左根右中序遍历序列：BDAC中序遍历:ADBCBDAC第十一页，共44页。第十二页，共44页。中序遍历:算法过程描述如下：1.若二叉树为空，则返回2.否则依次执行①中序遍历左子树②访问根结点③中序遍历右子树voidInOrder(BiTreeT){if(T!=NULL){

}}InOrder(T->lchild);printf("%3c",T->data);InOrder(T->rchild);typedefstructBiTNode{

ElemTypedata;structBiTNode*lchild,*rchild}BiTNode,*BiTree;第十三页，共44页。例：对如下二叉树进行中序遍历的结果为ABDCEFFCADEGBDBEAFCACBDFEG第十四页，共44页。ADBC左右根左右根左右根>A>>D>>C左右根后序遍历序列：DBCA后序遍历:BDBCA第十五页，共44页。第十六页，共44页。后序遍历:算法过程描述如下：1.若二叉树为空，则返回2.否则依次执行①后序遍历左子树②后序遍历右子树③访问根结点voidPostOrder(BiTreeT){if(T!=NULL){

}}PostOrder(T->lchild);PostOrder(T->rchild);printf("%2c",T->data);第十七页，共44页。例：对如下二叉树进行后序遍历的结果为ABDCEFFCADEGBDEBFCAABDCGEF第十八页，共44页。-+/a*b-efcd先序遍历：中序遍历：后序遍历：-+a*b-cd/ef-+a*b-cd/ef-+a*b-cd/ef第十九页，共44页。例1：已知一棵二叉树的先序序列为CEDBA，中序序列为DEBAC，试构造该二叉树。基本思想：在先序序列中找根，在中序序列中分左右。DEBA先序序列为：中序序列为：CEDABDEBCAECBABDA第二十页，共44页。练习先序序列为：ABDECFHG中序序列为：DBEAHFCG构造一棵二叉树。答案第二十一页，共44页。DEGFBCAH第二十二页，共44页。例2：已知一棵二叉树的后序序列为DABEC，中序序列为DEBAC，试构造该二叉树。基本思想：在后序序列中找根，在中序序列中分左右。DEBA后序序列为：中序序列为：DABCEDEBCAECBABDA第二十三页，共44页。练习后序序列为：DEBHFGCA中序序列为：DBEAHFCG构造一棵二叉树。答案第二十四页，共44页。DEGFBCAH第二十五页，共44页。2.二叉树遍历的非递归算法第二十六页，共44页。2.二叉树遍历的非递归算法第二十七页，共44页。2.二叉树遍历的非递归算法第二十八页，共44页。2.二叉树遍历的非递归算法第二十九页，共44页。2.二叉树先序遍历的非递归算法(1)先序遍历的非递归算法令p指向根结点。若p不为空，访问p所指结点，并将p压入栈中。若p为空，转4。将p所指结点的左孩子压入栈，转2。从栈中弹出栈顶结点，令p指向所弹出结点的右孩子；转2。第三十页，共44页。2.二叉树先序遍历的非递归算法ABCDEFGpiP->A(1)访问：AABCDEFGpiP->AP->B(2)访问：ABABCDEFGpiP->AP->BP->C(3)访问：ABCABCDEFGpiP->AP->B(4)访问：ABC第三十一页，共44页。ABCDEFGiP->AP->DP->E访问：ABCDEp(7)p=NULLABCDEFGiP->A(5)访问：ABCp=NULLABCDEFGiP->AP->D(6)访问：ABCDABCDEFGiP->AP->D访问：ABCDEp(8)第三十二页，共44页。ABCDEFGiP->AP->F访问：ABCDEGFp(12)ABCDEFGiP->AP->DP->G访问：ABCDEGp(9)ABCDEFGiP->A访问：ABCDEGp(11)ABCDEFGiP->AP->D访问：ABCDEGp(10)第三十三页，共44页。ABCDEFGiP->A访问：ABCDEGFp(13)ABCDEFGi访问：ABCDEGFp=NULL(14)第三十四页，共44页。2.二叉树先序遍历的非递归算法(2)中序遍历的非递归算法令p指向根结点。若p不为空，将p压入栈中。若p为空，转4。将p所指结点的左孩子压入栈，转2。从栈中弹出栈顶结点，访问所弹出结点，令p指向所弹出结点的右孩子；转2。第三十五页，共44页。2.二叉树中序遍历的非递归算法ABCDEFGpiP->A(1)ABCDEFGpiP->AP->B(2)ABCDEFGpiP->AP->BP->C(3)p=NULLABCDEFGiP->AP->B访问：C(4)第三十六页，共44页。pABCDEFGiP->A访问：CB(5)ABCDEFGiP->AP->D访问：CBp(6)ABCDEFGiP->AP->DP->E访问：CBp(7)ABCDEFGiP->AP->D访问：CBEp(8)第三十七页，共44页。ABCDEFGiP->AP->DP->G访问：CBEP=NULL(9)ABCDEFGiP->A访问：CBEGDp(11)ABCDEFGiP->AP->F访问：CBEGDp(12)ABCDEFGiP->AP->D访问：CBEGp(10)第三十八页，共44页。ABCDEFGiP->A访问：CBEGDFp=NULL(13)ABCDEFGi访问：CBEGDFAp(14)第三十九页，共44页。遍历算法应用按先序遍历序列建立二叉树的二叉链表，已知先序序列为：ABCDEGF求二叉树深度算法ABCDEFG统计二叉树中叶子结点个数算法第四十页，共44页。3.二叉树的层次遍历第四十一页，共44页。4.树和森林的遍历