第6章树1

第六章树前面几章，我们讨论了线性结构，如线性表、栈、队列以及线性结构的扩充(多维数组和广义表)。但在系统软件和应用软件的设计中，很多情况下需要描述数据的层次关系。本章讨论一种非线性数据结构：树和二叉树(即层次结构)。它能对数据结构随机再组织，故称树为动态结构。本章涉及内容：树和二叉树的定义、运算、性质、存储结构、二叉树的遍历、线索化和树与二叉树之间的转换等问题，最后给出二叉树的一个典型应用——Huffman（哈夫曼）编码及译码。6.1树的基本概念例6-１IBMPCDOS中文件结构是一棵树，如图6.1：MFD(根节点)子目录A子目录B子目录A1子目录A2文件文件文件文件文件文件有向弧MFD,B等为关系叶节点分支节点树的基本概念例6-2编译系统中将表达式组织成一棵树，如a+b*(c-b)-e/f的树结构如图6.2：6.1.1树的定义及基本操作1．定义：树（Tree）是n（n≥0）个节点满足层次关系的有限集，当n=0时，称为空树，记为Φ；当n＞0时，称为非空树。对非空树T满足下列条件：（1）T有且仅有一个称为根（root）的节点；（2）T的其余节点可分为m(m≥0)个互不相交的有限集：T1，T2..，Tm,Ti(1≤i≤m)为根的子树(subtree)。显然，这是一个递归定义，即当子树Ti非空时，又要满足定义中的（1）和（2）。—abcdef/*—+树的定义树T可形式化描述，即：T＝（D，R）其中D，R分别为元素集和关系集，若D=φ，则树T为空树，否则有：D＝{root}∪DF,root∈datatype,为根元素,DF=根下各子树Ti的元素集：(m≥0)，且Di∩Dj=φ(不相交)，1≤i，j≤m，i≠j。root,riri是root的子树Ti之根,Ti=(Di,Ri)——递归；R=Di={ri}UDFi,1≤i≤m，m＞0；фm=0设树T：即：D={A}∪DF，DF=D1∪D2，D1={B}∪DF1，DF1=D11∪D12，D11={E}，D12={F}，D2={C},故D＝{A,B,C,E,F},而R={A,B,B,E,B,F,A,C}。UmiiD1ACBEF有向弧的箭头可省去树的定义及特点从树T的定义可以看出其特点：根无上层节点（或称为父节点、直接前驱），叶节点无下层节点（或称孩子节点、直接后继），其它节点（分支节点）有唯一的一个直接前驱节点和若干个直接后继节点。2．树的逻辑结构表示法1）层次表示法前面关于树的一些例子，都属于层次表示法，它比较直观地表示了树中各节点的层次关系。下面对树的讨论，都采用这种表示法。2）嵌套表示法：如：3）广义表表示法：如例6-5中的树，可表示为：(A(B(E，F)，C))。ACBEFACBEF3.树的基本术语（1）节点：由数据元素(data)及若干连接子树的分支（指针）组成一个节点，即节点=data+pointers，其逻辑形式和存储形式如图6.7所示。逻辑形式：存储形式：（2）节点的出度（OD）：节点拥有的非空子树数目。（3）节点的入度(ID)：指向节点的分支（或有向弧、指针）的数目。（4）树的度（TD）：树中节点出度的最大值。如树T：datap1p2…pn（连接子树的根）(指向各子树的根节点）图6.7ACBEF此树中OD(A)=3，OD(B)=1。显然，叶节点的出度为0。根据树的特点，根的入度为0，其它各节点的入度=1。此树的度为3，它决定了分配给节点的指针数目。度=K的树称为K叉树。data树的基本术语（5）节点之间的关系节点的孩子（或子女）：节点的子树之根为该节点的孩子。如图6.8中，A的孩子分别为B，C，D，反之,B，C，D的双亲（父节点）为A。节点的兄弟：同一双亲下的孩子为兄弟。如图6.8中，B、C、D为兄弟,且B是C的左兄弟，D是C的右兄弟。而E和F之间为堂兄关系。（6）节点的层次：对非空树，根为第一层，根下的孩子节点为第二层，依次类推。层次数的最大值为该树的深度。（7）有序树和无序树：若树中任一节点的各子树从左到右有序，则该树为有序树（强调子树的次序），否则为无序树。设T1、T2：ADBECFACBABC若T1，T2为有序树，它们是两棵不同的树；若T1，T2为无序树，它们是两棵相同的树。图6.8树的基本术语（8）森林（或树林）：m(m≥0)棵互不相交的有序树的有序集合。例6-6设树T1、T2、T3如图6.8所示。图6.8则F={T1,T2,T3}构成一个森林。4．树的抽象数据类型根据上面的定义，我们可以定义如下的抽象数据类型：ADTTree{数据元素集：D（前面已介绍）；数据关系集：R；基本操作集：P；ACBDFEGH树的抽象数据类型TreeInit(&T)操作结果：构造空树T。TreeDestroy(&T)初始条件：树T存在。操作结果：撤销树T。TreeCreat(&T)操作结果：依照建树规则构造一棵树T。TreeClear(&T)初始条件：树T存在。操作结果：将树T清为空树。TreeEmpty(T)初始条件：树T存在。操作结果：若T为空树，返回TRUE，否则返回FLASE。TreeDepth(T)初始条件：树T存在。操作结果：返回T的深度。T＝Φ时，返回0。Root(x)初始条件：x是树或x是树中的节点。操作结果：返回树x或x所在树的根节点。空树返回“空值”。树的抽象数据类型Parent(T,x)初始条件：树T存在，x是T中的节点。操作结果：返回树T中节点x的父节点。若x为根则返回“空值”。Leftchild(T,x)初始条件：树T存在，x是T中的节点。操作结果：返回树Ｔ中节点x的最左孩子，若x为叶节点则返回“空值”。Rightbro(T,x)初始条件：树T存在，x是T中节点。操作结果：返回树T中节点x的右兄弟，若x为双亲的最右子则返回“空值”。InsertChild(&T,p,i,q)初始条件：p是树T中的节点，0≤i≤OD(p)，q是另一棵树的根节点。操作结果：将以q节点为根的树，作为p的第i棵子树插入T中。qp树的抽象数据类型DeleteChild(&T,p,i)初始条件：p是树T中的节点，0≤i≤OD(p)-1。操作结果：删除树T中某p节点的第i棵子树。TraverseTree(T)初始条件：树T存在。操作结果：依照某种次序（或规则）对树中的节点利用visit()函数进行访问，称为遍历（visit()是根据具体datatype和实际对数据的应用方式编写的访问函数）。}ADTTree；6.1.2树的性质树的性质是对树的一些本质的认识。讨论非空树的几个性质（或定理）。性质1：树中节点总数n（n≥0）等于树中各节点的出度之和加1。即：(OD(i)为第i节点的出度)证：除根外，每节点的入度=1，即每节点获得且仅获得一条分支，所以树中总的分支数B＝n－1或n＝B＋1。又：一个节点发出的分支数＝该节点的出度(定义)，所以各节点的分支数之和B＝树中各节点的出度之和。代入n=B+1,性质得证。性质2：度＝K的树（K叉树）第i(i≥1)层至多有Ki-1个节点。证：采用数学归纳法。i=1时，因第一层最多一个节点，故命题K1-1=1成立。设对树的i-1层命题成立，即K叉树第i-1层至多有K(i-1)-1=Ki-2个节点。又：因为是K叉树，所以i-1层上每个节点最多有K个孩子节点，故第i层节点数至多是i-1层的K倍，即第i层至多有Ki-2•K=Ki-1个节点，证毕。1)(1niiODn树的性质性质3：深度＝h(h≥1)的K（K＞1）叉树至多有(Kh-1)/(K-1)个节点。证：性质3是性质2的推广。设深度=h的k叉树最大节点数为S,显然证毕。若一棵深度＝h的k叉树的节点数＝(Kh-1)/(K-1)，则称之为满K叉树。如h=3，K=3的3层满3叉树如图6.10：性质4：包含n（n≥0）个节点的K（K＞1）叉树的最小深度为：11i(11h1KKKShhiii层最大结点数）第节点数=(33-1)/(3-1)=13)1)1((logknk树的性质证：设有n个节点的K叉树的深度为h，若该树h-1层都是满的，即每层有最大节点数Ki-1（1≤i≤h-1），且其余节点都落在第h层，则该树的深度达最小，根据性质3有：或：(Kh-1-1)＜n(K-1)≤(Kh-1)即：Kh－1＜n(k-1)+1≤Kh取对数：（h-1）＜logk(n(K-1)+1)≤h(h-1)h因为h为正整数，所以：h=证毕。1...h-1h11111KKnKKhh)1)1((logknk6.2二叉树二叉树，顾名思义，树的度＝2（或每节点的OD≤2），且当某节点的出度为1时，该节点的子树要么是它的左子树，要么是其右子树。这一点与一般的有序树有所差别。6.2.1二叉树的定义及操作1．定义：二叉树BT是一个二元组，即：BT=(D,R)其中D为树中元素集，R为元素间的关系集，若D=ф，则BT为空树，否则：D＝{root∪DL∪DRroot∈datatype,DL和DR分别为根root的左、右子树集,DL∩DR=ф}R＝{HL,HR}，HL和HR分别为根与左、右子树关系集，即：root,xl，xl为root的左子树SBTL之根，HL=RLSBTL=(DL,RL)——递归，DL≠ффDL=фroot,x2，x2为root的左子树SBTR之根，HR=RRSBTR=(DR,RR)——递归，DR≠ффDR=ф二叉树的定义例6-8设二叉树BT如图6.12:可递归推出：D＝{A,B,C,E,F,G}R={A,B,B,C,B,E,A,F,F,G}ABCEFGLLRR设L、R分别为二叉树根的左、右子树，则二叉树的五种基本形态如图从二叉树的形态看出，二叉树的优点是节点规范（每节点至多2个孩子），便于存储和运算算法的实现。2．二叉树的抽象数据类型ADTBinaryTree{数据元素集：D；数据关系集：R；基本操作集：P；BinaryTreeInit(&BT)操作结果：构造空二叉树BT。BinaryTreeDestroy(&BT)初始条件：二叉树BT存在。操作结果：撤销二叉树BT。BinaryTreeCreat(&BT)操作结果：依照建树规则构造一棵二叉树BT。BinaryTreeClear(&BT)初始条件：二叉树BT存在。操作结果：二叉树BT清为空树。BinaryTreeEmpty(BT)初始条件：二叉树BT存在。操作结果：若BT为空二叉树，返回TRUE，否则返回FLASE。BinaryTreeDepth(BT)初始条件：二叉树BT存在。操作结果：返回二叉树BT的深度。BT＝Φ时，返回0。二叉树的抽象数据类型Root(x)初始条件：x是二叉树或二叉树中的节点。操作结果：返回二叉树x或x所在二叉树的根节点。空二叉树返回“空值”。Parent(BT,x)初始条件：二叉树BT存在，x是BT中节点。操作结果：返回二叉树BT中节点x的父节点。若x为根则返回“空值”。Child(BT,x,i)初始条件：二叉树BT存在，x是BT中节点，i=0或1。操作结果：若i=0，则返回二叉树BT中节点x的左子；若i=1，则返回二叉树BT中节点x的右子。无相应的孩子时返回“空值”。Brother(BT,x,i)初始条件：二叉树BT存在，x是BT中节点，i=0或1。操作结果：若i=0，则返回二叉树BT中节点x的左兄弟；若i=1，则返回二叉树BT中节点x的右兄弟。无相应的兄弟时返回“空值”。二叉树的抽象数据类型InsertChild(&BT,p,i,q)初始条件：p是二叉树BT中的节点，i=0或1，q是一个二叉树节点。操作结果：i=0时，将q节点作为p的左子插入，i=1时作为p的右子插入，原p的左(右)子树改为q的左(右)子树。DeleteChild(&BT,p,i)初始条件：p是二叉树BT中的节点，i=0或1。操作结果：若i=0，则删除BT中P节点的左子树；若i=1，则删除P节点的右子树。TraverseBinaryTree(BT)初始条件：二叉树BT存在。操作结