《数据结构第6章_树学习教案.pptx》由会员分享，可在线阅读，更多相关《数据结构第6章_树学习教案.pptx（85页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构数据结构(sh j ji u)第第6章章_树树第一页，共85页。2023/2/72023/2/72 26.1 树的概念(ginin)树的定义树的定义(递归定义递归定义)：树（：树（Tree）是是n（n0）个结点的有限集合）个结点的有限集合T，满足两个条件：满足两个条件：（1）有且仅有一个特定的称为）有且仅有一个特定的称为根（根（Root）的结点，它没有前趋；）的结点，它没有前趋；（2）其余的结点可分成）其余的结点可分成(fn chn)m个互不相交的有限集合个互不相交的有限集合T1,T2,Tm，其中每个集合又是，其中每个集合又是一棵树，并称为根的子树。一棵树，并称为根的子树。当当n=0时
2、的空集合定义为空树。时的空集合定义为空树。第1页/共85页第二页，共85页。2023/2/72023/2/73 3使用圆圈表示结点使用圆圈表示结点(ji din)(ji din)，连线表示结点，连线表示结点(ji din)(ji din)之间的关系，之间的关系，结点结点(ji din)(ji din)的名字可写在圆圈内或圆圈旁。的名字可写在圆圈内或圆圈旁。n n树的直观树的直观(zhgun)(zhgun)表示法表示法第2页/共85页第三页，共85页。2023/2/72023/2/74 4n n树的基本树的基本(jbn)(jbn)术语术语l l结点：指树中的一个元素，包含数据项及若干结点：指树中
3、的一个元素，包含数据项及若干(rugn)(rugn)指向其子指向其子树的分支。树的分支。l l结点的度：指结点拥有的子树个数。结点的度：指结点拥有的子树个数。l l树的度：指树中结点的度的最大值。树的度：指树中结点的度的最大值。第3页/共85页第四页，共85页。2023/2/72023/2/75 5l l叶子：指度为零的结点，又称为终端结点。叶子：指度为零的结点，又称为终端结点。l l孩子：一个结点的子树的根称为该结点的孩子。孩子：一个结点的子树的根称为该结点的孩子。l l双亲：一个结点的直接双亲：一个结点的直接(zhji)(zhji)上层结点称为该结点的双亲。上层结点称为该结点的双亲。l l
4、兄弟：同一双亲的孩子互称为兄弟。兄弟：同一双亲的孩子互称为兄弟。l l结结点点的的层层次次：从从根根结结点点开开始始，根根结结点点为为第第一一层层，根根的的孩孩子子为为第第二二层，根的孩子的孩子为第三层，依次类推。层，根的孩子的孩子为第三层，依次类推。l l树的深度：树中结点的最大层次数。树的深度：树中结点的最大层次数。l l堂兄弟：双亲在同一层上的结点互称为堂兄弟。堂兄弟：双亲在同一层上的结点互称为堂兄弟。第4页/共85页第五页，共85页。2023/2/72023/2/76 6l l路路径径：若若存存在在一一个个结结点点序序列列k1,k2,kj,k1,k2,kj,可可使使k1k1到到达达kj
5、,kj,则则称称这个结点序列是这个结点序列是k1k1到达到达kjkj的一条路径。的一条路径。l l子子 孙孙 和和 祖祖 先先：若若 存存 在在 k1k1到到 kjkj的的 一一 条条 路路 径径 k1,k2,kjk1,k2,kj，则则k1,kj-1k1,kj-1为为kjkj的祖先，而的祖先，而k2,kjk2,kj为为k1k1的子孙。的子孙。l l森林：森林：m(m0)m(m0)棵互不相交的树的集合构成森林。棵互不相交的树的集合构成森林。l l有有序序树树和和无无序序树树：若若将将树树中中每每个个结结点点的的各各个个子子树树都都看看成成是是从从左左到到右右有有次次序序(cx)(cx)的的（即即
6、不不能能互互换换），则则称称该该树树为为有有序序树树，否则为无序树。否则为无序树。第5页/共85页第六页，共85页。2023/2/72023/2/77 7顺序存储顺序存储顺序存储时，首先必须对树形结构的结点进行某种方式的线性顺序存储时，首先必须对树形结构的结点进行某种方式的线性化，使之成为一个线性序列，然后存储。化，使之成为一个线性序列，然后存储。链式存储链式存储链式存储时，使用多指针域的结点形式，每一个指针域指向链式存储时，使用多指针域的结点形式，每一个指针域指向(zh xin)(zh xin)一棵子树的根结点。一棵子树的根结点。由于树的分支数不固定，很难给出一种固定的存储结构，通常由于树的
7、分支数不固定，很难给出一种固定的存储结构，通常采用二叉树的形式存储树。采用二叉树的形式存储树。树的存储树的存储(cn ch)(cn ch)结构结构第6页/共85页第七页，共85页。2023/2/72023/2/78 86.2 6.2 二叉树二叉树定义（二叉树的递归定义）：定义（二叉树的递归定义）：二叉树是二叉树是n n（n0n0）个结点的有限集，它或为空树（）个结点的有限集，它或为空树（n=0n=0），），或由一个根结点及两棵互不相交或由一个根结点及两棵互不相交(xingjio)(xingjio)的、分别称作的、分别称作这个根的左子树和右子树的二叉树构成。这个根的左子树和右子树的二叉树构成。二
8、叉树的五种基本形态：二叉树的五种基本形态：二叉树与度为二叉树与度为2 2的树的区别：二叉树的子树有左右之分，而的树的区别：二叉树的子树有左右之分，而树的子树不分左右；树的子树不分左右；第7页/共85页第八页，共85页。2023/2/72023/2/79 9uu满二叉树和完全满二叉树和完全(wnqun)(wnqun)二叉二叉树树l l一棵深度为一棵深度为k k且有且有2k-12k-1个结点的二叉树称为满二叉树。个结点的二叉树称为满二叉树。满二叉树的特点是每一层的结点数都达到该层可具有的最满二叉树的特点是每一层的结点数都达到该层可具有的最大结点数。大结点数。l l如果一个深度为如果一个深度为k k
9、的二叉树，它的结点按照从根结点开始，的二叉树，它的结点按照从根结点开始，自上而下，从左至右进行连续编号自上而下，从左至右进行连续编号(bin ho)(bin ho)后，得到的顺后，得到的顺序与满二叉树相应结点编号序与满二叉树相应结点编号(bin ho)(bin ho)顺序一致，则称这个顺序一致，则称这个二叉树为完全二叉树。完全二叉树的二叉树为完全二叉树。完全二叉树的1k-11k-1层上共有层上共有2k-1-12k-1-1个结点，第个结点，第k k层的结点集中在左边。层的结点集中在左边。l l满二叉树一定是完全二叉树，而完全二叉树不一定是满二满二叉树一定是完全二叉树，而完全二叉树不一定是满二叉树
10、。叉树。第8页/共85页第九页，共85页。2023/2/72023/2/71010二叉树的性质二叉树的性质(xngzh)-1(xngzh)-1性质性质1 1：在二叉树的第：在二叉树的第i i层上至多层上至多(zhdu)(zhdu)有有2i-12i-1个结点个结点(i1)(i1)。证明：可用数学归纳法予以证明。证明：可用数学归纳法予以证明。当当i=1i=1时，有时，有2i-1=20=12i-1=20=1，同时第一层上只有一个根结点，故，同时第一层上只有一个根结点，故命题成立。命题成立。设当设当i=ki=k时成立，即第时成立，即第k k层上至多层上至多(zhdu)(zhdu)有有2k-12k-1个
11、结点。个结点。当当i=k+1i=k+1时，由于二叉树的每个结点至多时，由于二叉树的每个结点至多(zhdu)(zhdu)有两个孩有两个孩子，所以第子，所以第k+1k+1层上至多层上至多(zhdu)(zhdu)有有2 2 2k-1=2k2k-1=2k个结点，故个结点，故命题成立。命题成立。第9页/共85页第十页，共85页。2023/2/72023/2/71111二叉树的性质二叉树的性质(xngzh)-2(xngzh)-2性质性质2 2：深度为：深度为k k的二叉树至多的二叉树至多(zhdu)(zhdu)有有2k-12k-1个结点个结点(k1)(k1)。证明：性质证明：性质1 1给出了二叉树每一层中
12、含有的最大结点数，深度为给出了二叉树每一层中含有的最大结点数，深度为k k的二叉树的结点总数至多的二叉树的结点总数至多(zhdu)(zhdu)为为故命题成立。故命题成立。第10页/共85页第十一页，共85页。2023/2/72023/2/71212二叉树的性质二叉树的性质(xngzh)-3(xngzh)-3性质性质3 3：对任何一棵二叉树，如果其终端结点：对任何一棵二叉树，如果其终端结点(ji din)(ji din)数为数为n0n0，度，度为为2 2的结点的结点(ji din)(ji din)数为数为n2n2，则，则n0=n2+1n0=n2+1。证明：设度为证明：设度为1 1的结点的结点(j
13、i din)(ji din)数为数为n1n1，则一棵二叉树的结点，则一棵二叉树的结点(ji din)(ji din)总数为：总数为：n=n0+n1+n2 n=n0+n1+n2 因为除根结点因为除根结点(ji din)(ji din)外，其余结点外，其余结点(ji din)(ji din)都有一个进入的都有一个进入的分支分支(边边)，设，设B B为分支总数，则为分支总数，则n=B+1n=B+1。又考虑到分支是由度为。又考虑到分支是由度为1 1和和2 2的结点的结点(ji din)(ji din)发出的，故有发出的，故有 B=2n2+n1 B=2n2+n1，即，即 n=2n2+n1+1 n=2n2
14、+n1+1 比较两式可得比较两式可得n0=n2+1n0=n2+1，证毕。，证毕。第11页/共85页第十二页，共85页。2023/2/72023/2/71313二叉树的性质二叉树的性质(xngzh)-4(xngzh)-4性质性质4 4：具有：具有n n个结点的完全二叉树的深度为个结点的完全二叉树的深度为 log2nlog2n+1+1或或 log2(n+1)log2(n+1)。(其中其中 x x 表示不大于表示不大于x x的最大整数，的最大整数，x x 表示不小于表示不小于x x的最小的最小整数。整数。)证明：设完全二叉树的深度为证明：设完全二叉树的深度为k k，则有，则有 2k-1-1 n 2k
15、-1-1 n 2k 1 (1)2k 1 (1)(1)(1)式变形为式变形为 2k-1 n+1 2k-1 n+1 2k 2k，两边取对数，两边取对数 k-1log2 k-1log2（n n1 1）k k 取整得取整得 k k log2(n+1)log2(n+1)2k-1 2k-1 n 2k n 2k（第（第k k层至少有一个层至少有一个(y)(y)结点）结点）（2 2）两边取对数两边取对数 k-1 k-1 log2n k log2n 1,i 1,则则 i i 的双亲为的双亲为 i/2i/2 若若2*i n,2*i n,则则 i i 的左孩子为的左孩子为2*i2*i，否则无左孩子，否则无左孩子若若
16、2*i+1 n,2*i+1 n,则则 i i 的右孩子为的右孩子为2*i+12*i+1，否则无右孩子，否则无右孩子若若i i为偶数为偶数,且且i!=n,i!=n,则其右兄弟为则其右兄弟为i+1i+1若若i i为奇数为奇数,且且i!=1,i!=1,则其左兄弟为则其左兄弟为i-1i-1结点结点i i 所在层次为所在层次为 log2ilog2i +1+1第13页/共85页第十四页，共85页。2023/2/72023/2/715156.3 6.3 二叉树的存储二叉树的存储(cn ch)(cn ch)结构结构6.3.1 6.3.1 顺序存储结构顺序存储结构完全二叉树完全二叉树根据二叉树性质根据二叉树性质
17、5 5，在一棵完全二叉树中，按照从根结点起，在一棵完全二叉树中，按照从根结点起，自上而下，从左至右的方式对结点进行顺序编号，便可得自上而下，从左至右的方式对结点进行顺序编号，便可得到到(d do)(d do)一个反映结点之间关系的线性序列。一个反映结点之间关系的线性序列。下图的完全二叉树的顺序存储结构如下表：下图的完全二叉树的顺序存储结构如下表：第14页/共85页第十五页，共85页。2023/2/72023/2/71616一般二叉树一般二叉树将二叉树映射为完全二叉树（通过虚结点）将二叉树映射为完全二叉树（通过虚结点）用完全二叉树的方式存储。用完全二叉树的方式存储。根据性质根据性质2 2，采用，
18、采用(ciyng)(ciyng)顺序存储结构存储一棵深度为顺序存储结构存储一棵深度为k k的完全二叉树或一般二叉树，向量的长度是的完全二叉树或一般二叉树，向量的长度是2k-12k-1。第15页/共85页第十六页，共85页。2023/2/72023/2/71717由于由于(yuy)(yuy)一般二叉树必须仿照完全二叉树那样存储，可能会浪费很一般二叉树必须仿照完全二叉树那样存储，可能会浪费很多存储空间，单支树就是一个极端情况。多存储空间，单支树就是一个极端情况。存储上述单支二叉树，所需的向量长度为存储上述单支二叉树，所需的向量长度为25-1=3125-1=31第16页/共85页第十七页，共85页。
19、2023/2/72023/2/718186.3.2 6.3.2 链式存储结构链式存储结构二叉树的链式存储结构二叉树的链式存储结构每个结点含有数据域和两个指针域，左、右指针域分别用每个结点含有数据域和两个指针域，左、右指针域分别用来指向左孩子和右孩子。二叉树的链式存储结构也称为二来指向左孩子和右孩子。二叉树的链式存储结构也称为二叉链表。叉链表。二叉链表结点的二叉链表结点的C C语言逻辑描述为：语言逻辑描述为：typedef int datatypetypedef int datatype；typedef struct nodetypedef struct node datatype datada
20、tatype data；struct node*lchildstruct node*lchild，*rchild*rchild；bitreebitree；bitree *root;bitree *root;注：注：其中其中rootroot是指向根结点的指针，当二叉树为空时，则是指向根结点的指针，当二叉树为空时，则root=NULLroot=NULL。若结点的某个若结点的某个(mu)(mu)孩子不存在时，则相应的指针域为孩子不存在时，则相应的指针域为空。空。第17页/共85页第十八页，共85页。2023/2/72023/2/71919三叉链表三叉链表为了能够寻找双亲为了能够寻找双亲(shungq
21、n)(shungqn)结点，在结点结点，在结点中增加一个指向双亲中增加一个指向双亲(shungqn)(shungqn)结点的指针域结点的指针域parentparent。第18页/共85页第十九页，共85页。2023/2/72023/2/720206.3.3 二叉树建立(jinl)（二叉链表的建立(jinl)）第19页/共85页第二十页，共85页。2023/2/72023/2/721216.3.3 6.3.3 二叉树建立二叉树建立(jinl)(jinl)（二叉链表的建立（二叉链表的建立(jinl)(jinl)）uu二叉树的建立二叉树的建立uu 指在内存中如何建立二叉树的存储结构。指在内存中如何建
22、立二叉树的存储结构。uu基本思想基本思想 uu对顺序存储结构而言，只需将二叉树各个对顺序存储结构而言，只需将二叉树各个(gg)(gg)结点的结点的值按原有的逻辑关系送入相应的向量单元中。值按原有的逻辑关系送入相应的向量单元中。uu对链式存储结构而言，其建立算法有多种，它们依赖于对链式存储结构而言，其建立算法有多种，它们依赖于按照何种形式来输入二叉树的逻辑结构信息。常用的算法是按照完全二按照何种形式来输入二叉树的逻辑结构信息。常用的算法是按照完全二叉树的层次顺序，依次输入结点信息来建立二叉链表。对于一般二叉树，叉树的层次顺序，依次输入结点信息来建立二叉链表。对于一般二叉树，则必须通过先添加若干个
23、虚结点使其成为完全二叉树。则必须通过先添加若干个虚结点使其成为完全二叉树。第20页/共85页第二十一页，共85页。2023/2/72023/2/72222uu 基本步骤基本步骤uu按照结点的序号，依次输入结点信息，若按照结点的序号，依次输入结点信息，若输入的结点不是虚结点，则建立一个新结输入的结点不是虚结点，则建立一个新结点。点。uu若新结点是第若新结点是第1 1个结点，则令其为根结点，个结点，则令其为根结点，否则将新结点作为孩子链接到它的双亲结否则将新结点作为孩子链接到它的双亲结点上。点上。uu如此反复进行，直到输入结束标志如此反复进行，直到输入结束标志(biozh)“(biozh)“”为止
24、。为止。uu问题：如何将新结点正确地链接到它的双问题：如何将新结点正确地链接到它的双亲结点上？亲结点上？第21页/共85页第二十二页，共85页。2023/2/72023/2/72323 算法具体实现算法具体实现依据先建立的结点，其孩子结点也一定先建立的特点，依据先建立的结点，其孩子结点也一定先建立的特点，所以可以设置一个所以可以设置一个(y)(y)指针数组构成的队列来保存已指针数组构成的队列来保存已输入结点的地址（虚结点的地址为空），并使队尾输入结点的地址（虚结点的地址为空），并使队尾(rear)(rear)指向当前输入的结点；队头指向当前输入的结点；队头(front)(front)指向这个结
25、点的双亲指向这个结点的双亲结点。结点。由于根结点的地址放在（顺序）队列的（指针）数组下由于根结点的地址放在（顺序）队列的（指针）数组下标为标为1 1的数组单元里，所以当的数组单元里，所以当rearrear为偶数时，则为偶数时，则rearrear所指所指的结点应作为左孩子与其双亲链接，否则的结点应作为左孩子与其双亲链接，否则rearrear所指的结所指的结点应作为右孩子与其双亲链接。点应作为右孩子与其双亲链接。若双亲结点或孩子结点为虚结点，则不需链接。若双亲结点或孩子结点为虚结点，则不需链接。当一个当一个(y)(y)双亲结点与两个孩子链接完毕，则进行出双亲结点与两个孩子链接完毕，则进行出队操作，
26、使队头指针指向下一个队操作，使队头指针指向下一个(y)(y)待链接的双亲结待链接的双亲结点。点。第22页/共85页第二十三页，共85页。2023/2/72023/2/72424二叉树的建立算法二叉树的建立算法bitree*CREATREE()bitree*CREATREE()/*/*建立二叉树函数，函数返回指向根结点的指针建立二叉树函数，函数返回指向根结点的指针*/*/char char chch；/*/*结点信息变量结点信息变量*/*/bitree*Q maxsize bitree*Q maxsize；/*/*设置指针类型数组来构成队列设置指针类型数组来构成队列(duli)*(duli)*i
27、nt intfront,rearfront,rear；/*/*队头和队尾指针变量队头和队尾指针变量*/*/bitree *root,*s bitree *root,*s；/*/*根结点指针和中间指针变量根结点指针和中间指针变量*/*/root=NULL root=NULL；/*/*二叉树置空二叉树置空*/*/front=1;rear=0;/*front=1;rear=0;/*设置队列设置队列(duli)(duli)指针变量初值指针变量初值*/*/*/*以上为初始化以上为初始化*/*/第23页/共85页第二十四页，共85页。2023/2/72023/2/72525while(ch=getchar
28、()!=#)/*while(ch=getchar()!=#)/*输入一个字符，当不是结束符时执行以下操作输入一个字符，当不是结束符时执行以下操作*/*/s=NULL;s=NULL;if(ch!=)/*if(ch!=)/*表示虚结点，当不是虚结点则建立新结点表示虚结点，当不是虚结点则建立新结点*/*/s=malloc(sizeof(bitree);s=malloc(sizeof(bitree);sdata=ch;sdata=ch;slchild=NULL;slchild=NULL;srchild=NULL;srchild=NULL;rear+;/*rear+;/*队尾指针增队尾指针增1 1，指向
29、新结点地址应存放，指向新结点地址应存放(cnfng)(cnfng)的单元的单元*/*/Qrear=s;/*Qrear=s;/*将新结点地址入队或虚结点指针将新结点地址入队或虚结点指针NULLNULL入队入队*/*/if(rear=1)root=s;/*if(rear=1)root=s;/*输入的第一个结点作为根结点输入的第一个结点作为根结点*/*/else if(s&Qfront)/*else if(s&Qfront)/*孩子和双亲结点都不是虚结点孩子和双亲结点都不是虚结点*/*/if(rear%2=0)Qfrontlchild=s;/*rear if(rear%2=0)Qfrontlchil
30、d=s;/*rear为偶数，新结点是左孩子为偶数，新结点是左孩子*/*/else Qfrontrchild=s;/*rear else Qfrontrchild=s;/*rear为奇数且不等于为奇数且不等于1 1，新结点是右孩子，新结点是右孩子*/*/if(rear%2=1)if(rear%2=1)front+;/*front+;/*结点结点*Qfront*Qfront的两个孩子处理完毕，出队列的两个孩子处理完毕，出队列*/*/return root;/*return root;/*返回根指针返回根指针*/*/*CREATREE */*CREATREE */第24页/共85页第二十五页，共85
31、页。2023/2/72023/2/726266.4 6.4 二叉树的遍历二叉树的遍历(bin l)(bin l)所谓树的遍历，就是按某种次序访问树中的结点所谓树的遍历，就是按某种次序访问树中的结点(ji din)(ji din)，要求每个结点要求每个结点(ji din)(ji din)访问一次且仅访问一次。访问一次且仅访问一次。遍历的结果：产生一个关于结点遍历的结果：产生一个关于结点(ji din)(ji din)的线性序列。的线性序列。6.4.1 6.4.1 深度优先递归遍历深度优先递归遍历 访问根结点访问根结点(ji din)(ji din)记作记作 D D 遍历根的左子树记作遍历根的左子
32、树记作 L L 遍历根的右子树记作遍历根的右子树记作 R R 则可能的遍历次序有：则可能的遍历次序有：先序先序 DLR DLR 逆先序逆先序 DRL DRL 中序中序 LDR LDR 逆中序逆中序 RDL RDL 后序后序 LRD LRD 逆后序逆后序 RLD RLD第25页/共85页第二十六页，共85页。2023/2/72023/2/727271.1.先序遍历先序遍历DLRDLR2.2.先序遍历算法的遍历过程先序遍历算法的遍历过程(guchng)(guchng)3.3.若二叉树非空，执行以下操作：若二叉树非空，执行以下操作：4.4.访问根结点；访问根结点；5.5.先序遍历左子树；先序遍历左子
33、树；6.6.先序遍历右子树。先序遍历右子树。7.7.void preorder(bitree*p)void preorder(bitree*p)8.8./*/*先序遍历二叉树，先序遍历二叉树，p p指向二叉树的根结点指向二叉树的根结点*/*/9.9.if(p!=NULL)/*if(p!=NULL)/*二叉树二叉树p p非空，则执行以下非空，则执行以下操作操作*/*/10.10.printf(“%c”,p-data);/*printf(“%c”,p-data);/*访问访问p p所指结点所指结点*/*/11.11.preorder(p-lchild);/*preorder(p-lchild);/
34、*先序遍历先序遍历左子树左子树*/*/12.12.preorder(p-rchild);/*preorder(p-rchild);/*先序遍历先序遍历右子树右子树*/*/13.13.14.14.遍历遍历(bin l)结果：结果：abdefc第26页/共85页第二十七页，共85页。2023/2/72023/2/728282.2.中序遍历中序遍历LDRLDR3.3.中序遍历算法的遍历过程中序遍历算法的遍历过程4.4.若二叉树非空，执行以下操作：若二叉树非空，执行以下操作：5.5.中序遍历左子树；中序遍历左子树；6.6.访问访问(fngwn)(fngwn)根结点；根结点；7.7.中序遍历右子树。中序
35、遍历右子树。8.8.void inorder(bitree*p)void inorder(bitree*p)9.9./*/*中序遍历二叉树，中序遍历二叉树，p p指向二叉树的根结点指向二叉树的根结点*/*/10.10.if if(p!=NULL)(p!=NULL)/*/*二二叉叉树树p p非非空空，则则执执行行以以下操作下操作*/*/11.11.inorder inorder(p-lchild);(p-lchild);/*/*中中序序遍遍历历左子树左子树*/*/12.12.printf printf(“(“%c%c”,”,p-data);p-data);/*/*访访问问(fngwn)p(fng
36、wn)p所指结点所指结点*/*/13.13.inorder inorder(p-rchild);(p-rchild);/*/*中中序序遍遍历历右子树右子树*/*/14.14.15.15.遍历遍历(bin l)结果：结果：dbefac第27页/共85页第二十八页，共85页。2023/2/72023/2/729293.3.后序遍历后序遍历LRDLRD4.4.后序遍历算法的遍历过程后序遍历算法的遍历过程5.5.若二叉树非空，执行以下若二叉树非空，执行以下(yxi)(yxi)操作：操作：6.6.后序遍历左子树；后序遍历左子树；7.7.后序遍历右子树；后序遍历右子树；8.8.访问根结点。访问根结点。9.
37、9.void postorder(bitree*p)void postorder(bitree*p)10.10./*/*后序遍历二叉树，后序遍历二叉树，p p指向二叉树的根结点指向二叉树的根结点*/*/11.11.if if(p!=NULL)(p!=NULL)/*/*二二叉叉树树p p非非空空，则则执执行行以下以下(yxi)(yxi)操作操作*/*/12.12.postorder postorder(p-lchild);(p-lchild);/*/*后后序遍历左子树序遍历左子树*/*/13.13.postorder postorder(p-rchild);(p-rchild);/*/*后后序遍
38、历右子树序遍历右子树*/*/14.14.printf printf(“(“%c%c”,”,p-data);p-data);/*/*访问访问p p所指结点所指结点*/*/15.15.16.16.遍历遍历(bin l)结果：结果：dfebca第28页/共85页第二十九页，共85页。2023/2/72023/2/730306.4.2 二叉树的广度优先遍历（按层次遍历二叉树）从根开始逐层访问。先遍历二叉树的第一层结点，然后遍历第二层结点，最后遍历最下层的结点。而对每一层的遍历是按从左至 右 的 方 式 进 行。在上层中先被访问的结点，它的下层孩子也必然先被访问，因此在这种遍历算法的实现时，需要使用一个
39、队列。在遍历进行之前先把二叉树的根结点的存储(cn ch)地址入队，然后依次从队列中出队结点的存储(cn ch)地址，每出队一个结点的存储(cn ch)地址则对该结点进行访问，然后依次将该结点的左孩子和右孩子的存储(cn ch)地址入队，如此反复，直到队空为止。广度优先(yuxin)遍历算法第29页/共85页第三十页，共85页。2023/2/72023/2/73131Bitree*Qmaxsize;Bitree*Qmaxsize;void layer(BiTree*p)void layer(BiTree*p)BiTree*s;BiTree*s;if(p!=NULL)if(p!=NULL)rea
40、r=1;rear=1;front=0;front=0;Qrear=p;Qrear=p;while(frontrear)/while(frontdata);printf(%c,s-data);if(s-lchild!=NULL)/if(s-lchild!=NULL)/左子树非空左子树非空 rear+;rear+;Qrear=s-lchild;/Qrear=s-lchild;/左子树根结点入队左子树根结点入队 二叉树的广度二叉树的广度(gungd)优先遍历实例优先遍历实例第30页/共85页第三十一页，共85页。2023/2/72023/2/73232 if(s-rchild!=NULL)/右子树非
41、空 rear+;Qrear=s-lchild;/右子树根结点(ji din)入队 第31页/共85页第三十二页，共85页。2023/2/733ABCDEFG二叉树的广度优先遍历二叉树的广度优先遍历二叉树的广度优先遍历二叉树的广度优先遍历(bin l)(bin l)实例实例实例实例输出序列为：输出序列为：输出序列为：输出序列为：A,B,C,D,E,F,GA,B,C,D,E,F,G第32页/共85页第三十三页，共85页。2023/2/72023/2/734346.4.3 6.4.3 深度优先的非递归算法深度优先的非递归算法 分析：二叉树的深度优先遍历算法是以分析：二叉树的深度优先遍历算法是以递归形
42、式递归形式(xngsh)(xngsh)给出的，运行效率低，给出的，运行效率低，可读性不强。因递归调用过程要用到栈来可读性不强。因递归调用过程要用到栈来保存每次调用的参数，所以，我们可以用保存每次调用的参数，所以，我们可以用栈来实现二叉树的深度优先遍历，将递归栈来实现二叉树的深度优先遍历，将递归算法转化为非递归算法。算法转化为非递归算法。以中序遍历为例，在遍历左子树之前，以中序遍历为例，在遍历左子树之前，先把根结点入栈，当左子树遍历结束后，先把根结点入栈，当左子树遍历结束后，从栈中弹出并访问根结点，再遍历右子树。从栈中弹出并访问根结点，再遍历右子树。算法(sun f)执行过程第33页/共85页第
43、三十四页，共85页。2023/2/72023/2/73535void inorder(BiTree*T)void inorder(BiTree*T)SqStack*S;SqStack*S;BiTree*P=T;/PBiTree*P=T;/P为工作指针为工作指针InitStack(S);/*InitStack(S);/*顺序栈初始化顺序栈初始化*/*/while(P!=NULL|!Empty(S)while(P!=NULL|!Empty(S)if(P!=NULL)if(P!=NULL)Push(S,P);/*Push(S,P);/*根结点根结点(ji din)(ji din)入栈入栈*/*/P=
44、P-lchild;/*P=P-lchild;/*遍历左子树遍历左子树*/*/elseelse Pop(S,P);/*Pop(S,P);/*左子树遍历结束，出栈左子树遍历结束，出栈*/*/printf(%c,P-data);printf(%c,P-data);P=P-rchild;/*P=P-rchild;/*遍历右子树遍历右子树*/*/第34页/共85页第三十五页，共85页。2023/2/736&a&b&d&c栈的变化情况栈的变化情况输出输出(shch)序列为：序列为：dbac第35页/共85页第三十六页，共85页。2023/2/72023/2/737376.4.4 6.4.4 从遍历序列恢复
45、二叉树从遍历序列恢复二叉树可可以以由由DLRDLR和和LDRLDR的的遍遍历历序序列列可可以以唯唯一一地地确确定定一一棵棵二二叉叉树树，或或者者由由LRDLRD和和LDRLDR的的遍遍历序列可以唯一地确定一棵二叉树。历序列可以唯一地确定一棵二叉树。通通过过(tnggu)DLR(tnggu)DLR或或者者LRDLRD的的遍遍历历序序列列确确定定 二二 叉叉 树树 或或 子子 树树 的的 根根 结结 点点；通通 过过(tnggu)LDR(tnggu)LDR确定左、右子树的序列。确定左、右子树的序列。第36页/共85页第三十七页，共85页。2023/2/72023/2/73838例：例：由先序序列由
46、先序序列(xli)ABHFDECKG(xli)ABHFDECKG 和中序序列和中序序列(xli)HBDFAEKCG(xli)HBDFAEKCG 恢复二叉树的过程。恢复二叉树的过程。第37页/共85页第三十八页，共85页。2023/2/72023/2/739396.4.5 6.4.5 遍历算法的应用遍历算法的应用统计二叉树的叶子结点数统计二叉树的叶子结点数int count=0;int count=0;int countleaf(bitree*p)int countleaf(bitree*p)if(p!=NULL)if(p!=NULL)count=countleaf(plchild);count
47、=countleaf(plchild);/*/*对左子树上的叶子结点计数对左子树上的叶子结点计数(j sh)*/(j sh)*/if(plchild=NULL)&(prchild=NULL)if(plchild=NULL)&(prchild=NULL)count=count+1;count=count+1;count=countleaf(prchild);count=countleaf(prchild);/*/*对右子树上的叶子结点计数对右子树上的叶子结点计数(j sh)*/(j sh)*/return count;return count;请考虑如何统计度为请考虑如何统计度为1 1的结点数，
48、度为的结点数，度为2 2的结点数。的结点数。第38页/共85页第三十九页，共85页。2023/2/72023/2/740402.利用二叉树先序遍历计算(j sun)二叉树的深度3.int l=h=0;4.int treedepth(bitree*p,int l)5.if(p!=NULL)6.l+;7.if (lh)8.h=l;9.h=treedepth(plchild,l);/计算(j sun)左子树的深度10.h=treedepth(prchild,l);/计算(j sun)右子树的深度11.12.return h;13.第39页/共85页第四十页，共85页。2023/2/72023/2/7
49、41413.3.求二叉树结点个数求二叉树结点个数求二叉树结点个数求二叉树结点个数int Size(BiTree*T)int Size(BiTree*T)if(T=NULL)return(0);if(T=NULL)return(0);else return(1+Size(T-lchild)+Size(T-rchild);else return(1+Size(T-lchild)+Size(T-rchild);/二叉树的结点个数是根结点、左右二叉树的结点个数是根结点、左右二叉树的结点个数是根结点、左右二叉树的结点个数是根结点、左右(zuyu)(zuyu)子树结点个数之和子树结点个数之和子树结点个数之
50、和子树结点个数之和 交换左右交换左右交换左右交换左右(zuyu)(zuyu)子树子树子树子树void Exchange(BiTree*T)void Exchange(BiTree*T)BiTree*S;BiTree*S;if(T!=NULL)if(T!=NULL)S=T-lchild;S=T-lchild;T-lchild=T-rchild;T-lchild=T-rchild;T-rchild=S;T-rchild=S;Exchange(T-lchild);Exchange(T-lchild);Exchange(T-rchild);Exchange(T-rchild);第40页/共85页第四十