《数据结构 第6章 树和二叉树.ppt》由会员分享，可在线阅读，更多相关《数据结构 第6章 树和二叉树.ppt（105页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第第6章章 树和二叉树树和二叉树6.1 6.1 树的定义和基本概念树的定义和基本概念6.2 6.2 二叉树二叉树 6.2.1 6.2.1 二叉树的定义和基本术语二叉树的定义和基本术语 6.2.2 6.2.2 二叉树的性质二叉树的性质 6.2.3 6.2.3 二叉树的存储结构二叉树的存储结构6.3 6.3 遍历二叉树遍历二叉树 6.3.1 6.3.1 遍历二叉树遍历二叉树 6.3.2 6.3.2 线索二叉树线索二叉树 6.4 6.4 树和森林树和森林 6.4.1 6.4.1 树的存储结构树的存储结构 6.4.2 6.4.2 森林与二叉树的转换森林与二叉树的转换 6.5 6.5 哈夫曼树及其应用哈
2、夫曼树及其应用 树型结构是一类重要的非线性结构。树型结构树型结构是一类重要的非线性结构。树型结构是结点之间有分支，并且具有层次关系的结构，它是结点之间有分支，并且具有层次关系的结构，它非常类似于自然界中的树。树结构在客观世界是大非常类似于自然界中的树。树结构在客观世界是大量存在的，例如家谱、行政组织机构都可用树形象量存在的，例如家谱、行政组织机构都可用树形象地表示。树在计算机领域中也有着广泛的应用，例地表示。树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；在分析算法在数据库系统中，可用
3、树来组织信息；在分析算法的行为时，可用树来描述其执行过程。等等。的行为时，可用树来描述其执行过程。等等。6.1 6.1 树的定义和基本操作树的定义和基本操作 一树的定义一树的定义 定义：树定义：树(Tree)(Tree)是是n(n=0)n(n=0)个结点的有限集个结点的有限集T T，T T为为空时称为空树，否则它满足如下两个条件：空时称为空树，否则它满足如下两个条件：（1 1）有且仅有一个特定的称为根）有且仅有一个特定的称为根(Root)(Root)的结点；的结点；（2 2）其余的结点可分为）其余的结点可分为m(m=0)m(m=0)个互不相交的子集个互不相交的子集T T1 1,T,T2 2,T
4、,T3 3TTm m，其中每个子集又是一棵树，并称其为，其中每个子集又是一棵树，并称其为子树子树(Subtree)(Subtree)。每棵子树的根结点有且仅有一个直每棵子树的根结点有且仅有一个直接前驱，但可以有接前驱，但可以有0个或多个直接后继。个或多个直接后继。由由此此可可知知，树树的的定定义义是是一一个个递递归归的的定定义义，即即树树的定义中又用到了树的概念的定义中又用到了树的概念。在图在图6-1(c)6-1(c)中，树的根结点为中，树的根结点为A A，该树还可以分为三个互，该树还可以分为三个互不相交子集不相交子集T T0 0，T T1 1，T T2 2，具体请参见图，具体请参见图6-26
5、-2，其中，其中T T0 0=B=B，E E，F F，J J，K K，LL，T T1 1=C=C，GG，T T2 2=D=D，H H，I I，MM，其中的，其中的T T0 0，T T1 1，T T2 2都是树，称为图都是树，称为图6-16-1（C C）中树的子树，而）中树的子树，而T T0 0，T T1 1，T T2 2又可以又可以分解成若干棵不相交子树。如分解成若干棵不相交子树。如T T0 0可以分解成可以分解成T T0000，T T0101两个不相两个不相交子集，交子集，T T0000=E=E，J J，K K，LL，T T0101=F=F，而，而T T0000又可以分为三个又可以分为三个不
6、相交子集不相交子集T T000000，T T001001，T T002002，其中，其中，T T000000=J=J，T T001001=K=K，T T002002=L=L。二树的逻辑结构描述二树的逻辑结构描述 一棵树的逻辑结构可以用二元组描述为：一棵树的逻辑结构可以用二元组描述为：tree=(k,R)k=ki 1in;n0,ki elemtype R=r其其中中，k是是具具有有相相同同特特性性的的数数据据元元素素的的集集合合;n为为树树中中结结点点个个数数，若若 n=0，则则为为一一棵棵空空树树，n 0时时称称为为一一棵棵非非空空树树，而而关关系系 r 应应满满足下列条件：足下列条件：（1）
7、有且仅有一个结点没有前驱）有且仅有一个结点没有前驱,称该结点为树根称该结点为树根;（2）除根结点以外）除根结点以外,其余每个结点有且仅有一个直接前驱其余每个结点有且仅有一个直接前驱;（3）树中每个结点可以有多个直接后继）树中每个结点可以有多个直接后继(孩子结点孩子结点)。例如，对图例如，对图6-1(c)的树结构的树结构,可以二元组表示为：可以二元组表示为：K=A，B，C，D，E，F，G，H，I，J，K，L，M R=r r=(A,B)，(A,C)，(A,D)，(B,E)，(B,F)，(C,G)，(D,H)，(D,I)，(E,J)，(E,K)，(E,L)，(H,M)四、四、基本术语基本术语1.结点
8、：结点：指树中的一个数据元素，一般用一个字母表示。2.度：度：一个结点包含子树的数目，称为该结点的度。树中结点度的最大值称为树的度。3.树树叶叶（叶叶子子）：度为0的结点，称为叶子结点或树叶，也叫终端结点。4.孩孩子子结结点点：若结点X有子树，则子树的根结点为X的孩子结点，也称为孩子，儿子，子女等。如图6-1（c）中A的孩子为B，C，D。5.双亲结点：双亲结点：若结点X有子女Y，则X为Y的双亲结点。6.祖祖先先结结点点：从根结点到该结点所经过分枝上的所有结点为该结点的祖先，如图6-1（c）中M的祖先有A，D，H。7.子孙结点：子孙结点：某一结点的子女及子女的子女都为该结点子孙。8.兄弟结点：兄
9、弟结点：具有同一个双亲的结点，称为兄弟结点。9.9.分枝结点：分枝结点：除叶子结点外的所有结点，为分枝结点，也叫非终端结点。1010层层数数：根结点的层数为1，其它结点的层数为从根结点到该结点所经过的分支数目再加1。11.11.树树的的高高度度（深深度度）：树中结点所处的最大层数称为树的高度，如空树的高度为0，只有一个根结点的树高度为1。12.12.有有序序树树 ：若一棵树中所有子树从左到右的排序是有顺序的，不能颠倒次序。称该树为有序树。13.13.无无序序树树：若一棵树中所有子树的次序无关紧要，则称为无序树。1414森森林林（树树林林）：若干棵互不相交的树组成的集合为森林。一棵树可以看成是一
10、个特殊的森林。五树的基本运算五树的基本运算(1)inittree(T)(1)inittree(T)初始化树T。(2)root(T)(2)root(T)求树T的根结点。(3)parent(T,x)(3)parent(T,x)求树T中，值为x的结点的双亲。(4)child(T,x,i)(4)child(T,x,i)求树T中，值为x的结点的第i个孩子。(5)addchild(y,i,x)(5)addchild(y,i,x)把值为x的结点作为值为y的结点的第i个孩子插入到树中。(6)delchild(x,i)(6)delchild(x,i)删除值为x的结点的第i个孩子。(7)traverse(T)(7
11、)traverse(T)遍历或访问树T。树的存储结构树的存储结构 在计算机中，树的存储通常采用顺序存储结构和链式存储结构，但无论采用何种存储方式，都要求存储结构不但能存储各结点本身的数据信息，还要能唯一地反映树中各结点之间的逻辑关系 1.双亲结点数组表示法#define Maxnode 100 /*树中结点的最大个数*/typedef struct elemtype data；int parent；NodeType；NodeType TMaxnode；0 0A A-1-11 1B B0 02 2C C0 03 3D D1 14 4E E1 15 5F F1 16 6G G2 27 7H H2
12、28 8I I4 49 9J J4 4孩子表示法 一、多重链表法一、多重链表法 由于树中每个结点都有零个或多个孩子结点，因此，可以令每个结点包括一个结点信息域和多个指针域，每个指针域指向该结点的一个孩子结点，通过各个指针域值反映出树中各结点之间的逻辑关系。在这种表示法中，树中每个结点有多个指针域，形成了多条链表，所以这种方法又常称为多重链表法。在一棵树中，各结点的度数各异，因此结点的指针域个数的设置有两种方法：每个结点指针域的个数等于该结点的度数；每个结点指针域的个数等于树的度数。二、孩子链表表示法二、孩子链表表示法 为树的每个节点建立一个孩子链表。孩子链表表示法是将树按图5.3所示的形式存储
13、。其主体是一个与结点个数一样大小的一维数组，数组的每一个元素有两个域组成，一个域用来存放结点信息，另一个用来存放指针，该指针指向由该结点孩子组成的单链表的首位置。单链表的结构也由两个域组成，一个存放孩子结点在一维数组中的序号，另一个是指针域，指向下一个孩子。这种存储表示可描述为：#define Maxnode 100 /*树中结点的最大个数*/typedef struct int childcode；struct ChildNode*nextchild；ChildNode typedef struct elemtype data；ChildNode*firstchild；NodeType；No
14、deType tMaxnode；双亲孩子表示法双亲孩子表示法双亲表示法仍将各结点的孩子结点分别组成单链表，同时用一维数组顺序存储树中的各结点，数组元素除了包括结点本身的信息和该结点的孩子结点链表的头指针之外，还增设一个域，存储该结点双亲结点在数组中的序号的树 孩子兄弟表示法 在树中，每个结点除其信息域外，再增加两个分别指向该结点的第一个孩子结点和下一个兄弟结点的指针。在这种存储结构下，树中结点的存储表示可描述为：typedef struct TreeNode elemtype data；struct TreeNode *fch，*nsib；NodeType；6.2 6.2 二叉树二叉树 二叉树
15、在树结构的应用中起着非常重要的作用，二叉树在树结构的应用中起着非常重要的作用，因为对二叉树的许多操作算法简单，而任何树都可以因为对二叉树的许多操作算法简单，而任何树都可以与二叉树相互转换，这样就解决了树的存储结构及其与二叉树相互转换，这样就解决了树的存储结构及其运算中存在的复杂性。运算中存在的复杂性。6.2.1 6.2.1 定义与基本操作定义与基本操作定义：二叉树是由定义：二叉树是由n(n=0)n(n=0)个结点的有限集合构成，此个结点的有限集合构成，此集合或者为空集，或者由一个根结点及两棵互不相交集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。的左右子树
16、组成，并且左右子树都是二叉树。这也是一个这也是一个递归递归定义。二叉树可以是空集合，定义。二叉树可以是空集合，二二叉树的特点是每个结点最多有两个孩子，或者说，在叉树的特点是每个结点最多有两个孩子，或者说，在二叉树中，不存在度大于二叉树中，不存在度大于2 2的结点，并且二叉树是有序的结点，并且二叉树是有序树。树。二叉树结点的子树要区分左子树和右子树，即使二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分，说明它是左子树，还是只有一棵子树也要进行区分，说明它是左子树，还是右子树。这是二叉树与树的最主要的差别。图右子树。这是二叉树与树的最主要的差别。图6.56.5列列出二叉树的出二叉
17、树的5 5种基本形态，图种基本形态，图6.5(C)6.5(C)和图和图6.56.5（d d）是）是不同的两棵二叉树。不同的两棵二叉树。(a)空二叉树AABABACB (b)根和空的左右子树 (c)根和左子树 (d)根和右子树 (e)根和左右子树图图6.5 6.5 二叉树的二叉树的5 5种形式种形式6.2.2 6.2.2 二叉树的性质二叉树的性质二叉树具有下列重要性质：二叉树具有下列重要性质：性质性质1 1：在二叉树的第在二叉树的第i i层上至多有层上至多有2 2i-1i-1个结点个结点(i1)(i1)。证明证明:用归纳法用归纳法v当当i=1,i=1,即第一层只有一个根结点即第一层只有一个根结点
18、,显然显然 2 2i-1i-1=2 20 0=1=1成立成立v假设假设i-1i-1时命题成立，即第时命题成立，即第i-1i-1层至多有层至多有2 2 i-2i-2个结点，个结点，则取则取i i 时，由于二叉树中每个结点至多有两个孩子，故时，由于二叉树中每个结点至多有两个孩子，故第第i i层上的结点数最多是第层上的结点数最多是第i-1i-1层上最多结点数的层上最多结点数的2 2倍，即倍，即取取i i时，该层上至多有时，该层上至多有22 22 i-2i-2=2=2 i-1i-1个结点。命题成立。个结点。命题成立。性质性质2.2.深度为深度为k k的二叉树至多有的二叉树至多有2 2k k-1-1个结
19、点个结点(k1)(k1)。（深度一定，二叉树的最大结点数也确定）（深度一定，二叉树的最大结点数也确定）证明：证明：深度为深度为k k的二叉树，若要求结点数最多，则的二叉树，若要求结点数最多，则必须每一层的结点数都为最多，由性质必须每一层的结点数都为最多，由性质1 1可知，最可知，最大结点数应为每一层最大结点数之和。既为大结点数应为每一层最大结点数之和。既为 2 20 0+2+21 1+2+2k-1k-1=2=2k k-1-1性质性质3.3.对任意一棵二叉树，如果叶子结点个数为对任意一棵二叉树，如果叶子结点个数为n n0 0，度为，度为2 2的的结点个数为结点个数为n n2 2，则有，则有n n
20、0 0=n=n2 2+1+1。证明：证明：设二叉树中度为设二叉树中度为1 1的结点数为的结点数为n n1 1，二叉树中总结点，二叉树中总结点数为数为N N，因为二叉树中所有结点均小于或等于，因为二叉树中所有结点均小于或等于2 2，所以有：所以有：N Nn n0 0n n1 1n n2 2 (6-1)(6-1)再看二叉树中的分支数，除根结点外，其余结点都有一个再看二叉树中的分支数，除根结点外，其余结点都有一个进入分支，设进入分支，设B B为二叉树中的分支总数，为二叉树中的分支总数，则有：则有：N NB B1 1。由于这些分支都是由度为由于这些分支都是由度为1 1和和2 2的结点射出的，所以有：的
21、结点射出的，所以有：B Bn1+2*n2 n1+2*n2 N NB B1 1n1n12n22n21 (6-2)1 (6-2)由式（由式（6 61 1）和（）和（6 62 2）得到：）得到：n0+n1+n2=n1+2*n2+1 n0+n1+n2=n1+2*n2+1 n0 n0n2n21 1 下面介绍两种特殊形态的二叉树：满二叉树和完全二叉树。下面介绍两种特殊形态的二叉树：满二叉树和完全二叉树。一棵深度为一棵深度为k k且由且由2 2k k-1-1个结点的二叉树称为个结点的二叉树称为满二叉树满二叉树。下图就是。下图就是一棵满二叉树。一棵满二叉树。对结点进行了顺序编号，如果深度为对结点进行了顺序编号
22、，如果深度为k k、由、由n n个结点的二叉树中个结点的二叉树中的结点能够与深度为的结点能够与深度为k k的顺序编号的满二叉树从的顺序编号的满二叉树从1 1到到n n标号的结点相标号的结点相对应，对应，则称这样的二叉树为则称这样的二叉树为完全二叉树完全二叉树。满二叉树是完全二叉树的。满二叉树是完全二叉树的特例。特例。完全二叉树的特点是：完全二叉树的特点是：（1)1)所有的叶结点都出现在第所有的叶结点都出现在第k k层或层或k k1 1层。层。（2 2）对任一结点，如果其右子树的最大层次为）对任一结点，如果其右子树的最大层次为L L，则其左子树的，则其左子树的最大层次为最大层次为L L或或L L
23、1 1。24536711231145891213671014151231145891267101234567123456 性质性质4 4：具有具有n个结点的完全二叉树高度为个结点的完全二叉树高度为 log2(n)+1 (注意注意 x 表示取不大于表示取不大于x的最大整数，读作对的最大整数，读作对x下取整，下取整，x 表示取不小于表示取不小于x的最小整数，读作对的最小整数，读作对x上取整。上取整。)证证明明：设设该该完完全全二二叉叉树树高高度度为为k，则则该该二二叉叉树树的的前前面面k-1层层为为满满二二叉叉树树，共共有有2k-1-1个个结结点点，而而该该二二叉叉树树具具有有k层层，第第k层层至
24、至少少至至少少有有1个个结结点点，最最多多有有2k-1个个结结点点。因因此此有有下下面面的的不不等等式式成成立立：（2k-1 1）+1 n（2k-1-1）+2k-1，即有，即有 2k-1n2k。于是于是 k-1 log2nk，由于，由于k是整数，则是整数，则k=log2 n+1证毕。证毕。性质性质5 5：如果对一棵有如果对一棵有n n个结点的完全二叉树的结点按层序编号个结点的完全二叉树的结点按层序编号（从第（从第1 1层到第层到第 loglog2 2n n +1+1层，每层从左到右按顺序编号）层，每层从左到右按顺序编号）,则对则对任一结点任一结点i i（1=i=n),1=i1i1，则其双亲是结
25、点则其双亲是结点 i/2i/2 。（2 2）如果）如果2in2in，则结点，则结点i i为叶子结点，无左孩子；否则，其为叶子结点，无左孩子；否则，其左孩子是结点左孩子是结点2i2i。（3 3）如果）如果2i2i1n1n，则结点，则结点i i无右孩子；否则，其右孩子是结无右孩子；否则，其右孩子是结点点2i2i1 1。证证此性质可采用数学归纳法证明。此性质可采用数学归纳法证明。因因为为1 1与与2 2、3 3是是相相对对应应的的，所所以以只只需需证证明明2 2和和3 3，而而且且在在此此只只需需讨讨论论有左孩子（有左孩子（2in2in）和有右孩子（）和有右孩子（2i+1n2i+1n）的情况。）的情
26、况。当当 i i1 1时时（i i是是根根），根根据据结结点点编编号号方方法法可可知知，根根的的左左、右右孩孩子子编号分别是编号分别是2 2和和3 3，结论成立。，结论成立。假定假定i-1i-1时结论成立，即结点时结论成立，即结点i-1i-1的左右孩子编号满足：的左右孩子编号满足：lchild lchild（i-1i-1）=2=2（i-1i-1）rchild rchild（i-1i-1）=2=2（i-1i-1）+1+1观观察察图图5.85.8知知，结结点点i i或或者者与与结结点点i-1i-1同同层层且且紧紧靠靠其其右右，或或者者结结点点i-i-1 1在在某某层层最最右右端端，而而结结点点i
27、i在在其其下下一一层层最最左左端端。但但是是，无无论论如如何何，结结点点i i的的左左、右右孩孩子子的的编编号号都都是是紧紧接接着着结结点点i-1i-1的的右右孩孩子子的的编编号号，故：故：lchild lchild（i i）=rchild=rchild（i-1i-1）+1=2i+1=2i rchild rchild（i i）=lchild=lchild（i i）+1=2i+1+1=2i+1 故命题成立。故命题成立。根据完全二叉树的结构和编号规则，在根据完全二叉树的结构和编号规则，在i i的左孩的左孩子前面的两个结点是结点子前面的两个结点是结点i-1i-1的左、右孩子，假设有：的左、右孩子，假
28、设有：结点结点i-1i-1的左孩子为的左孩子为2(i-1)2(i-1)，右孩子为，右孩子为2(i-1)+12(i-1)+1。2i-12(i-1)i2i+12i.i与 i+1同层.2i-12(i-1)i2i+12i.i与 i+1不同层i-1i-1 i i的左孩子应为的左孩子应为2i2i如果如果 2i 2in,n,则编号为则编号为2i2i的结点不存在的结点不存在,即即i i无左孩子无左孩子 而而i i的右孩子应为的右孩子应为2i+12i+1如果如果 2i+1 2i+1n,n,则编号为则编号为2i+12i+1的结点不存在的结点不存在,即即i i无右孩子无右孩子（2 2）和（）和（3 3）得证）得证.
29、最后证明最后证明:(1)i=1:(1)i=1时，结点时，结点i i是树的根；是树的根；否则否则(i(i1)1)，结点，结点i i的双亲为结点的双亲为结点i/2i/2 当当i=1i=1时时,显然根结点无双亲；显然根结点无双亲；当当i i1 1时，结点时，结点i i可能是其双亲可能是其双亲x x的左孩子，也可能是右孩子，若的左孩子，也可能是右孩子，若是左孩子，由（是左孩子，由（3 3）知，）知，x x的左孩子应为的左孩子应为2x2x，即，即2x=i2x=i，x=i/2x=i/2若是右孩子，由（若是右孩子，由（3 3）知，）知，x x的右孩子应为的右孩子应为2x+12x+1，即，即2x+1=i2x+
30、1=i，x=(i-1)/2x=(i-1)/2故故 i i的双亲为的双亲为i/2i/2 证毕证毕性质性质6.6.含有含有n n个结点的二叉链表中，有个结点的二叉链表中，有n+1n+1个空链域。个空链域。证明：空链域数证明：空链域数=2n=2n0 0+n+n1 1 因为因为 n=n n=n0 0+n+n1 1+n+n2 2 (1)(1)又有又有 n n0 0=n=n2 2+1 +1 即即-1=n-1=n2 2-n-n0 0 (2)(2)（1 1）-（2 2）得）得 n+1=2n n+1=2n0 0+n+n1 1 故空链域数故空链域数=n+1=n+16.2.3 6.2.3 二叉树的存储结构二叉树的存
31、储结构一一.顺序存储结构顺序存储结构 它是用一组连续的存储单元存储二叉树的数据元素。它是用一组连续的存储单元存储二叉树的数据元素。因此，必须把二叉树的所有结点安排成为一个恰当的序因此，必须把二叉树的所有结点安排成为一个恰当的序列，结点在这个序列中的相互位置能反映出结点之间的列，结点在这个序列中的相互位置能反映出结点之间的逻辑关系。通常是按照二叉树结点逻辑关系。通常是按照二叉树结点从上至下、从左到右从上至下、从左到右的顺序存储，但这样结点在存储位置上的前驱后继关系的顺序存储，但这样结点在存储位置上的前驱后继关系并不一定就是它们在逻辑上的邻接关系，只有通过一些并不一定就是它们在逻辑上的邻接关系，只
32、有通过一些方法确定某结点在逻辑上的前驱结点和后继结点，这种方法确定某结点在逻辑上的前驱结点和后继结点，这种存储才有意义。因此，依据二叉树的性质，完全二叉树存储才有意义。因此，依据二叉树的性质，完全二叉树和满二叉树采用顺序存储比较合适，树中结点的序号可和满二叉树采用顺序存储比较合适，树中结点的序号可以唯一地反映出结点之间的逻辑关系，这样既能够最大以唯一地反映出结点之间的逻辑关系，这样既能够最大可能地节省存储空间，又可以利用数组元素的下标值确可能地节省存储空间，又可以利用数组元素的下标值确定结点在二叉树中的位置，以及结点之间的关系。定结点在二叉树中的位置，以及结点之间的关系。abcdefghijk
33、l 1 2 3 4 5 6 7 8 9 10 11 12完全二叉树完全二叉树abcdefghijkl bt3的双亲为的双亲为3/23/2=1，即在即在b t1中；中；其左孩子在其左孩子在bt2i=bt6中；中；其右孩子在其右孩子在bt2i+1=bt7中。中。D 二叉树二叉树CGFEBA1 2 3 4 5 6 7 8 9 10 11 A B C D E 0 0 0 0 F G 一般二叉树也按完全二叉树形式存储一般二叉树也按完全二叉树形式存储,只有增添一只有增添一些并不存在的空结点（用些并不存在的空结点（用0 0表示），使之成为一棵完全表示），使之成为一棵完全二叉树的形式，然后再用一维数组顺序存储
34、。二叉树的形式，然后再用一维数组顺序存储。这种存储结构适合于完全二叉树，既不浪费存这种存储结构适合于完全二叉树，既不浪费存储空间，又能很快确定结点的存放位置、以及结点储空间，又能很快确定结点的存放位置、以及结点的双亲和左右孩子的存放位置，但对一般二叉树，的双亲和左右孩子的存放位置，但对一般二叉树，可能造成存储空间的浪费。可能造成存储空间的浪费。例如，深度为例如，深度为k k，且只有，且只有k k个结点的右单枝树个结点的右单枝树(每个非叶结点只有右孩子每个非叶结点只有右孩子)，需，需2 2k k-1-1个单元，即有个单元，即有2 2k k-1-k-1-k个单元被浪费。个单元被浪费。1k二、链式存
35、储结构二、链式存储结构 所谓二叉树的链式存储结构是指，用链表来表示一棵二叉树，所谓二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示着元素的逻辑关系。通常有下面两种形式。即用链来指示着元素的逻辑关系。通常有下面两种形式。（1 1）二叉链表存储）二叉链表存储 链表中每个结点由三个域组成，除了数据域外，还有两个链表中每个结点由三个域组成，除了数据域外，还有两个指针域，分别用来给出该结点左孩子和右孩子所在的链结点的存储指针域，分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。地址。ABCDEFG AB C D E F Glchild data rchild 在n个结点的二叉链表中，
36、有n+1个空指针域（2 2）三叉链表存储）三叉链表存储 每个结点由四个域组成，其中，每个结点由四个域组成，其中，datadata、lchildlchild以及以及rchildrchild三三个域的意义同二叉链表结构；个域的意义同二叉链表结构；parentparent域为指向该结点双亲结点的指域为指向该结点双亲结点的指针。这种存储结构既便于查找孩子结点，又便于查找双亲结点；但针。这种存储结构既便于查找孩子结点，又便于查找双亲结点；但是相对于二叉链表存储结构而言，它增加了空间开销。是相对于二叉链表存储结构而言，它增加了空间开销。lchild data parent rchild A B C D E
37、 F G三、二叉链表存储的描述三、二叉链表存储的描述typedef struct BiTNodetypedef struct BiTNode elemtype data elemtype data；struct BiTNode*lchild struct BiTNode*lchild，*rchild*rchild；Bitnode Bitnode，*Bitree*Bitree；即即将将BitreeBitree定定义义为为指指向向二二叉叉链链表表结结点点结结构构的的指指针针类类型型。尽尽管管在在二二叉叉链链表表中中无无法法由由结结点点直直接接找找到到其其双双亲亲，但但由由于于二二叉叉链链表表结结构
38、构灵灵活活，操操作作方方便便，对对于于一一般般情情况况的的二二叉叉树树，甚甚至至比比顺顺序序存存储储结结构构还还节节省省空空间间。因因此此，二二叉叉链链表表是是最最常常用用的的二二叉叉树树存存储储方方式式。后后面面所所涉涉及及到到的的二二叉叉树树的的存存储储结结构构不不加加特特别别说说明明的的都都是是指指二二叉叉链链表表结结构。构。Initiate（bt）建立一棵空二叉树。Create（x，lbt，rbt）生成一棵以x为根结点的数据域信息，以二叉树lbt和rbt为左子树和右子树的二叉树。Insertlchild（bt，x，parent）将数据域信息为x的结点插入到二叉树bt中作为结点paren
39、t的左孩子结点。如果结点parent原来有左孩子结点，则将结点parent原来的左孩子结点作为结点x的左孩子结点。Insertrchild（bt，x，parent）将数据域信息为x的结点插入到二叉树bt中作为结点parent的右孩子结点。如果结点parent原来有右孩子结点，则将结点parent原来的右孩子结点作为结点x的右孩子结点。Deletelchild（bt，parent）在 二 叉 树 bt中 删 除 结 点 parent的 左 子 树。Deleterchild（bt，parent）在二叉树bt中删除结点parent的右子树。Search（bt，x）在二叉树bt中查找数据元素x。Tra
40、verse（bt）按某种方式遍历二叉树bt的全部结点。四、二叉树的四、二叉树的基本操作基本操作 五五 算法的实现算法的实现下面讨论基于二叉链表存储结构的上述操作的实现算法。1Initiate（bt）初始建立二叉树bt，并使bt指向头结点。在二叉树根结点前建立头结点，就如同在单链表前建立的头结点，可以方便后边的一些操作实现。Bitree Initiate（）/*初始化建立二叉树bt的头结点*/Bitree bt;if（bt=（Bitnode*）malloc（sizeof（Bitnode）=NULL）return 0；bt-lchild=NULL；bt-rchild=NULL；return bt；
41、2Create（x，lbt，rbt）建立一棵以x为根结点的数据域信息，以二叉树lbt和rbt为左右子树的二叉树。建立成功时返回所建二叉树结点的指针；建立失败时返回空指针。BiTree Create（elemtype x，Bitree lbt，Bitree rbt）/*生成一棵以x为根结点的数据域值以lbt和rbt为左右子树 的二叉树*/Bitree p；if（p=（Bitnode*）malloc（sizeof（Bitnode）=NULL）return NULL；p-data=x；p-lchild=lbt；p-rchild=rbt；return p；算法 5.23Insertlchild（bt，
42、x，parent）将数据域信息为x的结点插入到二叉树bt中作为结点parent的左孩子结点。如果结点parent原来有左孩子结点，则将结点parent原来的左孩子结点作为结点x的左孩子结点。BiTree Insertlchild（Bitree bt，elemtype x，Bitree parent）/*在二叉树bt的结点parent的左子树插入结点数据元素x */Bitree p；if（parent=NULL）printf（“n插入出错”）；return NULL；if（p=（BiTNode*）malloc（sizeof（BiTNode）=NULL）return NULL；p-data=x；p
43、-lchild=NULL；p-rchild=NULL；if（parent-lchild=NULL）parent-lchild=p；else p-lchild=parent-lchild；parent-lchild=p；return bt；5Deletelchild（bt，parent）在二叉树bt中删除结点parent的左子树。当parent或parent的左孩子结点为空时删除失败。删除成功时返回根结点指针；删除失败时返回空指针。Bitree Deletelchild（Bitree bt，Bitree parent）/*在二叉树bt中删除结点parent的左子树*/Bitree p；if（pa
44、rent=NULL|parent-lchild=NULL）printf（“n删除出错”）；return NULL p=parent-lchild；parent-lchild=NULL；free（p）；/*当p为非叶子结点时，这样删除仅释放了所删子树根结点的空间，*/*若要删除子树分支中的结点，需用后面介绍的遍历操作来实现。*/return br；作业1.一棵深度为k的满二叉树的结点总数为2k-1，一棵深度为k的完全二叉树的结点总数的最小值为2k-1 最大值为2k-1 2.由a,b,c三个结点构成的二叉树，共有5种不同的结构。3.对于一个具有n个结点的二叉树，当它为一棵满二叉树时具有最小高度，即
45、为 log2(n)+1，当它为一棵单支树具有最大高度，即为n4.对于具有n个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为2n个，其中n-1个用于链接孩子结点，n+1个空闲着 6.3 6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树6.3.16.3.1遍历二叉树遍历二叉树 一、定义：一、定义：所所谓谓遍遍历历二二叉叉树树，就就是是遵遵从从某某种种次次序序，访访问问二二叉叉树树中中的的所所有结点，使得每个结点仅被访问一次。有结点，使得每个结点仅被访问一次。这这里里所所提提的的“访访问问”的的含含义义很很广广，可可以以是是查查询询、修修改改、输输出出某某元元素素的的值值，以以及及
46、对对元元素素作作某某种种运运算算等等等等。但但要要求求这这种种访访问问不不破破坏坏它它原原来来的的数数据据结结构构。遍遍历历一一个个线线性性结结构构很很简简单单，只只须须从从开开始始结结点点出出发发，顺顺序序扫扫描描每每个个结结点点即即可可。但但对对二二叉叉树树这这样样的的非非线线性性结结构构，每每个个结结点点可可能能有有两两个个结结点点，因因此此需需要要寻寻找找一一种种规规律律来系统访问树中的各结点。来系统访问树中的各结点。二、方法：二、方法：1、递归遍历：、递归遍历：v 由二叉树的定义是递归的，它是由三个基本单元组成，即根由二叉树的定义是递归的，它是由三个基本单元组成，即根结点、左子树和右
47、子树。因此，遍历一棵非空二叉树的问题可以结点、左子树和右子树。因此，遍历一棵非空二叉树的问题可以分解为三个子问题：访问根结点、遍历左子树、遍历右子树，只分解为三个子问题：访问根结点、遍历左子树、遍历右子树，只要依次遍历这三部分，就可以遍历整个二叉树。要依次遍历这三部分，就可以遍历整个二叉树。v 在任一给定结点上，可以按某种次序执行三个操作：访问结在任一给定结点上，可以按某种次序执行三个操作：访问结点本身，遍历该结点左子树，遍历该结点右子树。点本身，遍历该结点左子树，遍历该结点右子树。v 由于实际问题一般都是要求左子树较右子树先遍历，分别称由于实际问题一般都是要求左子树较右子树先遍历，分别称为先
48、序遍历（为先序遍历（先先访问根结点，再遍历左子树，再遍历右子树访问根结点，再遍历左子树，再遍历右子树）、中序遍历（中序遍历（先先遍历左子树，再访问根结点，再遍历右子树遍历左子树，再访问根结点，再遍历右子树）和后和后序遍历（先序遍历（先遍历左子树，再遍历右子树，最后访问根结点）遍历左子树，再遍历右子树，最后访问根结点）。v 令令L,R,DL,R,D分分别别代代表表二二叉叉树树的的左左子子树树、右右子子树树、根根结结点点，则则有有DLRDLR、LDRLDR、LRDLRD三种遍历规则。三种遍历规则。先序遍历二叉树先序遍历二叉树若二叉树非空，则：若二叉树非空，则：1 1）访问根结点）访问根结点 2)2
49、)先序遍历左子树先序遍历左子树 3 3）先序遍历右子树）先序遍历右子树ADBCD L RAD L RD L RBDCD L R先序遍历序列：先序遍历序列：A B D C主程序主程序Pre(T)返回返回pre(T R);返回返回pre(T R);ACBDTBvisite(B);pre(T L);BTAvisite(A);pre(T L);ATDvisite(D);pre(T L);DTCvisite(C);pre(T L);C返回T左是空返回左是空返回pre(T R);T左是空返回左是空返回T右是空返回右是空返回T左是空返回左是空返回T右是空返回右是空返回pre(T R);先序序列：A B D
50、Cvoid Preordervoid Preorder（Bint btBint bt）if if（bt=NULLbt=NULL）returnreturn；/*/*递递归归调调用的结束条件用的结束条件*/*/VisiteVisite（bt-databt-data）;/访问结点的数据域访问结点的数据域 PreorderPreorder（bt-lchildbt-lchild）；/*/*先先序序 递归遍历递归遍历btbt的左子树的左子树*/*/PreorderPreorder（bt-rchildbt-rchild）；）；中序遍历二叉树中序遍历二叉树若二叉树非空，则：若二叉树非空，则：1 1）中序遍历左