第6章-树与二叉树.

第6章树和二叉树【学习目标】1．领会树和二叉树的类型定义，理解树和二叉树的结构差别。2．熟记二叉树的主要特性，并掌握它们的证明方法。3．熟练掌握二叉树的各种遍历算法，并能灵活运用遍历算法实现二叉树的其它操作。4．理解二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。5．熟练掌握二叉树和树的各种存储结构及其建立的算法。6．学会编写实现树的各种操作的算法。7．了解最优树的特性，掌握建立最优树和赫夫曼编码的方法。【重点和难点】二叉树和树的遍历及其应用是本章的学习重点，而编写实现二叉树和树的各种操作的递归算法也恰是本章的难点所在。【知识点】树的类型定义、二叉树的类型定义、二叉树的存储表示、二叉树的遍历以及其它操作的实现、线索二叉树、树和森林的存储表示、树和森林的遍历以及其它操作的实现、最优树和赫夫曼编码6.1树的类型定义树型结构是一类重要的非线性结构，树型结构广泛用于描述家族谱系以及其它社会组织结构。在计算机领域中，如编译程序中的语法结构和数据库中的信息组织也都需要借用树来描述。本章将讨论树和二叉树两种树型结构。例：祖父伯父父亲叔父堂兄堂姐自己堂弟侄儿家族谱系图可用如下关系表示：祖父，伯父，祖父，父亲，祖父，叔父，伯父，堂兄，伯父，堂姐，父亲，你，叔父，堂弟，堂兄，侄儿树(Tree)：包含n（n=0）个结点的有限集合。当n=0时称为空树；任意一棵非空树满足以下条件：1）有且仅有一个称为根（root）的结点。（无前趋）2）除根外，每个结点都有且仅有一个前驱。3）当n1时，其余结点可分为m(m0)个互不相交的有限集合T1,T2,…,Tm，其中每一集合本身又是一棵树，称为这个根结点的子树。ABCDEFG树的定义是采用递归方法。例如所示图为含13个数据元素的集合，其中，A为根，其余12个数据元素分为3个互不相交的子集T1={B,E,F,K,L}、T2={C,G}和T3={D,H,I,J,M}，每个子集都是一棵树，称为A的子树，它们的根结点都是A的后继。这是一个递归的定义，如在子树T1中，B是根，其余元素分为2个互不相交的子集T11={E}和T12={F,K,L}，每个子集构成一棵B的子树，子树中的根结点是B的后继，依次类推。换句话说，在这13个数据元素之间存在下列关系：R={A,B,A,C,A,D,B,E,B,F,C,G,D,H,D,I,D,J,F,K,F,L,J,M}。虽然图上的线条没有标上箭头，但实际上存在着有向关系。因此，树是一种层次分明的结构术语：结点：包含一个数据元素及若干指向其子树的分支结点的度：结点拥有的子树数叶子（终端结点）：度为0的结点分支结点（非终端结点）：度不为0的结点。除根之外的分支结点也称为内部结点。树的度：树内各结点的度的最大值ABCDEFGIJKH称根和子树根之间的连线为分支”,分支代表了树中结点的关系，是有方向的.ABCDEFGIJKH孩子：结点的子树的根称为该结点的孩子双亲：兄弟：同一双亲的孩子间互称兄弟祖先：从根到该结点所经分支上的所有结点子孙：以某结点为根的子树中的任一结点称为该结点的子孙层次：根为第一层，根的孩子为第二层。。。堂兄弟：双亲在同一层的结点互为堂兄弟树的深度（或高度）：树中结点的最大层次ABCDEFGIJKH有序树：树中各子树从左至右有次序，不能交换无序树：第一个孩子：有序树中，最左边的子树的根最后一个孩子：有序树中，最右边的子树的根森林：m(m=0)棵互不相交的树的集合树的另一定义：树是一个二元组Tree=(root,F)，root是数据元素，称为树的根。F是m(m0)棵树的森林。F=(T1,T2,...Tm)，其中Ti=(ri,Fi)称做根root的第i棵子树；当m0时，在树根和其子树之间存在关系：RF={root,ri|i=1,2,...,m,m0}ADTTree{数据对象：D是具有相同特性的数据元素的集合。数据关系：若D为空集，则称为空树；若D中仅含一个数据元素，则关系R为空集；否则R={H}，树的抽象数据类型的定义如下(1)在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；(2)当n1时，其余数据元素可分为m(m0)个互不相交的(非空)有限集T1,T2,…,Tm,其中每一个子集本身又是一棵符合本定义的树，称为根root的子树，每一棵子树的根xi都是根root的后继，即root,xiH,i=1,2,…,m。基本操作：inittree(&T);DestroyTree(&T);CreatTree(&T,definition);ClearTree(&T);TreeEmpty(T);TreeDepth(T);Root(T);Value(T,cur_e);Assign(T,cur_e,value);Parent(T,cur_e);Leftchild(T,cur_e);RightSibling(T,cur_e);InsertChild(&T,&p,i,c);DeleteChild(&T,&p,i);TraverseTree(T,Visit());}对无序树而言，第i棵子树的概念也仅对存储结构中子树的次序而言。树的表示方法ABDCEKLFGIJHMABCDELKFGHIMJ(A(B(E(K,L),F),C(G),D(H(M),I,J)))就结构中数据元素之间存在的关系可将二者作如下对照：其余结点均存在唯一的前驱(双亲)结点和多个后继(孩子)结点其余元素均存在唯一的前驱元素和唯一的后继元素存在多个没有后继的叶子存在唯一的没有后继的尾元素存在唯一的没有前驱的根结点存在唯一的没有前驱的首元素树结构线性结构线性结构是一个序列，元素之间存在的是一对一的关系，而树是一个层次结构，元素之间存在的是一对多的关系。树VS线性结构6.2二叉树B树、B+树、B*树、R树、KD树、二叉树、四叉树、八叉树……研究二叉树的意义？二叉树的结构相对简单，其运算也自然简单，便于初学者入门。由于多叉树可以借助一定的规则转换为二叉树，因此二叉树结构在应用中具有非常重要的地位。6.2.1二叉树的定义由n个结点的有限集合组成。这个有限集或者为空集，或者由一个根结点及两棵互不相交的分别称为左子树和右子树的二叉树组成。每个结点至多有二棵子树（不存在度2的结点）；子树有左右之分。6.2二叉树二叉树的抽象数据类型定义如下（P121）：ADTBinaryTree{数据对象：D是具有相同特性的数据元素的集合。数据关系：若D为空集，称BinaryTree为空二叉树；否则关系R={H}：(1)在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；(2)D中其余元素必可分为两个互不相交的子集L和R，每一个子集都是一棵符合本定义的二叉树，并分别为root的左子树和右子树。如果左子树L不空，则必存在一个根结点XL，它是root的左后继(root,XL∈H)，如果右子树R不空，则必存在一个根结点XR为root的右后继(root,XT∈H)基本操作：略,P121-123,基本同树的定义一样，但是注意操作中的左右之分二叉树的五种基本状态(a)空二叉树AABABACB(b)根和空的左右子树(c)根和左子树(d)根和右子树(e)根和左右子树在了解了树和二叉树的定以后，大家思考一下二叉树是不是等同于度为2的有序树？树VS二叉树例：画出具有3个结点的树和具有3个结点的二叉树的形态7.2二叉树的概念和性质二叉树和树是两种不同的树型结构，二叉树不等同于度为2的有序树。如果根结点只有一棵子树，那么对树而言，它就是一个独生子，无次序可分，但对二叉树而言，必须明确区分它是根的左子树还是根的右子树，两者将构成不同的二叉树。6.2.2二叉树的性质性质1：在二叉树的第i层上至多有2i-1个结点（i=1)归纳基：i=1时，只有一个根结点。显然2i-1=20=1是对的。归纳假设：设对所有的j(1≤ji)，命题成立，即第j层上至多有2j-1个结点。归纳证明：由归纳假设第i-1层上至多有2i-2个结点，又二叉树的每个结点的度至多为2，则第i层上的最大结点数为第i-1层上最大结点数的2倍，即2×2i-2=2i-1。证毕。性质2：深度为K的二叉树至多有2k-1个结点（k=1）证明：由特性一可推出，深度为k的二叉树上最大结点数为122111kkiikii层上的最大结点数＝第=a1*(1-qn)/(1-q)=1*(1-2k)/(1-2)性质3：对任何一棵二叉树T，若其终端结点数为n0，度为2的结点数为n2，则n0=n2+1由于二叉树中只有三种结点，假设n1为二叉树T中度为1的结点数，则二叉树中结点总数n为证明：再看二叉树中的分支数目。除了根结点外，其余结点都有一个分支进入，假设B为分支数，则B＝n1+2n2⑶从另一角度看，这些分支是由度为1或2的结点射出的，所以又有n=B+1。⑵推出：n0+n1+n2=n1+2n2+1得：n0=n2+1n=n0+n1+n2⑴性质4，5同下面得特殊二叉树有关两种特殊形态的二叉树：满二叉树：深度为K且有2k-1个结点的二叉树。即每一层上的结点数都是最大结点数。叶子结点的个数=分支结点数（含根）+1对满二叉树的结点进行连续编号，自上而下，自左至右。完全二叉树：按同一原则对所有有结点进行编号，若每一结点都与同深度的满二叉树的编号一一对应，则称为完全二叉树。显然一棵深度为h的完全二叉树中，前h-1层中的结点都是“满”的，且第h层的结点都集中在左边。满二叉树本身也是完全二叉树。1236745123645123564满二叉树完全二叉树二叉树给出下面各图得确切名称完全二叉树的特点：1）叶子结点只可能在层次最大的二层上出现2）对任一结点，若其右分支下的子孙的最大层次为L，则基左分支下的子孙的最大层次必为L或L+112345完全二叉树完全二叉树的两个重要特征性质4：具有n个结点完全二叉树的深度为：log2n+1证明：设深度为K，有：2k-1-1n=2k-1或2k-1=n2k对不等式取对数k-1=log2nk，且K必为整数，有K=log2n+1性质5：如果对一棵有n个结点的完全二叉树的结点按层序编号，则对任一结点i（1=i=n），有：1）若i=1，则i为根，无双亲。若i1，则parent(i)是结点i/22）若2in，则结点i无左孩子，为叶子结点。否则Lchild(i)是结点2i3）若2i+1n，则结点i无右孩子，否则Rchild(i)是结点2i+1123645[i/2]ii+12i2i+12(i+1)2i+3i+12(i+1)2i+3i2i2i+1先证明（2）（3），然后很明显可得到（1）使用归纳法，首先证明i=1时成立，然后假设第i个结点成立，只需证明第i+1个结点也成立即可。当i=1时，由完全二叉树的定义，其左孩子结点是2，若2n，即不存在结点2，此时结点i没有左孩子。结点i的右孩子也只能是3，若结点3不存在，即3n，此时结点i无右孩子。现在假设第i个结点成立，则有如果2i=n，则2i是i的左孩子，否则没有左孩子。如果2i+1=n，则2i+1是i的右孩子，否则无右孩子。那么对于第i+1个结点，有可能与i处于同一层，也有可能处于不同层。（如课本p125图6.5）当i和i+1处于不同层时，则i应处在i+1（假设第k+1层）所处层的上一层的最右边，i+1应在i所处层（应为k层）的下一层的最左边。因此，i的左右孩子应处在i+1所在层的最右边，而i+1的左右孩子应在k+2层的最左边，根据层次编号的原则，i的左右孩子与i+1的左右孩子编号应是连续的。由于i的右孩子的编号是2i+1，所以i+1的左右孩子应是2i+2,2i+3，若2(i+1)n,则i+1无左孩子，若2(i+1)+1n，则i+1无右孩子。若i和i+1处于相同层时，它们或是兄弟或是堂兄弟，因此它们的左右孩子一定都在下一层的相邻位置上。即i+1的左孩