第七章树和二叉树.

7.1树的基本概念及ADT7.2二叉树7.2.1二叉树的概念7.2.2二叉树的性质7.2.3二叉树的存储结构7.2.4二叉树的遍历7.2.5二叉树的构造7.3线索二叉树7.4树和森林7.5Huffman树和Huffman编码树的应用某些数据库管理系统含有分层结构的数据库；复杂的程序，采用的基本数据结构是树；在编译系统中，编译程序把高级语言的语句或表达式分解为树结构加以分析和处理，然后生成机器代码的目的码指令；操作系统的文件处理采用分级管理的办法，采用树结构，以提高文件的存取速度；某些操作系统把主存也按树结构划分，树中的每个结点包含数据或代码段；某些程序模块本身近似于树型结构；二叉排序树：特点是用非线性结构表示一个线性有序表；决策树：在企业的数据处理和系统分析等领域中出现的决策问题：即要求根据一些给定条件来确定应采取什么行动，如保险公司的业务决策；博弈树（GameTree）：人——机博弈；堆（heap）排序：实际上是一棵完全二叉树结点的层次序列；Ldap：轻量目录访问协议；Huffman树：信息检索；………树例与特征社会的组织结构家族的族谱计算机中的目录组织描述层次结构，是一种一对多的逻辑关系是一种非线性结构树的形式化定义树：T={D,R}。D是包含n个节点的有穷集合（n≥0）。当n=0时为空树，否则关系R满足以下条件:有且仅有一个节点d0∈D，它对于关系R来说没有前驱节点，节点d0称作树的根节点。除节点d0外，D中的每个节点对于关系R来说都有且仅有一个前驱节点。D中每个节点对于关系R来说可以有零个或多个后继节点。7.1树的基本概念及其ADT定义7.1.1树的定义树的递归定义：树是由n（n≥0）个节点组成的有限集合（记为T）。其中：如果n=0，它是一棵空树，这是树的特例；如果n0，这n个节点中存在（且仅存在）一个节点作为树的根节点，简称为根节点（root），其余节点可分为m（m0）个互不相交的有限集T1,T2,…,Tm,其中每一棵子集本身又是一棵符合本定义的树，称为根root的子树。rootT1T2Tm…树定义ACBGFEHIJDMKLAT1T2T3树的抽象数据类型ADTTree{数据对象D：D是具有相同性质的数据元素的集合。数据关系R：若D为空集，则称为空树；若D仅含有一个数据元素，则R为空集，否则R={H}，H是如下二元关系：（1）在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；（2）若D-{root},则存在D-{root}的一个划分D1，D2…Dm（m0）,对任意jk(1j,km)有DjDK=,且对任意的i(1im),存在唯一的数据元素xiDi,root,xiH;（3）对应于D-{root}的划分，H-{root,x1,…root,xm}有唯一的一个划分H1,H2,…Hm(m0),对任意jk(1j,km)有HjHk=,且对任意i(1im)，Hi是Di上的二元关系，(Di，{Hi}）是一棵符合本定义的树，称为根root的子树。注意：“－”是集合的补运算，“”是集合的交运算基本操作：TreeInit(T);TreeChild(T,x,i);Treebuild(T,F);TreeClear(T);Traverse(T);TreeRoot(T);TreeParent(T,x);TreeRightBrother(T,x);TreeLeftBrother(T,x);TreeInsert(T,y,i,x);}ADTTree树的抽象数据类型7.1.2树的表示（1）树形表示法。这是树的最基本的表示，使用一棵倒置的树表示树结构，非常直观和形象。下图就是采用这种表示法。ABCDEFGJHIKLM逻辑结构表示1（2）文氏图表示法。使用集合以及集合的包含关系描述树结构。下图就是树的文氏图表示法。ABCDEFGJHIKLM逻辑结构表示2AEFBCGJHDKLMI（3）凹入表示法。使用线段的伸缩描述树结构。下图是树的凹入表示法。逻辑结构表示3ABCDEFGJHIKLM（4）括号表示法。将树的根节点写在括号的左边，除根节点之外的其余节点写在括号中并用逗号间隔来描述树结构。下图是树的括号表示法。括号表示法A(B(E,F),C(G(J)),D(H,I(K,L,M)))ABCDEFGJHIKLM树的其它逻辑表示方式ACBGFEHIJDMKLAJIMHDGCFLKEB凹入表示法ABFEKLGCDHMIJ嵌套集合表示法(A(B(E(K,L),F),C(G),D(H(M),I,J)))广义表表示法树型表示法类似于书的编目7.1.3树的基本术语1.节点的度与树的度：树中某个节点的子树的个数称为该节点的度。树中各节点的度的最大值称为树的度，通常将度为m的树称为m次树。2.分支节点与叶节点：度不为零的节点称为非终端节点,又叫分支节点。度为零的节点称为终端节点或叶节点。在分支节点中，每个节点的分支数就是该节点的度。如对于度为1的节点,其分支数为1，被称为单分支节点；对于度为2的节点，其分支数为2，被称为双分支节点，其余类推。ABCDEFGJHIKLM度为3度为2ABCDEFGJHIKLM度为3度为23.路径与路径长度：对于任意两个节点di和dj，若树中存在一个节点序列di,di1,di2,…,din,dj，使得序列中除di外的任一节点都是其在序列中的前一个节点的后继，则称该节点序列为由di到dj的一条路径，用路径所通过的节点序列(di,di1,di2,…,dj)表示这条路径。路径长度等于路径所通过的节点数目减1（即路径上分支数目）。ABCDEFGJHIKLMA到K的路径为（A,D,I,K）其长度为34.孩子节点、双亲节点和兄弟节点：在一棵树中，每个节点的后继，被称作该节点的孩子节点（或子女节点）。相应地，该节点被称作孩子节点的双亲节点（或父母节点）。具有同一双亲的孩子节点互为兄弟节点。进一步推广这些关系，可以把每个节点的所有子树中的节点称为该节点的子孙节点。从树根节点到达该节点的路径上经过的所有节点被称作该节点的祖先节点。ABCDEFGJHIKLM5.节点的层次和树的高度：树中的每个节点都处在一定的层次上。节点的层次从树根开始定义，根节点为第1层，它的孩子节点为第2层,以此类推,一个节点所在的层次为其双亲节点所在的层次加1。树中节点的最大层次称为树的高度（或树的深度）。6.有序树和无序树：若树中各节点的子树是按照一定的次序从左向右安排的，且相对次序是不能随意变换的，则称为有序树，否则称为无序树。ABCDEFGJHIKLM1234有的教材规定为第0层一般讨论无序树树和其子树之间的次序有序树和无序树之间的区别在于：子树之间是否存在次序关系。ACBGFEHIJDMKLACDGJHEIFBMKL如果讨论的是无序树，则这两棵树是等同的，否则是不等同的。此书一般讨论无序树7.森林：n（n＞0）个互不相交的树的集合称为森林。森林的概念与树的概念十分相近，因为只要把树的根节点删去就成了森林。反之，只要给n棵独立的树加上一个节点，并把这n棵树作为该节点的子树，则森林就变成了树。任何一棵非空树是一个二元组Tree=(root,F)其中：root被称为根结点F被称为子树森林注意与自然界中的树和森林的概念不同。概念示例结点结点的度(Degree)叶子（Leaf)或终端结点分支结点或非终端结点树的度层次(Level)树的深度(Depth)孩子（child)双亲（Parent)兄弟(Sibling)祖先子孙ACBGFEHIJDMKL树的基本操作分为三大类：查找插入删除查找操作分为特定的查找和按关系的查找特定的查找Root(T);Value(T,cur_e);按关系的查找Parent(T,cur_e);LeftChild(T,cur_e);RightSibling(T,cur_e);某些特性的判别TreeEmpty(T);TreeDepth(T);特殊的操作TraverseTree(T,Visit());查找树中值为cur_e的某个结点查找树中值为cur_e的结点的最左边的孩子插入操作InitTree(&T);CreatTree(&t,definition);Assign(&T,cur_e,valus);InsertChild(&T,&p,i,c);根据定义生成树，如给定树根和子树森林可以生成树改变树上某个结点的值插入一棵子树，如在树T中指针p所指的位置插入一棵以c为根的子树，并且作为第i棵子树删除操作ClearTree(&T)DestroyTree(&T);DeleteChild(&T,&p,i);删除树T中某个结点的某个子树一般讨论的是有向树（箭头略去不画）：1）有确定的根；2）树根和子树根之间为有向关系;树结构和线性结构的比较线性结构树结构第一个数据元素（无前驱）根结点（无前驱）最后一个数据元素（无后继）多个叶子结点（无后继）其他数据元素（一个前驱，一个后继）树中其他结点（一个前驱，多个后继）一对一一对多7.2二叉树7.2.1二叉树的概念二叉树(BinaryTree)：或者是一棵空树，或者是一棵由一个根结点和两棵互不相交的左子树和右子树所组成的非空树，左子树和右子树又同样都是二叉树。特征：每个结点最多只有两棵子树子树有左右之分，其次序不能任意颠倒许多实际问题抽象出来的数据结构往往是二叉树的形式ABECDFGHK根结点A的左子树根结点A的右子树二叉树的五种形态(a)(b)(c)(d)(e)空树只有一个根结点的树右子树为空左子树为空左右子树均非空与有序树不同，即使只有一棵子树也要区分出是左子树还是右子树。有序树右子树为空左子树为空在一棵二叉树中,如果所有分支节点都有左孩子节点和右孩子节点，并且叶节点都集中在二叉树的最下一层，这样的二叉树称为满二叉树。下图所示就是一棵满二叉树。可以对满二叉树的节点进行连续编号，约定编号从树根为1开始，按照层数从小到大、同一层从左到右的次序进行。图中每个节点外边的数字为对该节点的编号。ABCDEHIJKFGLMNO123456789101511121314满二叉树若二叉树中最多只有最下面两层的节点的度数可以小于2，并且最下面一层的叶节点都依次排列在该层最左边的位置上，则这样的二叉树称为完全二叉树。如下图所示为一棵完全二叉树。同样可以对完全二叉树中每个节点进行连续编号，编号的方法同满二叉树相同。图中每个节点外边的数字为对该节点的编号。ABCDEHIJKFG1234567891011完全二叉树189101112452673完全二叉树二叉树的抽象数据类型ADTBinTree{数据对象D：D是具有相同特性的数据元素的集合。数据关系R：若D=，则R=，称二叉树为空二叉树；若D，则R={H}，H是如下二元关系：（1）在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；（2）若D-{root},则存在D-{root}={D1,Dr},且D1Dr；（3）若D1，则D1中存在唯一的元素x1,root,x1H,且存在D1上的关系H1H；若Dr,则Dr中存在唯一的元素xr,root,xrH,且存在Dr上的关系HrH；H={root,x1,root,xr,H1,Hr};（4）（D1，{H1}）是一棵符合本定义的二叉树，称为根的左子树，（Dr，{Hr}）是一棵符合本定义的二叉树，称为根的右子树。二叉树的抽象数据类型基本操作：BinTreeInit(BT);BinTreeRoot(BT);BinTreeParent(BT,x);BinTreeLeftChild(BT,x);BinTreeRightChild(BT,x);BinTreeBulid(BT,LBT,RBT);BinTreeInsertLeft(BT,y,x);BinTreeInsertRight(BT,y,x);BinTreeDeleteLeft(BT,x);BinTreeDele