5-树及二叉树

《5-树及二叉树》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1.树的定义和术语2.二叉树:定义、性质、存储3.二叉树的遍历4.二叉树遍历的迭代器类*5.中序穿线树6.最优二叉树及其应用7.树和森林第五章树及二叉树树和森林树：n>0个结点的集合，根+其余结点分为m>=0个集合，每一个集合本身又是一棵树（子树）结点的度：该结点的子树数目树的度：树中各结点度数的最大值叶子、父结点、儿子结点、兄弟结点祖先结点：从根结点到该结点的路径上所有结点层次、高度：根为1,依次往下数有序树：规定所有结点的儿子结点次序，否则为无序树森林：m>=0棵互不相交树的集合其它表示方法：1.(A(B(L,E),C(F),D(G(I),H))2.类似于

2、书籍的目录表示法。高度定义为层数或层数－1，都可以；本书定义为层数。ABCDEFGHIL高度为4、度为3的树树和森林ADT5.1:树的ADT数据及关系:具有相同数据类型的数据元素或结点的有限集合。树T的二元组形式为：T＝（D，R）其中D为树T中结点的集合，R为树中结点之间关系的集合。D＝{Root}∪DF其中，Root为树T的根结点，DF为树T的根Root的子树集合。R＝{，i＝1，2，…，m}其中，ri是树T的根结点Root的子树Ti的根结点。操作:Constructor：前提：已知根结点的数据元素之值。结果：创建一棵树。Getroot:前

3、提：已知一棵树。.结果：得到树的根结点。FirstChild：前提：已知树中的某一指定结点p。结果：得到结点p的第一个儿子结点。NextChild：前提：已知树中的某一指定结点p和它的一个儿子结点u。结果：得到结点p的儿子结点u的下一个兄弟结点v。例：结点总数为3时的所有二叉树的树的形状二叉树的定义空或有一个根，根有左子树、右子树；而左右子树本身又是二叉树。和树的区别：可为空左右子树有序，不可颠倒BCDEFL例：二叉树二叉树的性质性质1：在二叉树的第i层上至多有2i-1个结点BCDEFLA1层：结点个数21-1=20个2层：结点个数22-1=21个3层：结点个

4、数23-1=22个证：k=1时成立，设k=i-1时成立则当k=i时在二叉树的第i层上至多有2i-1-1*2=2i-1个结点性质2：高度为k的二叉树至多有2k-1个结点证：利用性质1，将第1层至第k层的最多的结点数进行相加：1+2+22+…………+2k-2+2k-1=2k-1性质3：二叉树的叶子结点数n0等于度为2的结点数n2+1证：设度为1的结点数为n1，树枝的总数为B则：B=n-1=n0+n1+n2-1又B=n1+2×n2；原命题得证。CEFLA完全二叉树BCDEFLAPSQRUBCDEFLAPSQRXUWV满二叉树:每层结点数最多完全二叉树:1、满二叉树2

5、、从满二叉树最底层从右向左依次去掉若干结点形成的性质4：具有n个结点的完全二叉树高度为log2n+1证：根据性质2和完全二叉树的定义：设其高度为k2k-1-1

6、n)。2：对任何一个编号为j的结点而言，它的父亲结点的的编号为j/2。根结点无父结点。证：对编号归纳121110987654321二叉树的顺序存储一般情况：ABCDEFGHILA1-1B92C53D6-1E-1-1F-1-1G87H-1-1I-1-1L-140123456789rightleftdata应用范围：适用于二叉树上的结点个数已知，或不支持动态存储分配的高级语言。二叉树的顺序存储特殊情况：完全二叉树A23B45C67D89E100F00G00H00I00L00012345678910rightleftdata应用范围：适用于完全二叉树，且结点个数已知

7、。DCGEFBAHILABCDEFGHI0123456789L二叉树的顺序存储特殊情况：若不是完全二叉树，许多数据场为空，不合算。如下例所示：考虑浪费空间最多的情况，是一种什么情况？浪费2^k-1–k个单元AB∧D∧∧∧HI0123456789DBAHI二叉树的链接存储仅定义结点的类型即可。结点之间的关系通过指针实现。ABCDEFGHILdataleftright标准形式：（二叉链表）广义标准形式：（三叉链表）dataleftrightParent二叉树的链接存储例：A∧B/∧∧∧∧∧∧CDEFGGFDCBAE二叉树的ADTtemplate

8、e>classBinaryTree;/