CH6 树和二叉树 6.1 树的定义和基本术语 6.2 二叉树 6.3 遍历二叉树和线索二叉树 6.4 树和森林 6.5 树的遍历算法的应用举例 6.6 赫夫曼树及其应用 2002-10-11

教学内容 树和二叉树是一类具有层次或嵌套关系的非线性结构，被广泛地应用于计算机领域，尤其是二叉树最重要、最常用。 本章着重介绍了: 二叉树的概念、性质和存储表示； 二叉树的三种遍历操作 线索二叉树的有关概念和运算。 森林和二叉树之间的转换； 树的三种存储表示方法； 树和森林的遍历方法。 最后讨论了最优二叉树(哈夫曼树)的概念及其应用

教学目标 熟悉树和二叉树的递归定义，有关的术语及基本概念； 熟练掌握二叉树的性质，了解相应的证明方法； 熟练掌握二叉树的两种存储方法，特点及适用范围； 不仅要熟练掌握各种次序的遍历算法，而且还要能灵活运用遍历算法实现二叉树的其它各种运算； 了解二叉树线索化及其实质 熟练掌握树、森林与二叉树之间的转换方法； 了解最优二叉树的特性，掌握建立最优二叉树和哈夫曼编码的方法。

引言： 树型结构是一类重要的非线性结构。树型结构是结点之间有分支，并且具有层次关系的结构，它非常类似于自然界中的树。 树结构在客观世界国是大量存在的，例如家谱、行政组织机构都可用树形象地表示。 树在计算机领域中也有着广泛的应用： 在编译程序中，用树来表示源程序的语法结构； 在数据库系统中，可用树来组织信息； 在分析算法的行为时，可用树来描述其执行过程。 ……

6.1 树的定义和基本术语 1.树的定义： 树是由n（n≥0）个结点组成的有限集合。若n＝0，称为空树；若n＞0，则： 有一个特定的称为根（root）的结点。它只有直接后继，但没有直接前驱； 除根结点以外的其它结点可以划分为m（m≥0）个互不相交的有限集合T1，T2，…，Tm，每个集合Ti（i ＝ 1,2,…,m）又是一棵树，称为根的子树，每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。 由此可知，树的定义是一个递归的定义，即树的定义中又用到了树的概念。

root T3 T2 T1

6.1 树的定义和基本术语 2.树的基本术语 树的结点 结点的度 树的度： 结点的层次 树的高度（深度） 一个结点包含子树的数目，称为该结点的度。 孩子结点：若结点X有子树，则子树的根结点为X的孩子结点，也称为孩子，儿子，子女等。度为0的结点，称为叶子结点或树叶，也叫终端结点除叶子结点外的所有结点，为分枝结点，也叫非终端结点 树的结点 包含一个数据元素，和若干指向其子树的分支。 孩子、双亲、兄弟、祖先、堂兄弟 结点的度 树叶（叶子） 分枝结点 树的度： 树中结点度的最大值称为树的度。 结点的层次 树的高度（深度） 双亲结点：若结点X有子女Y，则X为Y的双亲结点。

6.1 树的定义和基本术语 3.树的抽象数据类型定义 ADT Tree{ 数据对象D：由n个具有相同特性的元素构成的集合 数据关系R： 若|D|＝1，则R为空关系；

否则 R＝{H}，H是如下的二元关系： 存在唯一的root∈D,在关系H下无前驱； 若D－{root}非空， 则存在D－{root}的一个划分：{D1，D2，……Dm}（m ＞0), 对任意的i(1≤i≤m）,存在唯一的xi∈D,有< root,xi > ∈H 对应于D－{root}的划分，H－{<root,x1>, <root,x2>,……， <root,xm>}有唯一的划分H1，H2，……Hk（ k＞0）,{Di ,Hi}是一棵符合本定义的树，称为root的子树。

}ADT Tree 基本操作P： InitTree(&T) ； CreateTree(&T,definiton)； Root(T)； Parent(T,cue_e)； LeftChild(T,cur_e)； RightSibling(T,cur_e)； TraverseTree(T,visit())； }ADT Tree

6.1 树的定义和基本术语 4.树的表示方法： （1）树形结构表示法（直观表示法）

（2） 凹入表示法 树的凹入表示法主要用于树的屏幕和打印显示。

（3） 嵌套集合表示法

4.广义表表示法（形式化表示方法）： 小结： （A（B（E（J，K，L），F），C（G），D（H（M），I））） 主要用于树的理论描述 树的表示方法的多样性，正说明了树结构在日常生活中及计算机程序设计中的重要性。 一般来说，分等级的分类方案都可用层次结构来表示，也就是说，都可产生一个树结构。

6.2.1 二叉树的定义 6.2.2 二叉树的性质 6.2.3 二叉树的存储结构 6.2 二叉树 6.2.1 二叉树的定义 6.2.2 二叉树的性质 6.2.3 二叉树的存储结构 二叉树 在树结构的应用中起着非常重要的作用，因为对二叉树的许多操作算法简单，而任何树都可以与二叉树 相互转换，这样就解决了树的存储结构及其运算中存在的复杂性。 2002-10-11

6.2.1 二叉树的定义 1.定义： 2.二叉树的五种基本形态： 二叉树是由n(n≥0)个结点的有限集合构成，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。 2.二叉树的五种基本形态： 6.2.1 二叉树的定义 定义：二叉树是由n(n>=0)个结点的有限集合构成，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。 这也是一个递归定义。二叉树可以是空集合，根可以有空的左子树或空的右子树。二查树不是树的特殊情况，它们是两个概念。

注意： 二叉树的定义也是一个递归定义； 二叉树与树是两个不同的概念，它不是树的特殊情况；这是因为二叉树的子树有左右之分，而树的子树不必区分次序。 二叉树与度为2的有序树也是不同的概念； 对于二叉树的子树而言，要么是根的左子树，要么是根的右子树，即使只有一棵子树也要区分是左是右； 度为2的有序树中，当一个结点有两棵子树时有左右之分，而只有一棵子树时就无左右之分。

问题： 1.只有两个结点的二叉树有几种不同的形态？ 2.只有3个结点的二叉树有几种不同形态？分别画出来。

有0个, 1个, 2个, 3个结点的不同二叉树如下 b0 =1 b1 =1 b2 =2 b3 =5 b4 =14

3.二叉树的抽象数据类型定义 ADT BinaryTree{ 数据对象D：由n个具有相同特性的元素构成的集合 数据关系R： 否则 R＝{H}，H是如下的二元关系： 存在唯一的root∈D,在关系H下无前驱； 若D－{root}非空，则存在D－{root}的一个划分：Dl，Dr分别有xl，xr 使< root,xl >, < root,xr > ∈H 对应于D－{root}的划分Dl，Dr ，有唯一的划分Hl，Hr,{Dl ,Hl}, {Dr ,Hr}分别是一棵符合本定义的二叉树，称为root的左、右子树。

基本操作： InitBiTree(&T) ； CreateBiTree(&T,definition)； Root(T)； Parent(T,e)； LeftChild(T,e); RightChild(T,e); PreorderTraverse(T,visit()); InorderTraverse(T,visit()) ; PostorderTraverse(T,visit()); LevelorderTraverse(T,visit()) }ADT BinaryTree

6.2.2 二叉树的性质 性质1 : 二叉树第i层上至多2i－1个结点（i≥1）。 证明：(采用数学归纳法) ②假设对所有的j(1≤j＜i)命题成立，即第j层上至多2j－1个结点;现证明j＝i时命题仍然成立。 ∵由归纳假设知，二叉树的i－1层至多有2i－2个结点 又由二叉树的定义知，二叉树每个结点的度至多为2 ∴第i层上的最大结点数目 ＝2×第i－1层上的最大结点数目＝2×2i－2 ＝ 2i－1 故j＝i时命题成立 ③根据数学归纳法，命题成立。

性质2： 深度为k的二叉树至多2k－1个结点（k≥1) ＝每层结点的最大数目之和 ＝20＋21＋…＋2k－1 ＝2k－1 两个特殊的二叉树： 满二叉树 完全二叉树 满二叉树：深度为k，且有2k－1个结点的二叉树称为满二叉树。 完全二叉树：对一棵深度为k的有n个结点的二叉树进行１～n编号（从第一层到第k层，每层从左到右）,如果每个结点都与深为k的满二叉树中编号为1 ～ n的结点一一对应，称这棵二叉树为完全二叉树。

1 2 3 4 5 6 7 15 14 13 12 11 10 ９ ８ 深为4的满二叉树 1 2 3 4 5 6 7 12 11 10 ９ ８ 深为4的完全二叉树

思考： 满二叉树与完全二叉树的有何异同点？ 满二叉树一定是一棵完全二叉树，反之完全二叉树不一定是一棵满二叉树。 满二叉树的叶子结点全部在最底层，而完全二叉树的叶子结点可以分布在最下面两层。

性质3 ： 证明： 对任何一棵二叉树T，若其终端结点数目为n0 ，度为2的结点数目为n2，则n0＝n2＋1。 又由于二叉树T中，除根结点以外，每个结点刚好有一个分支指入，设B为分支总数，则 B ＝ n －1 (2) 而二叉树的这些分支是由度为1和度为2的结点产生，则 B＝n1＋ 2 n2 (3) 综上三式，可知n0＝n2＋1成立。

练习： 1.有一棵三叉树，已知度为1,2,3的结点数分别n1,n2,n3,则该三叉树的叶结点数n0为多少？ 2.如果一棵树有n1个度数为1的结点，n2个度数为2的结点，…，nm个度数为m的结点，则终端结点数n0＝ ？ 3.对深为h的一棵满k叉树来说，其终端结点数n0＝?

假设完全二叉树的深度为k，则由性质2和完全二叉树的定义知： 性质4：具有n个结点的完全二叉树的深度为 证明： 假设完全二叉树的深度为k，则由性质2和完全二叉树的定义知： 2k－1 －1 ＜n≤ 2k －1 即： 2k－1 ≤ n＜ 2k 对上式取对数有： 由于k是整数，故

性质5： 对完全二叉树进行编号（按层次从左到右）编号可以反映二叉树结点之间的关系 。（如下图） i i+1 2i 2i＋1 2i＋2 2i＋3 当i＝1,结点i为根结点，无双亲结点，否则其双亲为 ; 若2i＞n,结点i无左子女;否则其左子女为2i; 若2i＋1＞n,结点i无右子女;否则其右子女为2i＋1。

课堂练习 问题1： 问题2： 问题3： 问题4： 什么是二叉树？简述树和二叉树的不同点。 二叉树有哪些基本性质？ 什么是满二叉树和完全二叉树？二者有何区别？ 问题4： 具有n个结点的非空二叉树的最小深度是多少？最大深度是多少？ 答： 二叉树是由n(n≥0)个结点的有限集合构成，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。 树与二叉树是两类不同的树型结构。树中并没有限定每个子树的位置，通常是无序的，即使在有序树中，也只是限定了各子树之间的相对次序，而没有限定子树所在的位置；而二叉树的每个结点至多有两个子树，且每个结点的子树有严格的左、右位置。

6.2.3.二叉树的存储结构 一、二叉树的 顺序存储结构 特点： 用一组连续的存储单元存储二叉树的数据元素， 一、二叉树的 顺序存储结构 特点： 用一组连续的存储单元存储二叉树的数据元素， 必须把二叉树的所有结点安排成为一个恰当的序列，结点在这个序列中的相互位置能反映出结点之间的逻辑关系。 编号的方法 首先对该树中每个结点进行编号，树中各结点的编号应与等深度的满二叉树中对应位置上结点的编号相同，然后以各结点的编号为下标，将各结点的值存储到一维数组的对应下标单元中。

二叉树的顺序存储表示- - - - -- - - #define MAX_TREE_SIZE 100 typedef ElemType SqBiTree[MAX_TREE_SIZE+1]

二叉树的顺序存储示例一 A B C 1 2 3 A B C 1 2 3 1 2 3 4 5 A B C A B # C 1 2 3 4 5

二叉树的顺序存储示例二 1 A 2 B 3 C 4 # 5 D 6 E 7 F 8 9 10 G 11 H

练习： 对如下一棵二叉树采用顺序存储结构，需要添加几个空结点?

小结： 对于完全二叉树来说 二叉树中的结点的编号完全可以反映出该二叉树中结点之间的逻辑关系，可将此类二叉树中结点的编号与数组下标建立一一对应关系，所以采用顺序存储结构较好。 对于一般的二叉树 需要添加 “空”结点，使之成为一棵完全二叉树，此时仍可用顺序存储结构表示这棵二叉树。 但这样可能造成空间浪费，最坏的情况是：深度为k且只有k个结点的单支树，需要长为2k－1的数组空间。 将其每个结点与完全二叉树上的结点完全对应，

6.2.3 二叉树的存储结构 A B C D F E G H 二、 二叉树的链式存储结构 1.结点结构的设计 二叉链表结点结构 6.2.3 二叉树的存储结构 二、 二叉树的链式存储结构 1.结点结构的设计 二叉链表结点结构 三叉链表结点结构 A B C D F E G H 根据二叉树的特点，每个结点有一个双亲（根结点除外）和至多两个称为左、右孩子的结点，因此可设计如下结点结构：

（1） 二叉树的二叉链表存储表示 typedef struct BiTNode{ ElemType data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; rchild data lchild 二叉链表结构

例如： A B C D F E G H

（2） 二叉树的三叉链表存储表示 typedef struct TriBNode{ ElemType data; struct TriBNode *lchild,*rchild,*parent; }TriBNode,*TriBTree; rchild parent data lchild 三叉链表结构

A B C D F E G H

6.3 二叉树的遍历和线索化 6.3.1 遍历二叉树 6.3.2 线索二叉树 2002-10-11

6.3.1 遍历二叉树 引入: 在二叉树的一些应用中，常常要求在树中查找具有某种特征的结点，或者对树中全部结点逐一进行某种处理。这就引入了遍历二叉树的问题，即如何按某条搜索路径巡访树中的每一个结点，使得每一个结点均被访问一次，而且仅被访问一次。 （访问可以是输出、比较、更新、查看元素内容等等各种操作） 遍历对线性结构是容易解决的，而二叉树是非线性的，因而需要寻找一种规律，以便使二叉树上的结点能排列在一个线性序列上，从而便于遍历。 这里提到的“访问”是指对结点施行某种操作，操作可以是输出结点信息，修改结点的数据值等，但要求这种访问不破坏它原来的数据结构。在本书中，我们规定访问是输出结点信息data，且以二叉链表作为二叉树的存贮结构。 这里的访问可以是输出、比较、更新、查看元素内容等等各种操作。

由二叉树的递归定义，二叉树的三个基本组成单元： 根结点（D） 左子树（L） 右子树（R）

6.3.1 遍历二叉树 二叉树的遍历策略： DLR——先（根）序遍历 LDR——中（根）序遍历 LRD——后（根）序遍历 除此以外，常用的遍历策略还有： 层次遍历 假如以L、D、R分别表示遍历左子树、遍历根结点和遍历右子树，遍历整个二叉树则有DLR、LDR、LRD、DRL、RDL、RLD六种遍历方案。若规定先左后右，则只有前三种情况，分别规定为：

一、先序遍历二叉树 操作定义： 例如：右图先序遍历序列： －＋a * b－c d／ef 若二叉树为空，则空操作； 否则： 1.访问根结点 2.先序遍历左子树 3.先序遍历右子树 例如：右图先序遍历序列： －＋a * b－c d／ef

问题： 对应于先序遍历序列为ABC的二叉树有几种形态，分别图示出。 如何实现二叉链表表示的二叉树的先序遍历算法？

void preorder(BiTree T){ if (T){ printf(T->data); 一个简单的先序遍历算法 void preorder(BiTree T){ if (T){ printf(T->data); preorder(T->lchild); preorder(T->rchild); } 算法6.1-1 Status preorder(BiTree T,Status(*visit)(ElemType e)){ if (T) { if (visit(T->data) if ( preorder(T->lchild,visit)) if (preorder(T->rchild,visit)) return OK; return ERROR; } else return OK; }//preorder

二、中序 遍历二叉树 操作定义： 例如：右图中序遍历序列： 若二叉树为空，则空操作； 否则： 1.中序遍历左子树 2.访问根结点 3.中序遍历右子树 例如：右图中序遍历序列： a＋b * c－d－e／f

void inorder(BiTree T){ if (T){ inorder(T->lchild); 一个简单的中序遍历算法 void inorder(BiTree T){ if (T){ inorder(T->lchild); printf(T->data); inorder(T->rchild); } 算法6.1-2 Status inorder(BiTree T,Status(*visit)(ElemType e)){ if (T) { if ( inorder(T->lchild,visit)) if (visit(T->data) if (inorder(T->rchild,visit)) return OK; return ERROR; } else return OK; }//inorder

三、后序遍历二叉树 操作定义： 例如：右图中序遍历序列： abcd－ * ＋ef／－ 若二叉树为空，则空操作； 否则： 1.后序遍历左子树 2.后序遍历右子树 3.访问根结点 例如：右图中序遍历序列： abcd－ * ＋ef／－

void postorder(BiTree T){ if (T){ postorder(T->lchild); 一个简单后序遍历的算法 void postorder(BiTree T){ if (T){ postorder(T->lchild); postorder(T->rchild); printf(T->data); } 算法6.1-3 Status postorder(BiTree T,Status(*visit)(ElemType e)){ if (T) { if ( postorder(T->lchild,visit)) if (postorder(T->rchild,visit)) if (visit(T->data) return OK; return ERROR; } else return OK; }//post order

四、二叉树的建立 A B C D F E G 方法1（按先序序列建立二叉树） 例如：建立如上二叉树的二叉链表结构应输入： Status CreateBiTree(BiTree &T){ scanf(&ch); if (ch==‘#‘) T=NULL; else { if(!(T=(BiTree)malloc(sizeof(BiNode)))) exit OVERFLOW; T->data=ch; CreateBiTree(T->lchild); CreateBiTree(T->rchild); } return OK; }//CreateBiTree 例如：建立如上二叉树的二叉链表结构应输入： ABC##DE#G##F###

两点说明： 1. 按先序次序输入二叉树中结点的值，用'#'表示空树，对每一个结点应当确定其左右子树的值（为空时必须用特定的空字符占位），故执行此程序时，最好先在纸上画出你想建立的二叉树，每个结点的左右子树必须确定，若为空，则用特定字符标出，然后再按先序输入这棵二叉树的字符序列； 2. 为了简化程序的书写量，以及程序的清晰性，对结点的访问以一条输出语句表示，若有更复杂的或多种访问，可以将结点的访问编写成函数，然后通过函数指针进行函数的调用。

四、二叉树的建立 方法二：建立二叉排序树 二叉排序树的定义 或者为一棵空树，或为满足如下条件的二叉树 1.若左子树非空，则左子树上所有结点的值均小于它的根结点的值； 2.若右子树非空，则右子树上所有结点的值均大于它的根结点的值； 3.它的左右子树也分别为二叉排序树。

例如：输入序列{45，12，37，3，53，100，24} 45 12 53 3 37 100 24

void insert(BiTree &T,ElemType x){ if (T==NULL){ T=(BiTree)malloc(sizeof(BiTNode)); T->data=x; T->lchild=T->rchild=NULL; } else{ if (x<T->data) insert(T->lchild,x); if (x>T->data) insert(T->rchild,x); }//insert

void CreateBiTree(BiTree &root){ ElemType x; root=NULL; scanf(&x); while (x){ insert(root,x); }//while }//CreateBiTree

五、二叉树遍历的非递归算法 1. 中序遍历算法的非递归算法一 Status inorder(BiTree T)){ InitStack(S);push(S,T); while (!StackEmpty(S)){ while (GetTop(S,p)&& p) push(S,p->lchild); pop(S,p); if (!StackEmpty(S)){ pop(S,p); visit(p->data); push(S,p->rchild); }//if }//while return OK; }//inorder

A B C D E 中序遍历算法的非递归过程示例 ^ D ^ ^ B B E A A A ^ ^ A C (1) (2)输出D (3)输出B

五、二叉树遍历的非递归算法 A B C D E 2. 中序遍历算法的非递归算法二 Status inorder(BiTree T){ InitStack(S); p=T; while (p||!StackEmpty(S)) { if (p){ push(S,p); p=p->lchild; } else { pop(S,p); visit(p->data)； p=p->rchild; }//while return OK; }inorder A B C D E

六、二叉树的遍历应用举例 例1 ：统计出给定二叉树中结点的数目 int count_n(BiTree T) { if (T==NULL) num=0; else { num1=count_n(T->lchild); num2=count_n(T->rchild); num= num1+num2+1; } return num;

六、二叉树的遍历应用举例 例2 ：统计出给定二叉树中叶子结点的数目 int count_n0(BiTree T) { int num,num1,num2; if (T==NULL) num=0; else if (T->lchild==NULL && T->rchild==NULL) num=1; else { num1=count_n0(T->lchild); num2=count_n0(T->rchild); num= num1+num2; } return num; }

思考： 如何统计给定二叉树中 单分支结点、双分支结的数目。 如何计算给定二叉树的深度？

六、二叉树的遍历应用举例 例3 ： 求二叉树的深度 int tree_depth(BiTree T){ int lh,rh,h; if (T==NULL) h=0; else { lh=tree_depth(T->lchild); rh=tree_depth(T->rchild); if (lh>=rh) h=lh+1; else h=rh+1; } return h;

六、二叉树的遍历应用举例 例4 ： 结点x的查找 Bitree search(BiTree T,ElemType x) { if(T) { if(T->data==x) return T; search(T->lchild,x); /*在左子树中查找*/ search(T->rchild,x); /*在右子树中查找*/ } else return NULL; 查找二叉树bt中的结点x，可以结合在四种遍历算法中的任何一个算法中进行。在此我们以前序遍历来实现查找运算的递归算法。

六、二叉树的遍历应用举例 例5: 交换二叉树的左右子树 void change_left_right(BiTree &T) { 例5: 交换二叉树的左右子树 void change_left_right(BiTree &T) { BiTree temp; if (T) { change_left_right(T->lchild); change_left_right(T->rchild); temp=T->lchild; T->lchild =T->rchild;T->rchild=temp; } 许多操作可以利用三种遍历顺序的任何一种，只是某种遍历顺序实现起来更加方便一些。而有些操作则不然，它只能使用其中的一种或两种遍历顺序。将二叉树中所有结点的左右子树进行交换这个操作就属于这类情况。

6.3.2 线索二叉树 一、分析与设计 二、线索二叉树上如何寻找结点的前驱和后继 三、线索二叉树上实现遍历二叉树（中序） 四、建立线索二叉树（中序） 总之，无论是前序、中序还是后序遍历二叉树，都需要遵循着一个规则，那就是按照一定的规则将二叉树上的结点排列在一个线性队上。这样一棵二叉树有且只有一个开始结点和一个终端结点，其他结点都有且只有一个前驱结点和一个后继结点。为了进一步理解树型结构中的前驱(双亲)结点和后继(孩子)结点的概念，下一节来研究线索二叉树。

一、分析与设计 讨论1： 答: 二叉树遍历的实质是什么？ 将非线性结构进行线性化操作。 对二叉树进行某种遍历之后，将得到一个线性有序的序列。 其中结点具有唯一前驱和唯一后继。

一、分析与设计 讨论2： 答： 如何获得这种“直接前驱”或“直接后继”？有何意义？ 二叉树中容易找到结点的左右孩子信息，但该结点的直接前驱和直接后继只能在某种遍历过程中动态获得。 先依遍历规则把每个结点对应的前驱和后继线索预存起来————“线索化”。 意义：从任一结点出发都能快速找到其前驱和后继，且不必借助堆栈。

一、分析与设计 讨论3：如何预存这类信息？ data lchild rchild fwd bwd 缺点：空间效率太低！

线索二叉树（Threaded Binary Tree） 一、分析与设计 一个结论： 用二叉链表法存储包含n个结点的二叉树，结点的指针域中会有n＋1个空链域。 思考： 二叉链表空间效率这么低，能否利用这些空闲区存放有用的信息或线索？ 解决方案： 我们可以用它来存放当前结点的直接前驱和直接后继等线索，以加快查找速度。 线索二叉树（Threaded Binary Tree）

一、分析与设计 data lchild rchild 方法二： 与原有的左右孩子指针域“复用”，充分利用那n＋1个空链域。 问题：计算机如何判断是孩子指针还是线索指针？ 证明： 用二叉链表存储包含n个结点的二叉树，结点必有2n个链域。 除根结点外，二叉树中每一个结点有且仅有一个双亲，意即每个结点地址占用了双亲的一个直接后继，n个结点地址共占用了n－1个双亲的指针域。也就是说，只会有n－1个结点的链域存放指针。 所以， 空指针数目＝2n－(n＋1)＝n＋1个。

一、分析与设计 线索二叉树的二叉线索存储表示 lchild ltag data rtag rchild typedef enum {Link,Thread} PointerTag; typedef struct BiThrNode{ ElemType data; struct BiThrNode *lchild,*rchild; PointerTag ltag,rtag; }BiThrNode,*BiThrTree

二、几种线索二叉树 中序线索二叉树 a＋b×c－d－e／f 问题： ＋ a e b － ／ × f c d 如何寻找结点的后继 rtag＝1 如何寻找结点的前驱 ltag＝1 ltag＝0 ＋ a e b － ／ × f c d NULL NULL

二、几种线索二叉树 H D G A C F B E 后序线索二叉树 后序遍历序列：ABCDEFGH 问题： 如何寻找结点的后继 若x为根结点 如何寻找结点的前驱？

三、中序线索二叉树的建立与遍历 （一）建立 ＋ a e b － ／ × f c d thrt 基本思想: 附加设置一个头结点thrt 如图所示： 带头结点的双向线索链表 算法描述 ＋ a e b － ／ × f c d

Status InorderThreading(BiThrTree &Thrt,BiThrTree T){ if (!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode))) exit（ OVERFLOW）; Thrt->ltag=0;Thrt->rtag=1;Thrt->rchild=Thrt if (!T) Thrt->lchild=Thrt; else { Thrt->lchild=T;pre=Thrt; InThreading(T); pre->rchild=thrt;pre->rtag=1; Thrt->rchild=pre; } return OK; }//InorderThreading

四、中序线索二叉树的建立 void InThreading(BiThrTree p){ if (p){ InThreading(p->lchild); if (!p->lchild) { p->ltag=1;p->lchild=pre;} if (!pre->rchild) {pre->rtag=1;pre->rchild=p;} pre=p; InThreading(p->rchild); } }// InThreading

三、中序线索二叉树的遍历 Status InOrderTraverse_Thr(BiThrTree Thrt){ p=Thrt->lchild; while (p!=Thrt){ while (p->ltag==0) p=p->lchild; visit(p->data;) while (p->rtag==1&&p->rchild!=Thrt){ p=p->rchild; visit( p->data); } p=p->rchild; }//while Return OK; }// InOrderTraverse_Thr

6.4.1 树的存储结构 6.4.2 森林和树的转换 6.4.3 森林和树的遍历 6.4 树和森林 6.4.1 树的存储结构 6.4.2 森林和树的转换 6.4.3 森林和树的遍历 2002-10-11

一、双亲表示法 二、孩子表示法 1.多重链表结点结构 2.孩子链表法 三、孩子兄弟表示法 6.4.1 树的存储结构 一、双亲表示法 二、孩子表示法 1.多重链表结点结构 2.孩子链表法 三、孩子兄弟表示法 2002-10-11

一、双亲表示法 下标 data parent R -1 1 A 2 B 3 C 4 D 5 E 6 F 7 G 8 H 9 K 1 2 3 R -1 1 A 2 B 3 C 4 D 5 E 6 F 7 G 8 H 9 K 1 2 3 4 5 6 7 8 9 R A C D E F G H K B

一、双亲表示法 #define MAX_TREE_SIZE 100 typedef struct PTNode{ ElemType data; int parent; }PTNode; typedef struct { PTNode nodes[MAX_TREE_SIZE+1]; int n; }Ptree;

二、孩子表示法 1、多重链表结点结构 data child1 …… Childd (d为树的度） 结点结构1 优点：树中的结点是同构的，操作方便； 缺点：有较多的空链域，造成空间浪费 （有n（k－1）＋1个空链域）。

二、孩子表示法 1、多重链表结点结构 data child1 …… Childd (d为结点的度） 结点结构2 缺点：树中的结点是不同构的，操作不方便； 优点：节约存储空间。

4 5 6 1 2 3 9 8 7 K H G F E D C B A R R A C D E F G H K B 2.孩子链表法 4 ^ 5 6 1 2 3 9 8 7 K H G F E D C B A R firstchild data next child 结点结构 R A C D E F G H K B 1 2 3 4 5 6 7 8 9

C 三、孩子兄弟表示法（树的二叉链表存储） R A D E F G H K B 存储结构表示： D ^ C E F H K R A B firstchild data nextsibling R A C D E F G H K B

6.4.2 树、森林与二叉树的转换 一、树和二叉树的转换 R A B C D E F G H K R A C D E F G H K B

讨论1：树转二叉树： 讨论2：二叉树怎样还原为树？ 加线——兄弟相连 抹线——长兄为父 旋转——孩子靠左 要点：逆操作，把所有右孩子变为兄弟！

二、森林《 ==〉树〈==》二叉树 A B D C E F G H J I A G B D H J I C E F G H J I E F

6.4.3 树和森林的遍历 问：树的先根遍历与对应二叉树的遍历有何关系？ 一、树的遍历 C C 1. 先根遍历： 若树为空，则空操作 否则 访问树的根结点 依次先根遍历每棵子树 例：右图所示树的先根遍历序列： R A C D E F G H K B R A B C D E F G H K 树的先根遍历可借用二叉树的先序遍历的算法实现。 RADEBCFGHK 问：树的先根遍历与对应二叉树的遍历有何关系？

问题：树的后根遍历与对应二叉树的遍历有何关系？ R A C D E F G H K B R A B C D E F G H K 2.后根遍历 若树为空，则空操作 否则 依次后根遍历每棵子树 访问树的根结点 例：右图所示树的后根遍历序列： 树的后根遍历可借用二叉树的中序遍历的算法实现。 DEABGHKFCR 问题：树的后根遍历与对应二叉树的遍历有何关系？

二、森林的遍历 ABCDEFGHIJ 问：森林的先序遍历与对应二叉树的遍历有何关系？ A G B D H J I C E F 1.先序遍历森林 若森林为空，则空操作； 否则： 访问第一棵树的根结点 先序遍历第一棵树中根结点的子树森林 先序遍历除去第一棵树后余下的树构成的森林 例：如图所示森林的先序遍历序列为： 森林的先序遍历可借用对应二叉树的先序遍历的算法实现。 ABCDEFGHIJ 问：森林的先序遍历与对应二叉树的遍历有何关系？ 答：相当于对对应的二叉树进行先序遍历。

问：森林的中序遍历与对应二叉树的遍历有何关系？ A G B D H J I C E F A B D C E F G H J I 2.中序遍历森林 若森林为空，则空操作， 否则： 中序遍历第一棵树根结点的子树森林 访问第一棵树的根结点 中序遍历除第一棵树后余下的树构成的森林 例：下图所示森林的中序遍历序列为： 森林的中序遍历可借用对应二叉树的中序遍历的算法实现。 BCDAFEHJIG 问：森林的中序遍历与对应二叉树的遍历有何关系？ 答：相当于对对应的二叉树进行中序遍历

6.5 应用举例 例1： 分析： 由二叉树的先序序列和中序序列建立该二叉树。 若二叉树的任意两个结点的值都不相同，则二叉树的前序序列和中序序列能唯一确定一棵二叉树。 另外，由前序序列和中序序列的定义可知，前序序列中第一个结点必为根结点，而在中序序列中，根结点刚好是左、右子树的分界点。 因此，可按如下方法建立二叉树：

步骤如下： 1.用前序序列的第一个结点作为根结点; 2.在中序序列中查找根结点的位置，并以此为界将中序序列划分为左、右两个序列(左、右子树); 3.根据左、右子树的中序序列中的结点个数，将前序序列去掉根结点后的序列划分为左、右两个序列，它们分别是左、右子树的前序序列; 4.对左、右子树的前序序列和中序序列递归地实施同样方法，直到所得左、右子树为空。

例如： 假设前序序列为ABDGHCEFI，中序序列为GDHBAECIF，试建立这棵二叉树。

6.5 应用举例 A B C D F E G H 例2： 层次遍历二叉树 定义： 二叉树的层次遍历算法： 对于一棵二叉树，若规定遍历顺序为从上到下(上层遍历完才进入下层)，从左到右(同一层从左到右进行）这样的遍历称为按层次遍历。 二叉树的层次遍历算法： 分析： 过程示例 A B C D F E G H

void LevelOrder(BiTree T){ //按层次遍历二叉树T， Q为队列 InitQueue(Q); if (T){ // 若树非空 EnQueue(Q,T); //根结点入队列 While (!QueueEmpty(Q)){ DeQueue(Q,b); //队首元素出队列 visit(b->data); //访问结点 if (b->lchild) EnQueue(Q,b->lchild); //左子树非空，则入队列 if (b->rchild) EnQueue(Q,b->rchild);//右子树非空，则入队列 }//while }//if }LevelOrder

6.5 应用举例 例3:火车调度问题 问题描述： 有一个火车调度站如下图所示 分析： 树的搜索问题 车站 出口 入口 1,2,3,4,5

6.6.1 最优二叉树（ Huffman树） 定义 构造过程 应用 6.6.2 赫夫曼编码 6.6 赫夫曼树及其应用 6.6.1 最优二叉树（ Huffman树） 定义 构造过程 应用 6.6.2 赫夫曼编码 2002-10-11

6.6.1 最优二叉树 一、基本概念 1.结点的路径长度 2. 树的路径长度：树中结点的路径长度之和。 3．结点的权及带权路径长度 6.6.1 最优二叉树 一、基本概念 1.结点的路径长度 2. 树的路径长度：树中结点的路径长度之和。 3．结点的权及带权路径长度 若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。 结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。 4．树的带权路径长度（WPL） 树的带权路径长度规定为所有叶子结点的带权路径长度之和。 在一棵树中，从一个结点往下可以达到的孩子或子孙结点之间的通路，称为路径。通路中分支的数目称为结点的路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。

c 4.最优二叉树(Huffman树）(P144) 例如： 2 4 7 5 b 7 5 2 4 7 5 4 a 2 例如(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 4.最优二叉树(Huffman树）(P144) 4.最优二叉树(Huffman树）：给定n个权值{w1,w2,…，wn},构造一棵有n个结点的二叉树，使每个叶结点带权为wi，则其中带权路径长度WPL最小的二叉树称为最优二叉树。

二、应用（最佳判定算法）P144 分数 0~59 60~69 70~79 80~89 90~100 比例数 0.05 0.15 0.40 0.30 0.10 （a）WPL=0.05 ×1＋0.15×2＋ 0.40×3＋0.30 ×4＋0.10 ×4=3.15 对10000个成绩，则总共需要31500次比较。 （b）WPL=0.05 ×4＋0.15×3＋ 0.40×1＋0.30 ×2＋0.10 ×4=2.05 对10000个成绩，则总共需要20500次比较。 （c）WPL=0.05 ×3＋0.15×3＋ 0.40×2＋0.30 ×2＋0.10 ×2=2.20 对10000个成绩，则总共需要22000次比较。

三、构造哈夫曼树 1.根据给定的n个权值{w1,w2,……,wn}构成n棵二叉树的集合F ＝{T1，T2，…，Tn),其中每棵二叉树Ti中只有一个带权为wi的根结点，其左右子树为空。 2.在F中选择两棵根结点权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为左、右子树上根结点的权值之和。 3.在F中删除这两棵树，同时将新得到的二叉树加入F中。 4.重复第2、3步，直到F中只含一棵树为止。 这棵树就是哈夫曼树。

例1：以{7，5，2，4}为权值集合构造哈夫曼树。 （4） 2 4 5 7 6 11 18 （1） 2 4 5 7 （2） 2 4 5 7 6 （3） 2 4 5 7 6 11

例2：以{5，15，40，30，10}为权值集合构造哈夫曼树。 60 （4） （1） 40 30 15 5 10 5 10 15 （2） 40 30 5 10 15 40 30 60 （5） 100 （3） 5 10 15 40 30

练习： 以｛3,5,6,7,9,12｝为权值构造一棵Huffman树，并计算它的WPL。

6.6.2 哈夫曼编码 一、远程通信的基本过程与要求 发送端（编码） 接收端（译码） 要求： (1) 收发的速度快，即电文编码尽可能短； 6.6.2 哈夫曼编码 一、远程通信的基本过程与要求 发送端（编码） 接收端（译码） 信道 要求： (1) 收发的速度快，即电文编码尽可能短； (2) 接收端译码时不产生二义性的译码。 等长编码 不等长编码（前缀码）

解决方案： c d b a 7 5 2 4 (1)利用二叉树来设计二进制的前缀码； 如右图：a----0 b---10 (2)设计总电文最短的前缀码： 假定以每种字符的出现次数或出现频率为wi，编码长度为li，电文中共有n种字符，则电文编码总长度为： 即求以n种字符的频率为权，设计一棵Huffman树的问题，对应的编码称为Huffman编码。

weight parent lchild rchild 二、算法实现 1.有n个叶结点的Huffman树中共有m＝2n－1个结点，可将这些结点存储在一个一维数组中。 结点结构 weight parent lchild rchild typedef struct{ unsigned int weight; unsigned int parent,lchild,rchild; }HTNode,*HuffmanTree; 2.可以采用动态分配的一维数组存储编码表。 typedef char ** HuffmanCode;

算法1 Huffman编码 void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int w[ ],int n){ if ( n<=1) return ; m=2*n-1; HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); for (i=1;i<=m;i++) if (i<=n) HT[i]={w[i],0,0,0}; else HT[i]={0,0,0,0}; for (i=n+1;i<=m;i++) {//建立Huffman树 Select(HT,i-1,s1,s2); HT[s1].parent=i; HT[s2].parent=i; HT[i].lchild=s1; HT[i].rchild=s2; HT[i].weight= HT[s1].weight+ HT[s2].weight; }

//求叶到根逆向求每个字符的Huffman编码 HC=(HuffmanCode)malloc((n+1)*sizeof(char*)); cd=(char*)malloc(n*sizeof(char)); cd[n-1]=‘\0’; for (i=1;i<=n;i++) {start=n-1; for (c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent) if (HT[f].lchild==c) cd[- -start]=‘0’; else cd[--start]=‘1’ HC[i]=(char*)malloc((n-start)*sizeof(char)); strcpy(HC[i],&cd[start]); } free(cd); }//HuffmanCoding

算法2 Huffman译码 void HuffmandeCoding(HuffmanTree HT,int n){ m=2*n-1; i=m; while ((c=getchar())!=‘\n’){ if (i<=n){ printf(HT[i].data); i=m;} if (ch==‘0’) i=HT[i].lchild; else i=HT[i].rchild; }//while }// HuffmandeCoding

例1：以{7，5，2，4}为权值集合构造哈夫曼树。 weight parent lchild rchild 1 7 2 5 3 4 - 6 （1） 2 4 5 7 1 3

weight parent lchild rchild 1 7 2 5 3 4 6 - （2） 2 4 5 7 6 1 3

weight parent lchild rchild 1 7 2 5 6 3 4 11 - （3） 2 4 5 7 6 11 1 3

7 5 6 11 18 2 4 5 7 6 11 18 1 2 3 4 weight parent lchild rchild （4） 1 2 5 6 3 4 11 18 （4） 2 4 5 7 6 11 18 1 3

三、例6-2（p148) 1.HT的初态 5 29 7 8 14 23 11 weight parent lchild rchild 1 5 2 29 3 7 4 8 14 6 23 11 9 - 10 12 13 15 1.HT的初态 5 1 29 2 7 3 8 4 23 6 11 14

2.HT的终态 5 3 14 8 11 15 29 58 19 42 23 100 weight parent lchild rchild 2 29 14 3 7 10 4 8 12 6 23 13 11 15 19 42 58 100 5 1 3 7 14 8 4 11 9 15 10 29 2 12 58 19 42 13 23 6 100

本章小结 第6章结束 树 森林 先序遍历 后序遍历 孩子--兄弟 存储结构 遍历 1.定义和性质 顺序结构 2.存储结构 二叉链表 链式结构 二叉树 森林 顺序结构 链式结构 2.存储结构 二叉链表 三叉链表 中序遍历 后序遍历 先序遍历 层次遍历 3.遍历 遍历 Huffman树 应用 要求熟悉树和二叉树的定义和有关术语； 理解和记住二叉树的性质； 熟练掌握二叉树的顺序存储结构和链式存储结构。 遍历二叉树是二叉树中各种运算的基础，希望能灵活运用各种次序的遍历算法，实现二叉树的其他运算。 二叉树的线索化，目的是加速遍历过程和有效利用存储空间，希望熟练掌握。 并能掌握： 树和二叉树之间的转换方法，存储树的双亲表示法、孩子表示法和孩子兄弟法。 最后，对树和森林的遍历、最优二叉树的特性，建议读者要理解。 先序线索树 中序线索树 后序线索树 先 序 遍 历 中 4.线索化 线索二叉树 Huffman编码

习题 一、判断题 1.二叉树是树的特殊形式。 2.一棵度为2的树就是一棵二叉树。 3.由树转换成二叉树，其根结点的右子树总是空的。 4.如果结点A有3个兄弟，而且B是A的双亲，则B的度是5。 5.给定二叉树的先序遍历序列和后序遍历序列，就能惟一地确定一棵二叉树。 6.哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。

二、填空题 1.对于一个具有n个结点的二叉树，当它为一棵_________二叉树时，具有最小高度，即为_________，当它为一棵单支树时具有具有最大高度，即为_________。 2.对于一个具有n个结点的二叉树，当它存储在二叉链表中时，其指针字段的总数为_________个，其中_________个用于链接孩子结点，_________个空闲。 3.一棵深度为k的满二叉树的结点总数为___________，一棵深度为k的完全二叉树的结点总数的最小值为___________，最大值为___________。 4. 由三个结点构成的二叉树，共有_________种不同的结构。

5. 设深度为k的二叉树上只有度为0或度为2的结点，则这类二叉树上所含结点总数至少为_____。 6.具有n个结点的完全二叉树，若按层次从上到下、从左到右对其编号(根结点为1号)，则编号最大的分支结点序号为_______，编号最小的分支结点序号为_______，编号最大的叶子结点序号为________，编号最小的叶子结点序号为________。 7.有m个叶子结点的哈夫曼树，其结点总数为_______。 8.某二叉树的前序遍历结点访问顺序为ABDGCEFH，中序遍历结点访问顺序为DGBAECHF，则其后序遍历结点访问顺序为_____。

三、 简答题 1. 遍历序列具有如下特点的二叉树具有什么特征？（注意：二叉树至少有两个结点） 先序序列和后序序列正好相反 三、 简答题 1. 遍历序列具有如下特点的二叉树具有什么特征？（注意：二叉树至少有两个结点） 先序序列和后序序列正好相反 先序序列和中序序列正好一致 中序序列和后序序列正好一致 中序序列是一个有序序列 2.具有3个结点的树和3个结点的二叉树的有多少种不同形态，请分别画出来。

3. 已知一棵二叉树的中序序列和后序序列分别为BDCEAFHG和DECBHGFA，画出这棵二叉树。 4.对于权值W＝{14，15，7，4，20，3}，试给出相应的哈夫曼树，并计算其带权长度。