第6章树和二叉树

1、第6章 树和二叉树 树型结构是一类重要的非线性数据结构。其中以树和二叉树最为常用，直观看来，树是以分支关系定义的层次结构。 6.1 树的定义和基本术语 树树(Tree)是n(n0)个结点的有限集。在任意一棵非空树中： (1)有且仅有一个特定的称为根根(Root)的结点； (2)当n1时，其余结点可分为m(m0)个互不相交的有限集T1，T2，Tm，其中每一个集合本身又是一棵树，并且称为根的子树子树(SubTree)。 例如， (a)是只有一个根结点的树；(b)是有13个结点的树，其中A是根，其余结点分成三个互不相交的子集：T1= B，E，F，K，L，T2=C，G，T3=D，H，I，J，M；T1、

2、T2和T3都是根A的子树，且本身也是一棵树。 (a)只有根结点的树 (b)一般的树AMLKEFGCBJIHDA 树的结构定义是一个递归的定义，即在树的定义中又用到树的概念，它道出了树的固有特性。基本术语 树的结点结点包含一个数据元素及若干指向其子树的分支。 度为0的结点称为叶子叶子(1eaf)或终端结点终端结点。 度不为0的结点称为非终端结点非终端结点或分支结分支结点点。除根结点之外，分支结点也称为内部结点。 树的度树的度是树内各结点的度的最大值。 结点的子树的根称为该结点的孩子孩子(child)，相应地，该结点称为孩子的双亲双亲(Parent)。 同一个双亲的孩子之间互称兄弟兄弟(sibli

3、ng) 结点的祖先祖先是从根到该结点所经分支上的所有结点。 结点的层次层次(level)从根开始定义起，根为第一层，根的孩子为第二层。若某结点在第i层，则其子树的根就在第i+1层。其双亲在同一层的结点互为堂兄弟堂兄弟。 树中结点的最大层次称为树的深度深度(Depth)或高度高度。 如果将树中结点的各子树看成从左至右是有次序的(即不能互换)，则称该树为有序树有序树，否则称为无序树无序树。在有序树中最左边的子树的根称为第一个孩子，最右边的称为最后一个孩子。 森林森林(Forest)是m(m0)棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。由此，也可以森林和树相互递归的定义来描述树

4、。 就逻辑结构而言，任何一棵树是一个二元组Tree= (root，F)，其中：root是数据元素，称做树的根结点；F是m(m0)棵树的森林；F=(T1，T2，Tn)，其中Ti=(ri，Fi)称做根root的第i棵子树；当m!=0时，在树根和其子树森林之间存在下列关系： RF=| i=1 , 2 , , m , m 0 1层2层4层3层height= 4ACGBDE FK LHMIJ层次层次 根为第根为第1层层 最大层数为树的深度（高度）最大层数为树的深度（高度） 双亲双亲 (直接前驱）直接前驱） 孩子孩子（直接后继）（直接后继） 兄弟兄弟 堂兄弟堂兄弟 子孙子孙 祖先祖先d=3d=0d=2K

5、LFGMI JABCDEH抽象数据类型树的定义。 ADT Tree 数据对象数据对象D： D是具有相同特性的数据元素的集合。 数据关系数据关系R： 若D为空集，则称为空树；若D仅含一个数据元素，则R为空集，否则R=H， H是如下二元关系： (1)在D中存在唯一的称为根的数据元素root，它在关系H下无前驱； (2)若D-root!=，则存在D-root)的一个划分D1，D2，Dm (m0)，对任意j!=k(1j，km)有DjDk=，且对任意的i(1im)，唯一存在数据元素xiDi，有H； (3)对应于D-root的划分，H-，有唯一的一个划分H1，H2，Hm(m0)，对任意j!=k(1j，km

6、)有HjHk=，对任意i(1im)，Hi是Di上的二元关系，（Di ,Hi)是一棵符合本定义的子树，称为根root的子树。 基本操作基本操作： InitTree(T)； 操作结果：构造空树T。 DestroyTree(&T)； 初始条件：树T存在。 操作结果：销毁树T。CreateTree(&T，definition)； 初始条件：definition给出树T的定义。 操作结果：按definition构造树T。 ClearTree(T)； 初始条件：树T存在。 操作结果：将树T清为空树。 TreeEmpty(T)； 初始条件：树T存在。 操作结果：若T为空树，则返回TRUE，否

7、则FALSE； TreeDepth(T)； 初始条件：树T存在。 操作结果：返回T的深度。 Root(T)； 初始条件：树T存在。 操作结果：返回T的根。 Value(T，cur_e)； 初始条件：树T存在，cur_e是T中某个结点。 操作结果：返回cur_e的值。 Assign(T，cur_e，value)； 初始条件：树T存在，cur_e是T中某个结点。 操作结果：结点cur_e赋值为value。 Parent(T，cur_e)； 初始条件：树T存在，cur_e是T中某个结点。 操作结果：若cur_e是T的非根结点，则返回它的双亲。 否则函数值为“空”。 LeftChild(T，cur_e

8、)； 初始条件：树T存在，cur_e是T中某个结点。 操作结果：若cur_e是T的非叶子结点，则返回它的最左孩子，否则返回“空”。Rightsibling(T，cur_e)； 初始条件：树T存在，cur_e是T中某个结点。 操作结果：若cur_e有右兄弟，则返回它的右兄弟，否则函数值为“空”。 InsertChild(&T，&p，i，c)； 初始条件：树T存在，p指向T中某个结点，1ip指结点的度+1，非空树c与T不相交。 操作结果：插入c为T中p指结点的第i棵子树。 DeleteChild(T，&p，i)； 初始条件：树T存在，p指向T中某个结点，1ip指结点的度。

9、操作结果：删除T中p所指结点的第i棵子树。TraverseTree(T，Visit()； 初始条件：树T存在，Visit是对结点操作的应用函数。 操作结果：按某种次序对T的每个结点调用函数，visit()一次至多次，一旦visit()失败，则操作失败。ADT Tree6.2 二 叉 树 在讨论一般树的存储结构及其操作之前，我们首先研究一种称为二叉树的抽象数据。 6.2.1 二叉树的定义 二叉树二叉树(BinaryTree)是另一种树型结构，它的特点是每个结点至多只有二棵子树(即二叉树中不存在度大于2的结点)，并且，二叉树的子树有左右之分，其次序不能任意颠倒。 ADT BinaryTree 数据

10、对象数据对象D： D是具有相同特性的数据元素的集合。 数据关系数据关系R： 若D= ，则R=，称BinaryTree为空二叉树； 若D!= ，则R=H，H是如下二元关系： (1)在D中存在唯一的称为根的数据元素root，它在关系H 下无前驱； (2)若D-root!=，则存在D-root=Dl，Dr，且DlDr=； (3)若Dl!=，则Dl中存在唯一的元素xl，H，且存在Dl上的关系H1为H的子集；若Dr!=，则Dr中存在唯一的元素xr，H，且存在Dr上的关系Hr为H的子集； H=，Hl，Hr； (4)(Dl，Hl)是一棵符合本定义的二叉树，称为根的左子树，(Dr，Hr)是一棵符合本定义的二叉

11、树，称为根的右子树。 基本操作基本操作P： InitBiTree(&T)； 操作结果：构造空二叉树T。 DestroyBiTree(&T)； 初始条件：二叉树T存在。 操作结果：销毁二叉树T。 CreateBiTree(&T，definition) 初始条件：definition给出二叉树T的定义。 操作结果：按definition构造二叉树T。 ClearBiTree(&T)； 初始条件：二叉树T存在。 操作结果：将二叉树T清为空树。 BiTreeEmpty(T)； 初始条件：二叉树T存在。 操作结果：若T为空二叉树，则返回TRUE， 否则FALSE。 BiT

12、reeDepth(T)； 初始条件：二叉树T存在。 操作结果：返回T的深度。 Root(T)； 初始条件：二叉树T存在。 操作结果：返回T的根。 Value(T，e)； 初始条件：二叉树T存在，e是T中某个结点。 操作结果：返回e的值。 Assign(T，&e，value)； 初始条件：二叉树T存在，e是T中某个结点。 操作结果：结点e赋值为value。 Parent(T，e)； 初始条件：二叉树T存在，e是T中某个结点。 操作结果：若e是T的非根结点，则返回它的双亲。 LeftChild(T，e)； 初始条件：二叉树T存在，e是T中某个结点。 操作结果：返回e的左孩子。若e无左孩子，

13、则返回“空”。 RightChild(T，e)； 初始条件：二叉树T存在，e是T中某个结点。 操作结果：返回e的右孩子。若e无右孩子，则返回“空”。 Leftsibling(T，e)； 初始条件：二叉树T存在，e是T中某个结点。 操作结果：返回e的左兄弟。若e是T的左孩子或无左兄弟，则返回“空”。 RightSibling(T，e)； 初始条件：二叉树T存在，e是T中某个结点。 操作结果：返回e的右兄弟。若e是T的右孩子或无右兄弟，则返回“空”。 InsertChild(T , p , LR , c); 初始条件：二叉树T存在，p指向T中某个结点，LR为0或1，非空二叉树c与T不相交且右子树为

14、空。 操作结果：根据LR为0或1，插入c为T中p所指结点的左或右子树。p所指结点的原有左或右子树则成为c的右子树。 DleteChild(T，p，LR)； 初始条件：二叉树T存在，p指向T中某个结点，LR为0或1。 操作结果：根据Ix为0或1，删除T中p所指结点的左或右子树。 LevelOrderTraverse(T，Visit()； 初始条件：二叉树T存在，Visit是对结点操作的应用函数。 操作结果：层序遍历T，对每个结点调用函数Visit一次且仅一次， 一旦visit()失败，则操作失败。PreOrderTraverse(T，Visit()； 初始条件：二叉树T存在，Visit是对结点操

15、作的应用函数。 操作结果：先序遍历T，对每个结点调用函数Visit一次且仅一次，一旦visit失败，则操作失败。InOrderTraverse(T，Visit()； 初始条件：二叉树T存在，Visit是对结点操作的应用函数。 操作结果：中序遍历T，对每个结点调用函数Visit一次且仅一次，一旦visit失败，则操作作失败。 PostOrderTraverse(T，Visit()； 初始条件：二叉树T存在，Visit是对结点操作的应用函数。 操作结果：后序遍历T，对每个结点调用函数Visit一次且仅一次，一旦visit失败，则操作失败。ADT BinaryTree 上述数据结构的递归定义表明二叉

16、树或为空，或是由一个根结点加上两棵分别称为左子树和右子树，两棵互不相交的二叉树组成。由于这两棵子树亦是二叉树，则由二叉树的定义它们可以是空树。由此二叉树可以有五种基本形态 (a)空二叉树；(b)仅有根结点的二叉树；(c)右子树为空的二叉树；(d)左、右子树均非空的二叉树；(e)左子树为空的二叉树。 6.2.2 二叉树的性质二叉树的性质 二叉树具有下列重要特性。 性质性质1 在二叉树的第i层上至多有2i-1个结点(i1)。 利用归纳法容易证得此性质。 i=1时，只有一个根结点。 显然，2i-1=20=1是对的。 现在假定对所有的j，1ji，命题成立，即第j层上至多有2j-1个结点。那么，可以证明

17、j=i时命题也成立。 由归纳假设：第i-1层上至多有2i-2个结点。由于二叉树的每个结点的度至多为 2，故在第i层上的最大结点数为第i-1层上的最大结点数的2倍，即2*2i-2=2i-1。 性质性质2 深度为k的二叉树至多有2k-1个结点，(k1)。由性质1可见，深度为k的二叉树的最大结点数为 k k (第i层上的最大结点数) =2i-1=2k -1 i=1 i=1 性质性质3 对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。 设n1为二叉树T中度为1的结点数。因为二叉树中所有结点的度均小于或等于2所以其结点总数为 n=n0+n1+n2 (61) 再看二叉树

18、中的分支数。除了根结点外，其余结点都有一个分支进入，设B为分支总数，则n=B+1。由于这些分支是由度为1或2的结点射出的，所以又有B=n1+ 2n2。 n=n1+2n2+1 (62) 于是得由式(61)和(62)得 n0=n2+1 完全二叉树和满二叉树，是两种特殊形态的二叉树。 一棵深度为k且有2k-1个结点的二叉树称为满二叉树满二叉树。如图6.4(a)所示是深度为4的满二叉树，这种树的特点是每一层上的结点数都是最大结点数。 6.4(a) 可以对满二叉树的结点进行连续编号，约定编号从根结点起，自上而下，自左至右。由此可引出完全二叉树的定义：深度为k的，有n个结点的二叉树，当且仅当其每一个结点都

19、与深度为k的满二叉树中编号从1至n的结点一一对应时，称之为完全二叉树完全二叉树。16712 13 14 151110958423 如图6.4(b)所示为一棵深度为4的完全二叉树。显然，这种树的特点是：(1)叶子结点只可能在层次最大的两层上出现；(2)对任一结点，若其右分支下的子孙的最大层次为L，则其左分支下的子孙的最大层次必为L或L+1。如图6.4中(c)和(d)不是完全二叉树。 6.4(b) 6.4(c) 6.4(d)1211109876543217654231654321 完全二叉树将在很多场合下出现，下面介绍完全二叉树的两个重要特性。 性质性质4 具有n个结点的完全二叉树的深度为 log

20、2n +1。 证明：假设深度为k，则根据性质2和完全二叉树的定义有 2k-1-1n2k-1 或 2k-1n2k 于是k-1log2n1，则其双亲PARENT(i)是结点 i/2 。 (2) 如果2in，则结点i无左孩子(结点i为叶子结点)；否则其左孩子LCHILD(i)是结点2i。 (3)如果2i+1n，则结点i无右孩子；否则其右孩子RCHILD(i)是结点2i+1。 (a)结点i和i+1在同一层上； (b)结点i和i+1不在同一层上。 图6.5 完全二义树中结点i和i+1的左、右孩子 2i+1i/2i2ii+12i+22i+32i+3i+12i+2i2i2i+16.2.3 二叉树的存储结构二

21、叉树的存储结构 一、顺序存储结构 /二叉树的顺序存储表示 #define MAX_TREE_SIZE 100， /二叉树的最大结点数 typedef TElemType SqBiTreeMAX_TREE_SIZE; /0号单元存储根结点 SqBiTree bt； 按照顺序存储结构的定义，在此约定，用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素，即将完全二叉树上编号为i的结点元素存储在如上定义的一维数组中下标为i-1的分量中。 (a)完全二叉树； (b)一般二叉树。 图66 二叉树的顺序存储结构12345678910111212345000067 二、链式存储结构 由二

22、叉树的定义得知，二叉树的结点由一个数据元素和分别指向其左、右子树的两个分支构成，则表示二叉树的链表中的结点至少包含三个域：数据域和左、右指针域。 图6.7 二义树的结点及其存储结构DATAPARENTLCHILD RCHILD(a)二叉树的结点；rchilddatalchild(b)含有两个指针域的结点结构；rchildparentdatalchild(c)含有三个指针域的结点结构 链表的头指针指向二叉树的根结点。容易证得，在含有n个结点的二叉链表中有n+1个空链域。在6.3节中我们将会看到可以利用这些空链域存储其它有用信息，从而得到另一种链式存储结构线索链表。 (a)单支树的二叉链表； (b

23、)二叉链表； (c)三叉链表。 图68 链表存储结构 ABCDDCBACBAGFEDGFECDBAABCDEFG6.3 遍历二叉树和线索二叉树 6.3.1 遍历二叉树遍历二叉树 遍历二叉树(Traversing Binary Tree) ，即如何按某条搜索路径巡访树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。 回顾二叉树的递归定义可知，二叉树是由三个基本单元组成：根结点、左子树和右子树。因此，若能依次遍历这三部分，便是遍历了整个二叉树。假如以L、D、R分别表示遍历左子树、访问根结点和遍历右子树，则可有DLR、LDR、LRD、DRL、RDL、RLD六种遍历二叉树的方案。若限定先左后右

24、，则只有前三种情况，分别称之为先(根)序遍历，中(根)序遍历和后(根)序遍历。基于二叉树的递归定义，可得下述遍历二叉树的递归算法定义。 先序遍历二叉树的操作定义为： 若二叉树为空，则空操作；否则 (1)访问根结点； (2)先序遍历左子树； (3)先序遍历右子树。中序遍历二叉树的操作定义为： 若二叉树为空，则空操作；否则 (1)中序遍历左子树； (2)访问根结点； (3)中序遍历右子树。后序遍历二叉树的操作定义为： 若二叉树为空，则空操作；否则 (1)后序遍历左子树； (2)后序遍历右子树； (3)访问根结点。 例如图6.9所示的二叉树表示下述表达式 a+b*(c-d)-e/f 若先序遍历此二叉

25、树，按访问结点的先后次序将结点排列起来，可得到二叉树的先序序列为 -+a*b-cd/ef (63) 类似地，中序遍历此二叉树，可得此二叉树的中序序列为 a+b*c-d-e/f (64) 后序遍历此二叉树，可得此二叉树的后序 序列为 abcd -*+ef/- (65) 从表达式来看，以上三个序列(63)、 (64)和(65)恰好为表达式的前缀表 示(波兰式)、中缀表示和后缀表示 (逆波兰式)。 图6.9表达式的二叉树/-+fecbd-*aStatus PreOrderTraverse ( Bitree T, Status (*Visit)(TElemType e)1if(T) 2 if(Visi

26、t(T-data)3 if(PreOrderTraverse(T-lchild，Visit)4 if(PreOrderTraverse(T-rchild，Visit) return OK;5 return ERROR；6 else return OK；7/PreOrderTraverse 二叉树操作 计算一棵二叉树的叶子结点数目 这个操作可以使用三种遍历顺序中的任何一种，只是需要将访问操作变成判断该结点是否为叶子结点，如果是叶子结点将累加器加1即可。下面这个算法是利用先序遍历实现的。 理解定义：如果二叉树有左（右）子树，则分别求出左右子树叶子结点数目（指针换成左或右子树），然后求和。 三种情况

27、，1、空树；2、只有一个根节点；3、有子树 void Leaf(BTree BT,int &count) if (BT) if (!BT-lchild) & (!BT-rchild) count+; Leaf(BT-lchild, count); /计算左子树的叶子结点个数 Leaf(BT-rchild, count); /计算右子树的叶子结点个数 求二叉树的高度 这个操作使用后序遍历比较符合人们求解二叉树高度的思维方式。首先分别求出左右子树的高度，在此基础上得出该棵树的高度，即左右子树较大的高度值加1。 int hight(BTree BT) /h1和h2分别是以BT为根的左

28、右子树的高度 if (BT=NULL) return 0; else h1 = hight(BT-lchild); h2 = hight(BT-right); return maxh1,h2+1; 复制二叉树 根据已有的一个二叉树，复制一棵二叉树。 BiTNode *GetTreeNode(TelmentType item, BiTNode *lptr, BiTNode *rptr) if (!(T=(BitNode *)malloc(sizeof(BiTNode) exit (1);T-data = item;T-lchild = lptr;T-rchild = rptr;Retrun T;

29、 BiTNode *CopyTree(BiTNode *T) if(!T) return NULL; if(T-lchild) newlptr = CopyTree (T-lchild); else newlptr = NULL; if(T-rchild) newrptr = CopyTree (T-rchild); else newrptr = NULL; newnode = GetTreeNode(T-data, newlptr,newrptr); return newnode; 建立二叉树根据先序序列（包含空格）创建二叉树。 先序遍历和中序遍历共同确定一个二叉树 Status Creat

30、eBiTree(BiTree&T)scanf(&ch)； if(ch= ) T=NULL； else if(!(T=(BiTNode*)malloc(sizeof(BiTNode) exit(OVERFLOW) ; T-data=ch； /生成根结点 CreateBiTree(T-lchild)； /构造左子树 CreateBiTree(T-rchild)； /构造右子树 return OK; /CreateBiTree 6.4 树和森林 这一节我们将讨论树的表示及其遍历操作，并建立森林与二叉树的对应关系。 6.4.1 树的存储结构树的存储结构 在大量的应用中，人们曾使用多种形

31、式的存储结构来表示树。这里，我们介绍三种常用的链表结构。 一、双亲表示法 假设以一组连续空间存储树的结点，同时在每个结点中附设一个指示器指示其双亲结点在链表中的位置，其形式说明如下： /树的双亲表存储表示 #define MAX_TREE_SIZE 100 typedef struct PTNode TElemType data； int parent； /双亲位置域 PTNode；typedef struct PTNode nodesMAX_TREE_SIZE int n； /结点数PTree；例如，图6.13展示一棵树及其双亲表示的存储结构。 ABFKHGEDCR 6 K 6 H 6 G

32、3 F 1 E 1 D 0 C 0 B 0 A -1 这种存储结构利用了每个结点(除根以外)只有唯一的双亲的性质。PARENT(T，x)操作可以在常量时间内实现。反复调用PARENT操作，直到遇见无双亲的结点时，便找到了树的根，这就是ROOT(x)操作的执行过程。但是，在这种表示法中，求结点的孩子时需要遍历整个结构。二、孩子表示法 由于树中每个结点可能有多棵子树，则可用多重链表，即每个结点有多个指针域，其中每个指针指向一棵子树的根结点，此时链表中的结点可以有如下两种结点格式 若采用第一种结点格式，则多重链表中的结点是同构的，其中d为树的度。由于树中很多结点的度小于d，

33、所以链表中有很多空链域，空间较浪费，不难推出，在一棵有n个结点度为k的树中必有n(k-1)+1个空链域。若采用第二种结点格式，则多重链表中的结点是不同构的，其中d为结点的度，degree域的值同d。此时，虽能节约存储空间，但操作不方便。datachild1child2 childddatadegreechild1child2 childd 另一种办法是把每个结点的孩子结点排列起来，看成是一个线性表，且以单链表作存储结构，则n个结点有n个孩子链表(叶子的孩子链表为空表)。而n个头指针又组成一个线性表，为了便于查找，可采用顺序存储结构。 对应图6.13 K H G F E R D C B A352

34、1987060123456789412986073K6H6G6F2E0R-1D0C4B4A40123456789这种存储结构可形式地说明如下：/树的孩子链表存储表示 typedef struct CTNode /孩子结点 int child； struct CTNode *next； *ChildPtr； typedef struct TElemType data； ChildPtr firstchild；/孩子链表头指针 CTBox； typedef struct CTBox nodesMAX_TREE_SXZE； int n，r； /结点数和根的位置 CTree； 三、孩子兄弟表示法 又称

35、二叉树表示法，或二叉链表表示法。即以二叉链表作树的存储结构。链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点，分别命名为 firstchild域和nextsibling域。/树的二叉链表(孩子兄弟)存储表示 typedef struct CSNode ElemType data； struct CSNode * firstchild， *nextsibling； CSNode，*CSTree； 图6.15是图6.13中的树的孩子兄弟链表。利用这种存储结构便于实现各种树的操作，首先易于实现找结点孩子等的操作。例如：若要访问结点x的第i个孩子，只要先从firstchild域找到第

36、1个孩子结 点 ， 然 后 沿 着 孩 子 结 点 的 nextsibling域连续走i-1步，便可找到x的第i个孩子。当然，如果为每个结点增设一个PARENT域，则同样能方便地实现PARENT(T，x)操作。 KFACDEGHBR 6.4.2 森林与二叉树的转换森林与二叉树的转换 由于二叉树和树都可用二叉链表作为存储结构，则以二叉链表作为媒介可导出树与二叉树之间的一个对应关系。也就是说，给定一棵树，可以找到唯一的一棵二叉树与之对应，从物理结构来看，它们的二叉链表是相同的，只是解释不同而已。 图6.16 树与二叉树的对应关系示例 DECBAEDCBAEDCBAADECB树二叉树 对应ABCDE

37、存储存储解释解释 从树的二叉链表表示的定义可知，任何一棵树和对应的二叉树，其右子树必空。若把森林中第二棵树的根结点看成是第一棵树的根结点的兄弟，则同样可导出森林和二叉树的对应关系。例如， 森林与二叉树对应 树与二叉树对应 树根连接DCBAFEJIHGDCBAFEJIHGJIHDCGFEBA 这个一一对应的关系导致森林或树与二叉树可以相互转换，其形式定义如下 一、森林转换成二叉树 如果F=Tl，T2，Tm是森林，则可按如下规则转换成一棵二叉树B=(root，LB，RB)。 (1)若F为空，即m=0，则B为空树； (2)若F非空，即m!=0，则B的根root即为森林中第一棵树的根ROOT(T1)；

38、B的左子树LB是从Tl中根结点的子树森Fl=T11,T12,T1m转换而成的二叉树；其右子树RB是从森林F=T2,T3,Tm转换而成的二叉树。 二、二叉树转换成森林 如果B=(root，LB，RB)是一棵二叉树，则可按如下规则转换成森林F=T1，T2，Tm： (1)若B为空，则F为空； (2)若B非空，则F中第一棵树T1的根ROOT(T1)即为二叉树B的根root；T1中根结点的子树森林F1是由B的左子树LB转换而成的森林；F中除了T1之外其余树组成的森林F=T2，T3，Tm是由B的右子树RB转换而成的森林。 从上述递归定义容易写出相互转换的递归算法。同时，森林和树的操作亦可转换成二叉树的操作

39、来实现。 6.6 赫夫曼树及其应用 赫夫曼(Huffman)树，又称最优树，是一类带权路径长度最短的树。 6.6.1 最优二叉树(赫夫曼树) 首先给出路径和路径长度的概念。从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径，路径上的分支数目称做路径长度。树的路径长度是从树根到每一结点的路径长度之和。6.2.1节中定义的完全二叉树就是这种路径长度最短的二叉树。 若将上述概念推广到一般情况，考虑带权的结点。结点的带权路径长度为从该结点到树根之间的路径长度与结点上权的乘积。树的带权路径长度为树中所有叶子结点的带权路径长度之和，通常记作 n WPL= wklk k=1 假设有n个权值w1,w

40、2,wn，试构造一棵有n个叶子结点的二叉树，每个叶子结点带权为wi，则其中带权路径长度WPL最小的二叉树称做最优二叉树或赫夫曼树。 例如，图6.22中的三棵二叉树，都有4个叶子结点a、b、c、d，分别带权7、5、2、4，它们的带权路径长度分别为 (a)WPL=7*2+5*2+2*2+4*2=36 (b)WPL=7*3+5*3+2*1+4*2=46 (c)WPL=7*1+5*2+2*3+4* 3=35 其中以(c)树的为最小。可以验证，它恰为赫夫曼树，即其带权路径长度在所有带权为7、 5、2、4的四个叶子结点的二叉树中居最小。cbda(c)abdc(b)dcba(a) 利用赫夫曼树可以得到最佳判

41、定算法。 例如，要编制一个将百分制转换成五级分制的程序。显然，此程序很简单，只要利用条件语句便可完成。如： if(a60)b=“bad”； else if(a70) b=“pass”； else if(a80) b=“general”； else if(a90) b=“good”； else b=“excellent”； 这个判定过程可以图6.23(a)的判定树来表示。如果上述程序需反复使用，而且每次的输入量很大，则应考虑上述程序的质量问题，即其操作所需时间。因为在实际生活中，学生的成绩在五个等级上的分布是不均匀的。假设其分布规律如下表所示： 分数 0-5960-69 70-79 80-899

42、0-100比例数 0.05 0.15 0.40 0.30 0.10 则80以上的数据需进行三次或三次以上的比较才能得出结果。假定以5，15，40，30和 10为权构造一棵有五个叶子结点的赫夫曼树，则可得到如图6.23(b)所示的判定过程，它可使大部分的数据经过较少的比较次数得出结果。 图6.23(a) (b)A60A70A80A90良好优秀中等及格不及格YYYYNNNNa6060=a7080=a9070=a80良好中等及格优秀不及格YYNYNNNY 但由于每个判定框都有两次比较，将这两次比较分开，我们得到如图6.23(c)所示的判定树，按此判定树可写出相应的程序。假设现有10000个输入数据，

43、若按图6.23(a)的判定过程进行操作，则总共需进行31500次比较；而若按图6.23(c)的判定过程进行操作，则总共仅需进行22000次比较。 (c)A60A70A80A1时，其余结点可分为m(m0)个互不相交的有限集T1，T2，Tm，其中每一个集合本身又是一棵树，并且称为根的子树子树(SubTree)。 2.2 树的特性及表示方式 树的结构定义是一个递归的定义，即在树的定义中又用到树的概念，它道出了树的固有特性。 树是以分支关系定义的层次结构。 树中除根结点外其它结点都由一个分支引入，而每个结点可有至多个分支，因此树中除根结点无前趋结点外，其它结点都只有一个直接前趋结点，但可有至多个直接后

44、继结点。显然数是一种非线性的结构。 树有多种表示形式，如：树形表示法、嵌套集合表示法、凹入式表示法、广义表表示法。.3 树的相关术语结点结点的度树的度叶子结点双亲结点孩子结点兄弟结点树的深度（高度）路径路径长度树的路径长度祖先结点子孙结点有序树森林 2.4 二叉树的定义和它的五种形态 二叉树(BinaryTree)是一种树型结构，它的特点是每个结点至多只有二棵子树(即二叉树中不存在度大于2的结点)，并且，二叉树的子树有左右之分，其次序不能任意颠倒。 五种形态为空二叉树、只有一个根结点的二叉树、右子树为空的二叉树、左子树为空的二叉树、左右子树非空的二叉树。 2.5 二叉树的性质 熟练掌握二叉树的

45、结构特性，掌握完全二叉树和满二叉树的定义，了解相应的证明方法。 性质性质1 在二叉树的第i层上至多有2i-1个结点(i1)。 性质性质2 深度为k的二叉树至多有2k-1个结点，(k1)。 性质性质3 对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。 性质性质4 具有n个结点的完全二叉树的深度为 log2n +1。 性质性质5 如果对一棵有n个结点的完全二叉树(其深度为log2n+1)的结点按层序编号(从第1层到第log2n+1层，每层从左到右)，则对任一结点i(1in)，有 (1)如果i=1，则结点i是二叉树的根，无双亲；如果i1，则其双亲PARENT(i)

46、是结点 i/2 。 (2)如果2in，则结点i无左孩子(结点i为叶子结点)；否则其左孩子LCHILD(i)是结点2i。 (3)如果2i+1n，则结点i无右孩子；否则其右孩子RCHILD(i)是结点2i+1。 2.7 遍历二叉树和线索二叉树 遍历二叉树是二叉树各种操作的基础。实现二叉树遍历的各种算法与所采用的存储结构有关。不仅要熟练掌握各种遍历策略的递归和非递归算法，了解递归过程中栈的作用和状态，而且能灵活运用遍历算法实现二叉树的其他操作。 理解二叉树线索化的实质是建立结点与其在相应序列中的前驱或后继之间的直接联系，熟悉掌握二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。二叉

47、树的线索化过程是基于对二叉树进行遍历，而线索二叉树上的线索又为相应的遍历提供了方便。2.8 树的存储结构及与二叉树的转换 熟悉树的各种存储结构（双亲表示法 、孩子表示法、孩子兄弟表示法）及其特点，因为树和二叉树都可以用二叉链表表示，则以二叉链表为媒介很容易导出树与二叉树之间的对应关系。掌握树和森林与二叉树的转换方法。建立存储结构是其它操作的前提，因此应掌握1至2种建立二叉树和树的存储结构方法（双亲表示法、孩子表示法、孩子兄弟表示法）。2.9 森林与二叉树的转换（略） 2.10 树和森林的遍历 树与森林的先根序遍历结果与对应的二叉树的先序序列相同，后根序遍历与对应二叉树的中序序列相同。2.11 最优二叉树（哈夫曼树）的概念 树的带权路径长度为树中所有叶子结点的带权路径长度之和，通常记作WPL，带权路径长度W