6章树和二叉树.

第六章树与二叉树学习导读树型结构（Tree）是一类重要的非线性数据结构。其中以树和二叉树最为常见，树是以分支关系定义的层次结构。人类社会的族谱和各种社会组织机构都可用树来形象表示。编译程序中，可用树来表示源程序的语法结构。数据库系统中，树型结构也是信息的重要组织形式之一。本章重点讨论二叉树的存储结构及其各种操作，并研究树和森林与二叉树的转换关系，最后介绍一个典型的应用例子：哈夫曼树和哈夫曼编码。1.树的定义和基本术语2.二叉树3.遍历二叉树和线索二叉树4.树与森林5.赫夫曼树及其应用6学时6.1树的定义和基本术语1、树(Tree)的定义树是n（n≥0）个结点的有限集。在任意一棵非空树中：（1）有且仅有一个特殊的称为根(Root)的结点；（2）当n＞1时，其余结点可分成m（m＞0）个互不相交的有限集T1,T2,…,Tm，其中每一个集合本身又是一棵树，并且称为根的子树（SubTree）。如图6.1：A为根结点;（B，E，F）、（C，G，H，J，K，L，M）、（D，I）分别为根结点A的三棵子树。B，C，D分别为三棵子树的根结点。显然这是一个递归定义。图6.1树的示意图ABCDEFGHIJKLMRootABCDEFGHIJKLMRoot上述树的定义加上树的一组基本操作构成抽象数据类型树的定义:ADTTree{数据对象D:D是具有相同特性的数据对象的集合。数据关系R:若D为空集，则称为空树；若D仅含一个数据元素，则R为空集，否则R={H}，H是如下二元关系：⑴在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；⑵若D-{root}≠Φ，则存在D-{root}的一个划分D1，D2，…，Dm（m＞0），对任意j≠k（1≤j，k≤m）有Dj∩Dk=Φ，且对任意的i（1≤i≤m），唯一存在数据元素xi∈Di，有＜root，xi＞∈H；⑶对应于D-{root}的划分，H-{＜root，x1＞，…，＜root，xm＞}有唯一的一个划分H1，H2，…，Hm（m＞0），对任意j≠k（1≤j，k≤m）有Hj∩Hk=Φ，且对任意的i（1≤i≤m），Hi是Di上的二元关系，（Di，{Hi}）是一棵符合本定义的树，称为根root的子树。基本操作P：15个。P119}ADTTreeABCDEFGHIJKLMRoot(A(B(E,F(I,J)),C,D(G,H)))第一层第二层第三层第四层高度=4ABCDEGHIFJJIHGFEDCBAABEFIJCDGHE广义表表示法树形表示法嵌套集合表示法凹入表表示法树的各种表示法IJ2、树中结点的度(Degree)与树的度树中每个结点的分枝数称为该结点的度。例如图6.1中根结点A的度为3。B的度为2。G的度为4。而E，F，H，I，J，K，L，M的度全为零。树的度是树中结点的最大度数。所以图6.1的度为4。在实际应用中我们称度为零的结点为叶子(Leaf)结点，称度不为零的结点为分枝结点。如图6.1中E，F，H，I，J，K，L，M都是叶子结点，B，C，D，G都是分枝结点。从树中我们知道度为4的树中结点的度有0，1，2，3，4五种。因而可推知度为m的树中结点的度有m+1种。ABCDEFGHIJKLMRoot3、孩子(Child)结点与双亲(Parent)结点树中结点的子树的根结点称为该结点的孩子结点。相反，称该结点为孩子结点的双亲。例如图6.1中，B，C，D是根结点A的三个孩子结点。A为B，C，D的双亲。而，B，C，D三个结点又互称为兄弟(Sibling)结点（它们具有同一个双亲）。而E，F，G，H，I称为堂兄弟（它们的双亲称为兄弟结点）。祖先结点是从根结点到达某结点所经过分枝上的所有结点通称为该结点的祖先。例如A，C，G为结点J，K，L，M的祖先。子孙结点以某结点为根的子树中的任一结点都称为该结点的子孙。例如G，H，J，K，L，M都是C的子孙。ABCDEFGHIJKLM图6.1树的示意图ABCDJKLM4、树中结点的层数(Level)从根结点开始，根为一层结点，其孩子结点为二层结点依次类推，叶子结点为最下层结点。例如:右图示。这种分层的好处是树中结点的最大层数称为该树的高度（深度）。所以右图（用黑数字）所示树的高度（深度）为4。实际应用中树也可以以根为0层结点开始，此时，结点的层数为从根到达该结点的路径长度。如果，知道树中每层结点的个数，便可计算出对树中所有结点查找一遍所花费的总代价。使用哪种方式用户可根据系统需要进行选择。0……………………..11…………22…E.FGHI…33…….….4Root5、森林（Forest)是m(m=0)棵互不相交的树的集合（可以看成是把一棵树的根结点去掉，所得到的子树构成森林）。例如图6.2为图6.1去掉根结点A，以其三个孩子结点B，C，D为根的三棵子树构成的森林。6、有序树与无序树如果树中每个结点的孩子结点规定从左到右是有次序的（不许随意改动）那么，称该树为有序树。否则称为无序树。图6.3为相同的无序树，不同的有序树。BCDEFGHIJKLM图6.2森林AABCCBBBACCA图6.3就逻辑结构而言，任何一棵树都是一个二元组Tree=(Root,F),其中：Root是数据元素，称为树的根结点;F是m(m=0)棵树的森林,F=(T1,T2,…Tm),其中Ti=(ri,Fi)称为根root的第i棵子树;当M!=0时，在树根和其子树森林之间存在下列关系：RF={Root,ri|i=1,2,…m,m0}这个定义将有助于得到森林和树与二叉树之间转换的递归定义。6.2二叉树（BinaryTree)6.2.1二叉树的定义二叉树是每个结点至多有两个孩子结点的一种树。其中两个孩子结点分别被称为左孩子结点和右孩子结点。而以左孩子结点为根的子树称为左子树，以右孩子结点为根的子树称为右子树。另外，二叉树是有序树，其左右孩子的次序不能任意颠倒。P121-122二叉树的五种基本形态如下：只有根只有右子树有左右子树空二叉树只有左子树6.2.2二叉树的性质性质1在二叉树的第i层上至多有2个结点（i≥1）。利用归纳法容易证明该性质。i=1时，只有一个根结点。2=2=1是正确的。现假设对所有的j，1≤j＜i，命题成立，第j层上至多有2个结点。那么可以证明j=i时命题也成立。由归纳假设：第i-1层上至多有2个结点。由于二叉树的每个结点的度至多为2，故在第i层上的最大结点数为第i-1层的最大结点数的2倍，即2*2=2。性质2深度为K的二叉树至多有2-1个结点（k≥1）。由性质1可见，深度为K的二叉树的最多结点数∑（第i层上的最大结点数）=∑2=2-1=1+2+4+8+……+2i-1i-10j-1i-2i-2i-1kki=1ki=1i-1kK-1性质3对任何一棵二叉树T，如果其终端（即叶子）结点数为n0，度为2的结点数为n2，则n0=n2+1。证明：设n1为二叉树中度为1的结点数。所以二叉树结点的总个数为n=n0+n1+n2（6-1）又设B为二叉树的分枝总数，则B=n-1。又有B=n1+2n2。于是得n-1=n1+2n2整理得n=n1+2n2+1（6-2）把（6-1）代入（6-2）得n0+n1+n2=n1+2n2+1整理得n0=n2+1结果得证。满二叉树一棵深度为K且含有2-1个结点的二叉树称为满二叉树。这种树的特点是每一层上的结点个数都是最大结点数。如图6.5所示。对于一棵满二叉树，从根结点向下，同层从左到右进行连续编号又可引出完全二叉树的定义。完全二叉树深度为K，具有N个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至N的结点完全一一对应（即结点的编号与位置都相同）时，称该二叉树为完全二叉树。如图6.6。图6.5满二叉树图6.6完全二叉树1234568910111223456789101112131415117k1上面的两棵二叉树都不是完全二叉树。性质4具有n个结点的完全二叉树的深度为K=logn+1。证明：假设深度为K，则根据性质2和完全二叉树的定义有2-1＜n≤2-1或2≤n＜2于是K-1≤logn〈K，因为K是整数，所以K=logn+12345671234567789K-1kK-1k222性质5如果一棵有n个结点的完全二叉树（其深度为logn+1）的结点按层编号，则对任一结点i（1≤i≤n），有1)如果i=1,则结点i是二叉树的根，无双亲；如果i1,则其双亲PARENT(i)结点是i/22)如果2in，则结点i无左孩子结点；否则其左孩子结点LCHILD（i）的编号为2i。3）如果2i+1n，则结点i无右孩子结点；否则其右孩子结点RCHILD（i）的编号为2i+1。i/2ii+12i2i+12i+22i+32思考题1、一棵完全二叉树中的某个结点，如果没有左孩子结点，则其一定没有右孩子。这种说法正确吗？2、具有N个结点的一棵完全二叉树中，编号最小的叶子结点的编号是多少？3、高度为K的一棵完全二叉树中，结点的总个数最多是多少？最少是多少？4、设一棵满二叉树中，结点的总个数为20—40间的一个素数，问满二叉树中共有多少个叶子结点？5、一棵完全二叉树中结点的总个数是一个偶数，问该完全二叉树中度为一的结点数是多少？6、设一棵完全二叉树中结点I的堂兄弟结点的编号是2i+3，问该堂兄弟结点的双亲结点编号是多少？6.2.3二叉树的存储1、二叉树的顺序存储对于一棵高度为K的完全二叉树或满二叉树，可以直接用顺序方式存储。如图6.7示。#defineMAX_TREE_SIZE100（最大结点数）TElemTypeSqBiTree[MAX_TREE_SIZE]；（0号存储根）序号地址图6.7完全二叉树的顺序存储1a2b3c4d5e6f7ghijkl89101112abcdefghijkl12345678910111201234567891011bt一般二叉树的顺序存储右图为一棵二叉树，如果要用顺序存储的方式进行存储，那么，必须对树中结点按照完全二叉树（或满二叉树）的规则进行顺序编号。才可以实现顺序存储。从图6.8中可以看出对图6.8一般二叉树二叉树用顺序存储空间利用率低。同学们可以考虑图6.9所示的一般二叉树用顺序存储计算机应分配多少存储单元？实际应用多少个单元？图6.9一般二叉树a2bc35d10e11f1123456789101112abc0d0000ef1A2B3C6D7E14F15G2、二叉树的链式存储结构由二叉树的定义得知，二叉树的结点有一个数据元素和分别指示其左、右孩子的两个分枝构成，所以表示二叉树的链表中的结点至少应含有三个域：数据域和左、右孩子指针域。如图6.10示。在实际工作中有时需要查找结点的双亲，为此在结点中还要增加一个指向其双亲结点的指针域。如图6.11示.图6.10含有两个指针域图6.11含有三个指针域datalchildrchildlchilddatarchildlchilddataparentrchildABCDEFA∧BCD∧E∧∧F∧∧∧A∧∧B∧C∧D∧E∧∧F∧//----------二叉树的二叉链表存储表示----------typedefstructBiTNode{P127TElemTypedata;structBiTNode*lchild,*rchild;//}BiTNode,*BiTree;//----------地区基本操作的函数原型说明（部分）----------StatusCreateBiTree(BiTree&T);//按先序次序输入二叉树结点的值，空格表示空树，构造二叉链表的二叉树TStatusPreOrderTraversa(BiTreeT,Status(*Visit)(TElemTypee));//先序遍历二叉树T，Visit是对结点操作的应用函数StatusInOrderTraversa(BiTreeT,Status(*Visit)(TElemTypee));//中序遍历二叉树T，Visit是对结点操作的应用函数StatusPostOrderTraversa(BiTreeT,Status(*Visit)(TElem