6.1 树的概念与类型

第六章树树的定义二叉树的定义，性质及存储二叉树的遍历二叉树的线索化树的存储和遍历树、森林与二叉树转换哈夫曼树6.1树的概念与类型6.1.1树的相关概念树是由n（n≥0）个结点组成的有限集合当n＝0时称为空树否则，在任一非空树中必有一个称为根的结点；当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,……Tm其中每一个集合本身又是一棵树，称为根的子树特点非空树中至少有一个根结点树中各子树是互不相交的集合A只有根结点的树ABCDEFGHIJKLM有子树的树根子树树的表示法下列是否是树形结构？否否是是树的表示法集合包含关系文氏图法广义表表示法凹入表表示法树的术语结点(node)结点的度(degree)树的度叶子结点(leaf)分支结点孩子结点(child)双亲结点(parents)兄弟结点(sibling)堂兄弟结点树的层次树的深度有序树与无序树森林路径祖先与子孙终端结点与非终端结点树的表示法结点：表示树中的元素，包括数据项及若干指向其子树的分支结点的度：结点拥有的子树数叶子：度为0的结点，也叫终端结点分支结点：度不为0的结点，也叫非终端结点内部结点：除根结点之外的分支结点也称为内部结点树的基本术语树的度:一棵树中最大的结点度数孩子:结点子树的根称为该结点的孩子双亲:孩子结点的上层结点叫该结点的双亲兄弟:同一双亲的孩子之间互成为兄弟祖先:结点的祖先是从根到该结点所经分支上的所有结点子孙:以某结点为根的子树中的任一结点都成为该结点的子孙树的基本术语结点的层次:从根结点算起，根为第一层，它的孩子为第二层……堂兄弟:其双亲在同一层的结点互称为堂兄弟深度:树中结点的最大层次数有序树:如果将树中结点的各子树看成从左至右是有次序的(即不能互换)，则称该树为有序树，否则称为无序树。有序树中最左边的子树的根称为第一个孩子，最右边的称为最后一个孩子森林:m(m

0)棵互不相交的树的集合ABCDEFGHIJKLM结点A的度：结点B的度：结点M的度：叶子：结点A的孩子：结点B的孩子：结点I的双亲：结点L的双亲：结点B，C，D为？结点F,G为？树的度：结点A的层次：结点M的层次：树的深度：结点A是结点F，G的？结点E,K,L,F是结点B的？树形结构的逻辑特征典型的分支层次结构纵向关系祖先与子孙是纵向次序任一结点都可以有零个或多个直接后继结点但至多只有一个直接前趋结点叶结点无后继根结点无前趋横向关系有序树中，若k1和k2是兄弟，且k1在k2的左边，则k1的任一子孙都在k2的任一子孙的左边ABCDEFGHIJKLM树的基本操作初始化操作INITATE(T)置T为空树求根ROOT(T)或ROOT(x)求树T的根或求结点X所在的树的根结点。若T为空或X不在任何一棵树上，则函数值为“空”求双亲PARENT(T,x)求树T中结点x的双亲结点，若结点x是树T的根结点或结点X不在树T中，则函数值为“空”

求孩子结点CHILD(T,x,i)求树T中结点x的第i个孩子结点，若结点x是树T的叶子或无第i个孩子或结点x不在树T中，则函数值为“空求右兄弟RIGHT_SIBLING(T,x)求树T中结点x右边的兄弟，若结点x是其双亲的最右边的孩子结点或结点x不在树T中，则函数值为“空”；树的基本操作建树CRT_TREE(x,F)生成一颗以x结点为根，以森林F为子树森林的树；插入子树操作INS_CHILD(y,i,x)置以结点x为根的树为结点y的第i棵子树，若原树中无结点y或结点y的子树个数小于i-1，则空操作；删除子树操作DEL_CHILD(x,i)删除结点x的第i棵子树，若无结点x或结点x的子树个数小于i，则空操作；遍历操作TRAVERSE(T)按某个次序依次访问树中各个结点，并使每个结点只被访问一次；清除操作CLEAR(T)将树T置为空树树的应用决策：根据一些给定的条件来确定应采取的行动。R1R2R3R4R5123C1乘客年龄16—60C2购买往返票C3乘客有优待证收费：票价的100%收费：票价的90%收费：票价的80%收费：票价的70%Y-YXYYNXYNNXNY-XNN-X树的应用：决策树树的应用：判定树采用图a进行判断，80%以上的数据要进行三次或三次以上的比较才能得到结果。如何使大部分数据经过较少次数的比较得到结果？等级分数段比例优秀良好中等及格不及格0~5960~6970~7980~8990~1005％15％40％30％10％二叉树定义二叉树是结点的有限集合或者是空树或者由一个根结点和两棵二叉子树构成左子树，右子树子树不相交特点每个结点至多有二棵子树不存在度大于2的结点子树有左、右之分，次序不能任意颠倒二叉树是否是一种特殊的树?二叉树的五种形态空二叉树右子树为空的二叉树左子树非空的二叉树仅有根结点的二叉树左右子树均非空的二叉树满二叉树深度为k的满二叉树，有2k-1个结点2k-1，是深度为K的二叉树所具有的最大结点个数123114589121367101415满二叉树特点每层上的结点数都达到最大值只有度为0的结点和度为2的结点每个结点均有两棵高度相同的子树叶子结点都在树的最下面一层上满二叉树辨析具有n个结点、深度为K的二叉树当且仅当其所有结点对应于深度为k的满二叉树中编号由1到n的那些结点时该二叉树便是完全二叉树完全二叉树123114589126710完全二叉树特点叶子结点只可能在最大的两层上出现对任意结点，若其右分支下的子孙最大层次为L，则其左分支下的子孙的最大层次必为L或L+1除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。123114589121367101415满二叉树完全二叉树辨析性质1:在二叉树第i层上至多有2i-1

个结点(i≥1)证明当i=1时，只有一个根结点。显然，2i-1

＝20

＝１是对的假设对所有的j(1≤j﹤i)，命题成立即第j层上至多有2j-1

个结点那么可以证明j=i时命题成立归纳假设：第i-1层上至多有2i-2

个结点。由于二叉树的每个结点的度至多为2，故在第i层上的最大结点数为第i-1层上的最大结点数的2倍即2*2i-2＝2i-1。二叉树的性质性质2深度为k的二叉树至多有2k－１个结点(k≥1)二叉树的性质性质3：对任意二叉树T，如果其终端结点数为n0，度为2的结点数为n2,则n0=n2+1。证明二叉树中结点总数为：

n=n0+n1+n2(5-1)二叉树的分支数为：

n1+2*n2(5-2)因此：结点总数为：

n=n1+2*n2+1由(5-1)、(5-2)两式可得n0=n2+1二叉树的性质性质4具有n个结点的完全二叉树的深度为

log2

n」+1证明假设深度为k，则根据性质2和完全二叉树的定义有于是因为k是整数,所以二叉树的性质二叉树的性质性质5对一棵有n个结点的完全二叉树的结点按层序号编号(从第1层到

log2n

+1层，每层从左到右)，则对任一结点i(i≤i≤n),有如果i=1，则结点i是根结点，无双亲，否则，其双亲结点为

i/2

如果2i