第六章 树和二叉树 学习要点 理解树的定义和基本术语，重点了解二叉树的定义、性质、存储结构； 掌握二叉树遍历的递归算法及它的典型运算； 第六章 树和二叉树 学习要点 理解树的定义和基本术语，重点了解二叉树的定义、性质、存储结构； 掌握二叉树遍历的递归算法及它的典型运算； 理解线索化二叉树的特性以及寻找某结点的前驱和后继的方法； 理解树、森林和二叉树间的相互转换规则； 掌握哈夫曼树的实现方法，理解构造哈夫曼编码及带权路径长度的计算。

6.1 树的定义和基本术语 一、树的定义及相关术语 1．树的定义 树形结构是一种重要的非线性结构，讨论的是层次和分支关系。 　　树形结构是一种重要的非线性结构，讨论的是层次和分支关系。 定义：树(Tree)是由n（n≥0）个有限数据元素的集合，当集合为空时称为空树，否则它满足如下两个条件： （1）有且仅有一个特定的称为根(Root)的结点； （2）其余的结点可分为m(m>=0)个互不相交的子集T1,T2,T3…Tm，其中每个子集又是一棵树，并称其为子树(Subtree)。每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。 由此可知，树的定义是一个递归的定义，即树的定义中又用到了树的概念。

Ø （a）空树 （b）仅含有根结点的树 （c） 含有多个结点的树 T={A, B,C,D, E, F, G, H, I, J,K,L,M} 　　T1={B, E, F, K, L} , T2={C, G} , T3={D, H, I, J, M} 这些集合中的每一集合都本身又是一棵树，它们是A的子树。 　例如，对于T1，B是根，其余结点可以划分为2个互不相交的集合： 　　T11={E,K,L}，T12={F}，T11,T12 是B 的子树。

从逻辑结构看： 1）树中只有根结点没有前趋； 2）除根外，其余结点都有且仅一个前趋； J I A C B D H G F E K L M 从逻辑结构看： 1）树中只有根结点没有前趋； 2）除根外，其余结点都有且仅一个前趋； 3）树的结点，可以有零个或多个后继； 4）除根外的其他结点，都存在唯一条从根到该结点的路径； 5）树是一种分枝结构 （除了一个称为根的结点外）每个元素都有且仅有一个直接前趋，有且仅有零个或多个直接后继。

2．树的应用 1）树可表示具有分枝结构关系的对象 例1 家族族谱 例1 家族族谱 设某家庭有13个成员A、B、C、D、E、F、G、H、I、J、K、L、M他们之间的关系可下图所示的树表示： J I A C B D H G F E K L M

2）树是常用的数据组织形式 有些应用中数据元素之间并不存在间分支结构关系，但是为了便于管理和使用数据，将它们用树的形式来组织。 例3 计算机的文件系统 不论是Linux文件系统还是Windows文件系统，所有的文件是用树的形式来组织的。 文件夹1 文件夹n 文件1 文件2 文件夹11 文件夹12 文件11 文件12 /

3．树的逻辑结构描述 一棵树的逻辑结构可以用二元组描述为： 　　tree =(k,R) 　　　k={ki∣1≤i≤n;n≥0,kielemtype} 　　R={r} 其中，k是n个具有相同特性的数据元素的集合;n为树中结点个数，若 n=0，则为一棵空树， n> 0时称为一棵非空树，而关系 r 应满足下列条件： （1）有且仅有一个结点没有前驱,称该结点为树根; （2）除根结点以外,其余每个结点有且仅有一个直接前驱; （3）树中每个结点可以有多个直接后继(孩子结点)。 　　例如，对上图中的树结构,可以二元组表示为： 　　K={A，B，C，D，E，F，G，H，I，J，K，L，M} 　　r={(A,B)，(A,C)，(A,D)，(B,E)，(B,F)，(C,G)，(D,H)， 　　　(D,I)，(D,J)，(E,K)，(E,L)，(H,M)}

4． 基本术语 1. 结点：指树中的一个数据元素，一般用一个字母表示。 2. 度：一个结点包含子树的数目，称为该结点的度。 　　树中结点度的最大值称为树的度。 3. 树叶（叶子）：度为0的结点，称为叶子结点或树叶，也叫终端结点。 4. 孩子结点：若结点X有子树，则子树的根结点为X的孩子结点，也称为孩子，儿子，子女等。如图6-1（c）中A的孩子为B，C，D。 5. 双亲结点：若结点X有子女Y，则X为Y的双亲结点。 6. 祖先结点：从根结点到该结点所经过分枝上的所有结点为该结点的祖先，如图6-1（c）中M的祖先有A，D ，H 。 7. 子孙结点：某一结点的子女及子女的子女都为该结点子孙。 8. 兄弟结点：具有同一个双亲的结点，称为兄弟结点。

9. 分枝结点：除叶子结点外的所有结点，为分枝结点，也叫非终端结点。 10. 层数：根结点的层数为1，其它结点的层数为从根结点到该结点所经过的分支数目再加1。 11. 树的高度（深度）：树中结点所处的最大层数称为树的高度，如空树的高度为0，只有一个根结点的树高度为1。 12. 有序树 ：若一棵树中所有子树从左到右的排序是有顺序的，不能颠倒次序。称该树为有序树。 13. 无序树： 若一棵树中所有子树的次序无关紧要，则称为无序树。 14. 森林（树林）： 若干棵互不相交的树组成的集合为森林。一棵树可以看成是一个特殊的森林。

5． 树的基本操作 (1) inittree(T) 初始化树T。 (2) root(T) 求树T的根结点。 (3) parent(T,x) 求树T中，值为x的结点的双亲。 (4) child(T,x,i) 求树T中，值为x的结点的第i个孩子。 (5) addchild(y,i,x) 把值为x的结点作为值为y的结点的第i个孩子插入到树中。 (6) delchild(x,i) 删除值为x的结点的第i个孩子。 (7) traverse(T) 遍历或访问树T。

6.2 二叉树 　　树是一种分枝结构的对象，在树的概念中，对每一个结点孩子的个数没有限制，因此树的形态多种多样，本章我们主要讨论一种最简单的树——二叉树。 　　二叉树是一种重要的树形结构，但不是前面所介绍的“树”的特例。因为二叉树既不是只有两个子树的树，也不是最多有两个子树的树。另外树和二叉树操作也有不相同的地方。

φ 6.2.1 二叉树的定义 1．二叉树 二叉树： 或为空树，或由根及两颗不相交的左子树、右子树构成，并且左、右子树本身也是二叉树。 　　二叉树： 或为空树，或由根及两颗不相交的左子树、右子树构成，并且左、右子树本身也是二叉树。 　　当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个结点。 A F G E D C B φ 说明 1）二叉树中每个结点最多有两颗子树；二叉树每个结点度小于等于2; 2）左、右子树不能颠倒——有序树; 3）二叉树是递归结构，在二叉树的定义中又用到了二叉树的概念;

(a)、(b)是不同的二叉树， (a)的左子树有四个结点， F G E D C B A G E D B C F (a) (b) (a)、(b)是不同的二叉树， (a)的左子树有四个结点， (b)的左子树有两个结点， 二叉树、树及有序树的区别 　　从定义上看，二叉树既不是只有两个子树的树，也不是最多只有两个子树的树。它们主要差别在于二叉树的子树有左右之分。在有序树中，虽然一个结点的孩子之间是有左右次序的，但若该结点只有一个孩子时，就无须区分其左右次序。而在二叉树中，即使是一个孩子也有左右之分。

二叉树的基本形态 φ (a)空树 (b)仅有根 (c) 右子树空 (d)左子树空 (e)左、右子树均在

2．二叉树的相关概念 　　结点、 度、 树叶（叶子）、 孩子结点、 双亲结点、 祖先结点、 子孙结点、 兄弟结点、分枝结点、 层数、 树的高度（深度） 满二叉树 　　在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都集中在树的最下一层，这样的一棵二叉树称作满二叉树。满二叉树的特点是每一层的结点数都达到最大值，即对深度为k的满二叉树，有2k-1个结点。 A A B C B C E F G H G H k=3的满二叉树 非满二叉树

完全二叉树 　　如果一颗二叉树只有最下一层结点数可能未达到最大，并且最下层结点都集中在该层的最左端，则称为完全二叉树； 　　其特点是：叶子结点只能出现在最下层和次下层，也就是说至多是最下面的两层上结点的度数可以小于2，且最下层的叶子结点集中在树的左部。显然，一棵满二叉树必定是一棵完全二叉树，而完全二叉树未必是满二叉树。 A A A B C B C B C E F G H E F E F H (a) (b) (c) (a)、(b)完全二叉树 (c)不是完全二叉树

6.2.2 二叉树的主要性质 性质1 在二叉树的第i层上最多有2i-1个结点 性质2 深度为k的二叉树最多有2k-1个结点 A F G E D C B 6.2.2 二叉树的主要性质 性质1 在二叉树的第i层上最多有2i-1个结点 性质2 深度为k的二叉树最多有2k-1个结点 性质3 设二叉树叶子结点数为n0，度为2的结点n2，则n0 = n2+1 性质3证明： 　　设n为二叉树的结点总数，n1为二叉树中度为1的结点数，则有： n＝n0＋n1＋n2 （5-1） 　　在二叉树中，除根结点外，其余结点都有唯一的一个进入分支。设B为二叉树中的分支数，那么有： B＝n－1 （5-2） 　　这些分支是由度为1和度为2的结点发出的，一个度为1的结点发出一个分支，一个度为2的结点发出两个分支，所以有 B＝n1＋2n2 （5-3） n= n1＋2n2 +1 综合1、2、3式可以得到： n0＝n2＋1 性质1证明： 　　用数学归纳法。 　　i=1时，2i-1=20=1，由于只有一个根结点，所以i=1时，该命题成立。 　　假设i-1时命题成立，即第i-1层至多有2i-2个结点，则取i 时，由于二叉树中每个结点至多有两个孩子，故第i层上的结点数最多是第i-1层上最多结点数的2倍，即取i时，该层上至多有2×2i-2=2i-1个结点。命题成立。 性质2证明： 　　设第i层的结点数为xi（1≤i≤k），深度为k的二叉树的结点数为n，由性质1可知，xi最多为2i-1，则有：        n=20+21+…+2k-1=2k-1     故命题正确。

性质4 具有n个结点的完全二叉树的深度k为└ log2n ┘+1。 性质4证明： 　　根据完全二叉树的定义和性质2可知，当一棵完全二叉树的深度为k、结点个数为n时，有 2k－1-1＜n≤2k-1 即 2k－1≤n＜2k 　　对不等式取对数，有 k－1≤log2n＜k 　　由于k是整数，所以有k＝└ log2n ┘+1。 A B C E F

性质5 对于具有n个结点的完全二叉树，如果按照从上至下和从左到右的顺序对二叉树中的所有结点从1开始顺序编号，则对于任意的序号为i的结点，有： (1) 如果i=1，则序号为i的结点是根结点，无双亲结点； 如果i＞1，则序号为i的结点的双亲结点的序号为└i/2┘ 。 (2) 如果2i≤n，则序号为i的结点的左孩子结点的序号为2i； 　 如果2i＞n，则序号为i的结点无左孩子。 (3) 如果2i＋1≤n，则序号为i的结点的右孩子结点的序号为2i+1； 　 如果2i＋1＞n，则序号为i的结点无右孩子。 性质6 含有n个结点的二叉链表中，有n+1个空链域。 A B C E F G 1 2 3 4 5 6 性质6证明： 　　n个结点共有2n个链域，而每个结点（除根结点外）都有一个分支指向，则共有n-1个分支，其中每个分支占有一个链域，所以空链域为2n-(n-1)=n+1。 lchild data rchild

6.2.3 二叉树的存储结构 1．顺序存储结构 满二叉树或完全二叉树的顺序结构 6.2.3　二叉树的存储结构 1．顺序存储结构 满二叉树或完全二叉树的顺序结构 　　对于完全二叉树来说，除最下面一层外，各层都被结点充满着，每一层结点个数恰是上一层结点个数的2倍。因此从一个结点的编号就可推知其双亲、左右孩子等结点的编号。假设编号i的结点是ki（1≤i≤n），则有： 1．若i＞1，则ki的双亲编号为└i/2┘，若i=1，则ki是根结点，无双亲； 2．若2i≤n，则ki的左孩子的编号为2i，否则ki无左孩子即ki是叶子。因此完全二叉树中编号i＞└n/2┘的结点必定是叶子。 3．若2i+1≤n，由ki的右孩子编号是2i+1；否则ki无右孩子。

　　例如，用一维数组bt[ ]存放一棵完全二叉树，将标号为 i 的结点的数据元素存放在分量 bt[i-1]中。存储位置隐含了树中的关系，树中的关系是通过完全二叉树的性质实现的。 　　例如，bt[5]（i=6)的双亲结点标号是k= └i/2┘=3，双亲结点所对应的数组分量bt[k-1]=bt[2]。 bt[1]（i=2)的右孩子结点标号是k= 2i+1=5，所对应的数组分量bt[k-1]=bt[4]。 A B C E F G 1 2 3 4 5 6 顺序结构图示 1 2 3 4 5 6 n-1 A B C E F G ……

非完全二叉树的顺序结构 　　按完全二叉树的形式补齐二叉树所缺少的那些结点，对二叉树结点编号，将二叉树原有的结点按编号存储到内存单元“相应”的位置上。但这种方式对于畸形二叉树，浪费较大空间。 1 A A C 2 3 B C B F 4 5 6 7 D E D E F 8 9 G G 10 A B C D E ∧ F G

链表中每个结点由三个域组成，除了数据域外，还有两个指针域，分别用来给出该结点左孩子和右孩子所在结点的存储地址。结点的存储的结构为： 2．链式存储结构 二叉链表 　　链表中每个结点由三个域组成，除了数据域外，还有两个指针域，分别用来给出该结点左孩子和右孩子所在结点的存储地址。结点的存储的结构为： lchild data rchild A ∧ D A B ∧ C ∧ ∧ E ∧ ∧ F ∧ B C D E F

typedef struct BiTNode{ elemtype data； 二叉树的二叉链表存储表示可描述为： typedef struct BiTNode{ elemtype data； struct BiTNode *lchild，*rchild； /*左右孩子指针*/ }Bitnode，*Bitree； ∧ D A B ∧ C ∧ ∧ E ∧ ∧ F ∧ 　Bitree定义为指向二叉链表结点结构的指针类型。  　另外一个二叉链表是由根指针root惟一确定。 　若二叉树为空，则root=NULL；若结点的某个孩子不存在，则相应的指针为空。 　具有n个结点的二叉链表中，共有2n个指针域，其中只有n-1个用来指示结点的左、右孩子，其余的n+1个指针域为空。

每个结点由四个域组成，其中，data、lchild以及rchild三个域的意义同二叉链表结构；parent域为指向该结点双亲结点的指针。 三叉链表 　　每个结点由四个域组成，其中，data、lchild以及rchild三个域的意义同二叉链表结构；parent域为指向该结点双亲结点的指针。 lchild data rchild parent A A ∧ B C D E B ∧ C ∧ F Struct node { int data; struct node * lch,*rch,*parent; }; ∧ D ∧ E ∧ ∧ F ∧

6.2.4 二叉树的基本操作及实现 1．二叉树的基本操作 Initiate（） 建立一棵空二叉树。 Create（x，lbt，rbt） Insertlchild（bt，x，parent） 　将结点x插入到二叉树bt中作为结点parent的左孩子结点。如果结点parent原来有左孩子结点，则将结点parent原来的左孩子结点作为结点x的左孩子结点。 Insertrchild（bt，x，parent） 　将结点x插入到二叉树bt中作为结点parent的右孩子结点。如果结点parent原来有右孩子结点，则将结点parent原来的右孩子结点作为结点x的右孩子结点。

　Deletelchild（bt，parent） 　Deleterchild（bt，parent） 　　在二叉树bt中删除结点parent的右子树。 　Search（bt，x） 　　在二叉树bt中查找数据元素x。 　Traverse（bt） 　　按某种方式遍历二叉树bt的全部结点。

1．算法的实现 　以二叉链表为存储结构实现上述算法。 Initiate（） 　　初始建立二叉树bt，并使bt指向头结点。在二叉树根结点前建立头结点，就如同在单链表前建立的头结点，可以方便后边的一些操作实现。 Bitree Initiate ( ) {Bitree bt; if((bt=(Bitnode *)malloc(sizeof(Bitnode)))= =NULL) return NULL; bt->lchild=NULL; bt->rchild=NULL; return bt; }

建立一棵以x为根结点，以二叉树lbt和rbt为左右子树的二叉树。建立成功时返回所建二叉树结点的指针；建立失败时返回空指针。 Create（x，lbt，rbt） 　　建立一棵以x为根结点，以二叉树lbt和rbt为左右子树的二叉树。建立成功时返回所建二叉树结点的指针；建立失败时返回空指针。 BiTree Create(elemtype x,Bitree lbt,Bitree rbt) {Bitree p; if ((p=(Bitnode *)malloc(sizeof(Bitnode)))==NULL) return NULL; p->data=x; p->lchild=lbt; p->rchild=rbt; return p; } 演　示

Insertlchild（bt，x，parent） 　　将结点x插入到二叉树bt中作为结点parent的左孩子结点。如果结点parent原来有左孩子结点，则将结点parent原来的左孩子结点作为结点x的左孩子结点。 BiTree Insertlchild(Bitree bt,elemtype x,Bitree parent) { Bitree p; if (parent==NULL) { printf("\n插入出错");return NULL; } if ((p=(BiTNode *)malloc(sizeof(BiTNode)))==NULL) return NULL; p->data=x; p->lchild=NULL; p->rchild=NULL; if (parent->lchild==NULL) parent->lchild=p; else {p->lchild=parent->lchild; parent->lchild=p; } return bt; }

Deletelchild（bt，parent） 　　在二叉树bt中删除结点parent的左子树。当parent或parent的左孩子结点为空时删除失败。删除成功时返回根结点指针；删除失败时返回空指针 Bitree Deletelchild(Bitree bt,Bitree parent) {Bitree p; if (parent==NULL||parent->lchild==NULL) { printf("\n删除出错"); return NULL; } p=parent->lchild; parent->lchild=NULL; free(p); return br; /*当p为非叶子结点时，这样删除仅释放了所删子树根结点的空间，若要删除子树分支中的结点，需用后面介绍的遍历操作来实现。*/

6.3 遍历二叉树和线索二叉树 6.3.1 遍历二叉树 遍历：按某种搜索路径访问二叉树的每个结点，而且每个结点仅被访问一次。 访问：含义很广，可以是对结点的各种处理，如修改结点数据、输出结点数据。 　　遍历是各种数据结构最基本的操作，许多其他的操作可以在遍历基础上实现。 　　通过一次完整的遍历，可使二叉树中结点信息由非线性排列变为某种意义上的线性序列。也就是说，遍历的过程就是把非线性结构二叉树中的结点排成一个线性序列的过程。

一．二叉树的遍历方法 　　二叉树是递归定义的，它是由三部分组成，即根结点 、左子树、右子树。 　　二叉树的遍历可以分解为：访问根结点，遍历左子树和遍历右子树。 令：L：遍历左子树 D：访问根结点 R：遍历右子树 有六种遍历方法： D L R，L D R，L R D， D R L，R D L，R L D A C B F D E G 　　约定先左后右,有三种遍历方法： D L R、L D R、L R D ，分别称为 先序遍历、中序遍历、后序遍历

　先序遍历（D L R） 　若二叉树非空 　（1）访问根结点； 　（2）先序遍历左子树； 　（3）先序遍历右子树； A C B F D E G 例：先序遍历右图所示的二叉树 （1）访问根结点A （2）先序遍历左子树：即按 D L R 的顺序遍历左子树 （3）先序遍历右子树：即按 D L R 的顺序遍历右子树 先序遍历序列：A,B,D,E,G,C,F

　中序遍历（L D R） 　若二叉树非空 　（1）中序遍历左子树 　（2）访问根结点 　（3）中序遍历右子树 A C B F D E G 例：中序遍历右图所示的二叉树 （1）中序遍历左子树：即按 L D R 的顺序遍历左子树 （2）访问根结点A （3）中序遍历右子树：即按 L D R 的顺序遍历右子树 中序遍历序列： D,B,G,E,A,C,F

　后序遍历（L R D） 　若二叉树非空 　（1）后序遍历左子树 　（2）后序遍历右子树 　（3）访问根结点 A C B F D E G 例：后序遍历右图所示的二叉树 （1）后序遍历左子树：即按 L R D 的顺序遍历左子树 （2）后序遍历右子树：即按 L R D 的顺序遍历右子树 （3）访问根结点A 后序遍历序列： D,G,E,B,F,C,A

- + 先序遍历序列： / a * f e b c d 例：先序遍历、中序遍历、后序遍历下图所示的二叉树 中序遍历序列： 后序遍历序列： -,+,a,*,b,-,c,d,/,e,f a,+,b,*,c,-,d,-,e,/,f a,b,c,d,-,*,+,e,f,/,-

二．遍历的递归算法 　先序遍历（D L R）的定义： A C B 　若二叉树非空 （1）访问根结点； （2）先序遍历左子树 （3）先序遍历右子树； F D E G 上面先序遍历的定义等价于： 若二叉树为空，结束 ——基本项（也叫终止项） 若二叉树非空 ——递归项 （1）访问根结点； （2）先序遍历左子树 （3）先序遍历右子树；

bt a*(b-c)+d/e 1. 先序遍历递归算法 void Preorder(BiTree bt) { if (bt!=NULL) { 1. 先序遍历递归算法  void Preorder(BiTree bt) { 　if (bt!=NULL) 　{ 　　/*Visite(bt->data); */ 　　printf(“%c,”,bt->data); 　　Preorder(bt->lchild); 　　Preorder(bt->rchild); 　} } 先序序列为：　+ * a – b c / d e 称为前缀表达式 a*(b-c)+d/e

bt a*(b-c)+d/e 2. 中序遍历递归算法 void Inorder (BiTree bt) { if (bt!=NULL) { 2. 中序遍历递归算法  void Inorder (BiTree bt) { 　if (bt!=NULL) 　{ 　　Inorder (bt->lchild); 　　printf(“%c,”, bt->data); 　　Inorder (bt->rchild); 　} } 中序序列为　a * b – c+ d / e 称为中缀表达式 你能写出后序遍历递归算法了吧？

bt a*(b-c)+d/e 3. 后序遍历递归算法 void Postorder (BiTree bt) { if (bt!=NULL) 3. 后序遍历递归算法  bt void Postorder (BiTree bt) { 　if (bt!=NULL) 　{ 　　Postorder (bt->lchild); 　　Postorder (bt->rchild); 　　printf(“%c,”, bt->data); 　} } 后序序列为 a b c – * d e / + 称为后缀表达式 + * / ∧ a ∧ - /\ d /\ ∧ e ∧ ∧ b ∧ ∧ c ∧ a*(b-c)+d/e

三．二叉树遍历的非递归算法 　　递归算法逻辑清晰、易懂，但在实现时，由于函数调用栈层层叠加，效率不高，故有时考虑非递归算法。 　　这一路线正是从根结点开始沿左子树深入下去，当深入到最左端，无法再深入下去时，则返回，再逐一进入刚才深入时遇到结点的右子树，再进行如此的深入和返回，直到最后从根结点的右子树返回到根结点为止。先序遍历是在深入时遇到结点就访问，中序遍历是在从左子树返回时遇到结点访问，后序遍历是在从右子树返回时遇到结点访问。

1 先序遍历（D L R）的非递归算法。 　　在下面算法中，二叉树以二叉链表bt存放，用一维数组stack[Maxsize] 实现栈，变量top用来表示当前栈顶的位置。 （1）令当前指针p指向根结点。 （2）当p非空访问当前结点p，将p压入栈中，令当前指针　　　 指向其左孩子，重复（2），直到p为NULL （3）当p为空时，从栈中弹出栈顶元素赋给变量p，令当前　　 指针指向其右孩子 （4）若栈非空或当前指针非NULL，执行（2）；当p为空且　　 栈也为空时，遍历结束。

- + * / a e d b c 先序遍历的非递归算法 void NRPreOrder(BiTree bt) { BiTree stack[Maxsize],p; int top; if (bt!=NULL){ top=0;p=bt; while(p!=NULL||top>=0) { while(p!=NULL) { printf("%d",p->data); top++; stack[top]=p; p=p->lchild; } if (top>0) { p=stack[top]; top--; p=p->rchild; } }} /* 初始化 */ /* 访问结点的数据域 */ /* 将当前指针p压栈 */ /* 指针指向p的左孩子 */ /*从栈中弹出栈顶元素，指针指向p的右孩子结点*/

中序遍历的非递归算法 　　从二叉树的根结点开始，令变量p为根结点，若p不为空，则令p沿左子树根结点前进，在前进过程中，把所经历的结点逐个压入栈中，当p为空时，弹出栈顶元素给p，并访问该结点，再令p为它当前结点的右子树根结点。重复上述过程，当p为空且栈也为空时，遍历结束。 　　在算法具体实现时，只需将先序遍历的非递归算法中的Visite（p->data）移到p=stack[top]和p=p->rchild之间即可。 后序遍历的非递归算法

例1 编写 求二叉树的叶子结点个数的算法 四．遍历的应用 输入：二叉树的二叉链表 结果：二叉树的叶子结点个数 ∧ D A B ∧ C ∧ ∧ E ∧ ∧ F ∧ bt 例1 编写 求二叉树的叶子结点个数的算法 输入：二叉树的二叉链表 结果：二叉树的叶子结点个数 void leaf(BiTree bt) //采用二叉链表存贮二叉树，n为全局变量，用于累加二叉树的叶子结点的个数。本算法在先序遍历二叉树的过程中，统计叶子结点的个数。在主程序中第一次被调用时，n赋值为0 {if(bt!=NULL) {if(bt->lchild= =NULL&&bt->rchild = =NULL) n=n+1; //若root所指结点为叶子, 则累加 leaf(bt->lchild); leaf(bt->rchild); }

比较先序遍历算法和计算叶子结点算法，有什么相同和不同？ void Preorder(BiTree bt) { 　if (bt!=NULL) 　{ printf(“%d,”, root->data); 　　Preorder(bt->lchild); 　　Preorder(bt->rchild); 　} } 比较先序遍历算法和计算叶子结点算法，有什么相同和不同？ 访问结点时 调用printf( ) 访问结点时统计叶子结点的个数 void leaf(BiTree bt) { if(bt!=NULL) {if(bt->lchild= =NULL&&bt->rchild = =NULL) n=n+1; leaf(bt->lchild); leaf(bt->rchild); } 函数名不同 结构类似

例2 设计算法求解给定二叉树的高度 A 输入：二叉树的二叉链表 结果：二叉树的高度 B C 分析如下： 例2 设计算法求解给定二叉树的高度 输入：二叉树的二叉链表 结果：二叉树的高度 A D C B 分析如下： （1）若二叉树为空，则其高度为0，求解结束 （2）若二叉树不为空，则其高度为左右子树高度最大值加1 int high(BiTree bt) { int a,b; if (bt==NULL) return 0; else{ a=high(bt->lchild); b=high(bt->rchild); if (a>b) return a+1; else return b+1; }

* 例3 建立二叉链表 输入：二叉树的先序序列 结果：二叉树的二叉链表 例3 建立二叉链表 输入：二叉树的先序序列 结果：二叉树的二叉链表 　遍历操作访问二叉树的每个结点，而且每个结点仅被访问一次。是否可在利用遍历，建立二叉链表的所有结点并完成相应结点的链接？ 基本思想：输入(在空子树处添加空格字符的二叉树的)先序序列(设每个元素是一个字 符)，按先序遍历的顺序，建立二叉链表，并将该二叉链表根结点指针赋给root A F E D C B * A B D * F * * * C E * * *

如果输入字符不是空格，则建立一个新结点，然后建立其左子树和右子树；如果是空格则返回，继续进行下一次操作。 　　如果输入字符不是空格，则建立一个新结点，然后建立其左子树和右子树；如果是空格则返回，继续进行下一次操作。 BiTree create_tree() { BiTree bt; char ch; ch=getchar(); if (ch==' ') bt=NULL; else{ bt= (BiTree)malloc(sizeof(Bitnode)); bt->data = ch; bt->lchild=create_tree(); bt->rchild=create_tree(); } return (bt); /*若ch== ' ' ，则root=NULL返回*/ /*建立（根）结点*/ /*构造左子树链表，并将左子树根结点指针赋 给（根）结点的左孩子域*/ /*构造右子树链表，并将右子树根结点指针赋 给（根）结点的右孩子域*/

（在空子树处添加*的二叉树的）先序序列： A B D F C E T A （在空子树处添加*的二叉树的）先序序列： A B D F C E B ∧ C ∧ ∧ D ∧ E ∧ ∧ F ∧

练习： 1．已知一棵度为k的树中有n1个度为1的结点，n2个度为2的结点，…，nk个度为k的结点，问该树中有多少个叶子结点？ 3．由二叉树的先序序列和中序序列可唯一确定一棵二叉树，试构造相应的二叉树。 先序 ABCDEFGHI 先序 ABCDEFGHIJ 中序 ADECFBGIH 中序 BDECAGIJHF 4．由二叉树的后序序列和中序序列可唯一确定一棵二叉树，试构造相应的二叉树。 后序 DCFEBIHGA 后序 DECBGIHFA 中序 DCBFEAGHI 中序 DCEBAFHGI

6.3.2 线索二叉树 一．线索二叉树的定义 　　为了保留结点在某种遍历序列中直接前驱和直接后继的位置信息，可以利用二叉树的二叉链表存储结构中的那些空指针域来指示。这些指向直接前驱结点和指向直接后继结点的指针被称为线索（thread），加了线索的二叉树称为线索二叉树。 在二叉树的先序、中序或后序遍历序列中两个相邻的结点　互称为前驱与后继。 指向前驱或后继结点的指针称为线索。 加上线索的二叉链表表示的二叉树叫线索二叉树。 对二叉树按某种遍历次序使其变为线索二叉树的过程叫线　索化。

二．线索二叉树的结构 　　出发点：具有n个结点的二叉树若采用二叉链表存储结构，在2n个指针域中只有n－1个指针域是用来存储结点孩子的地址，而另外n＋1个指针域存放的都是NULL。 　　利用某结点空的左指针域（lchild）指出该结点在某种遍历序列中的直接前驱结点的存储地址，利用结点空的右指针域（rchild）指出该结点在某种遍历序列中的直接后继结点的存储地址；对于那些非空的指针域，则仍然存放指向该结点左、右孩子的指针。 　　在存储中如何区别某结点的指针域内存放的是指针还是线索？

结构： ltag＝ rtag＝ 为每个结点增设两个标志位域ltag和rtag： 0 lchild指向结点的左孩子 0 rchild指向结点的左孩子 1 rchild指向结点的前驱结点 rtag＝ 结构示意图： ltag lchild data rchild rtag typedef struct BiThrNode { elemtype data; struct BiThrNode *lchild,*rchild; int ltag, rtag; }Bithrnodetype,*Bithrtree;

A B D C E T 1 ^ A B C D E 先序序列：A B C D E 先序线索二叉树

中序序列：B C A E D 中序线索二叉树 后序序列：C B E D A 后序线索二叉树 A B D C E T 1 ^ A B C D 1 ^ A B C D E A B D C E T 后序序列：C B E D A 后序线索二叉树 1 ^

A B C D E 　　在存储线索二叉树时增设一头结点，其结构与其它线索二叉树的结点结构一样，只是其数据域不存放信息，其左指针域指向二叉树的根结点，右指针域指向某种遍历时访问的最后一个结点。而原二叉树在某序遍历下的第一个结点的前驱线索和最后一个结点的后继线索都指向该头结点。 0 A 0 1 B 0 0 D 1 1 C 1 1 E 1 T 中序序列：BCAED 带头结点的中序线索二叉树 0 1 头结点： lt=0, lc指向根结点 rt=1, rc指向遍历序列中最后一个结点 遍历序列中第一个结点的lc域和最后 一个结点的rc域都指向头结点

三．线索二叉树的基本操作实现 1) 如何中序线索化？ 　　对二叉树线索化，实质上就是将每个结点中空的左右孩子指针域分别修改为指向其中序序列的前驱、后继结点。线索化算法： 因每个结点均可能有空指针需要线索化，首先进行遍历。 每个结点线索化操作包括： 　若左子树为空，左标志置1，左孩子指针改为指向其前驱。 　若右子树为空，右标志置1，右孩子指针改为指向其后继。 每个结点进行线索化时，应知道每个结点的前驱和后继结点的地址。对于前驱结点的指针值，可设一指针变量pre来记录。而对于其后继结点的指针值，是按遍历次序进行的，线索该结点时还不知道。

线索化时只能对其前驱线索化，后继线索化无法进行。？！ 对于p所指结点的线索化分为两步： 当p所指结点为当前结点时，前驱线索化； 　　p所指结点的前驱结点（由pre指示）的后继线索化； 　　p所指结点的前驱线索化。 pre所指结点的线索化 pre所指结点的前驱线索化 pre所指结点的后继线索化 p所指结点的线索化 p所指结点的前驱线索化 p所指结点的后继线索化 P所指结点为当前结点时的操作

中序遍历二叉树T，并将其中序线索化，*head指向头结点 int InOrderThr(BiTree head,BiTree T) { if ((head=(Bitnode *)malloc(sizeof(Bitnode)))==NULL) return 0; head->ltag=0; head->rtag=1; head->rchild=head; if (!T) head->lchild =head; else { head->lchild=T; pre=head; InThreading(T); pre->rchild=head; pre->rtag=1; head->rchild=pre; } return 1; /*建立头结点*/ /*右指针回指*/ /*若二叉树为空，则左指针回指*/ /*中序遍历进行中序线索化*/ /*最后一个结点线索化*/

void InThreading(BiTree p) { if (p){ InThreading(p->lchild); 中序遍历进行中序线索化 void InThreading(BiTree 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); } /*左子树线索化*/ /*前驱线索化*/ /*后继线索化*/ /*右子树线索化*/ 演　示

2) 在中序线索二叉树中查找任意结点的中序前驱结点 　　对于中序线索二叉树上的任一结点，寻找其中序的前驱结点，有以下两种情况： 如果该结点的左标志为1，那么其左指针域所指向的结点便是它的前驱结点； 如果该结点的左标志为0，表明该结点有左孩子，根据中序遍历的定义，它的前驱结点是以该结点的左孩子为根结点的子树的最右结点，即沿着其左子树的右指针链向下查找，当某结点的右标志为1时，它就是所要找的前驱结点。

在中序线索二叉树中查找任意结点的中序前驱结点 在中序线索二叉树中查找任意结点的中序前驱结点　　 Bithrtree Inprenode(Bithrtree p) { Bithrtree pre; pre=p->lchild; if (p->ltag!=1) while(pre->rtag==0) pre=pre->rchild; return(pre); } 演　示

3) 在中序线索二叉树上查找值为x的结点 　　利用在中序线索二叉树上寻找后继结点和前驱结点的算法，就可以遍历到二叉树的所有结点。比如，先找到按中序遍历的第一个结点，然后再依次查询其后继；或先找到按中序遍历的最后一个结点，然后再依次查询其前驱。这样，既不用栈也不用递归就可以访问到二叉树的所有结点。 Bithrtree Search (Bithrtree head,elemtype x) { Bithrtree p; p=head->lchild; while (p->ltag==0&&p!=head) p=p->lchild; while(p!=head && p->data!=x) p=Inpostnode(p); if (p==head) { printf("Not Found the data!\n"); return(0);} else return(p); }

4) 在中序线索二叉树上的更新 　　线索二叉树的更新是指，在线索二叉树中插入一个结点或者删除一个结点。一般情况下，这些操作有可能破坏原来已有的线索。这里仅讨论一种比较简单的情况，即在中序线索二叉树中插入一个结点p，使它成为结点s的右孩子。 下面分两种情况来分析： （1）若s的右子树为空，如图(a)所示，则插入结点p之后成为图(b)所示的情形。在这种情况中，s的后继将成为p的中序后继，s成为p的中序前驱，而p成为s的右孩子。二叉树中其它部分的指针和线索不发生变化。 （a） （b）

（2）若s的右子树非空，如图(a)所示，插入结点p之后如图(b)所示。S原来的右子树变成p的右子树，由于p没有左子树，故s成为p的中序前驱，p成为s的右孩子；又由于s原来的后继成为p的后继，因此还要原来指向s的前驱左线索，改为指向p。 （a） （b）

void Insertthrright(Bithrtree s,Bithrtree p) { Bithrtree w; p->rchild=s->rchild; p->rtag=s->rtag; p->lchild=s; p->ltag=1; s->rchild=p; s->rtag=0; if(p->rtag==0){ w=Inpostnode(p); w->lchild=p; } /*将s变为p的中序前驱*/ /*p成为s的右孩子*/ /*当s原来右子树不空时，找到s的后继w，使其前驱指向p*/

6.4 树和森林 　6.4.1　 树的存储结构 　　在计算机中，树的存储通常采用顺序存储结构和链式存储结构，但无论采用何种存储方式，都要求存储结构不但能存储各结点本身的数据信息，还要能唯一地反映树中各结点之间的逻辑关系 1.双亲结点数组表示法 　　由树的定义可以知道，树中的每个结点（除根结点）都有唯一的一个双亲结点，根据这一特性，可用一组连续的存储空间（一维数组）存储树中的各个结点，数组中的一个元素表示树中的一个结点，数组元素为结构体类型，其中包括结点本身的信息以及结点的双亲结点在数组中的序号，树的这种存储方法称为双亲结点数组表示法。其存储表示可描述为下图： 　　图中用parent域的值为-1表示该结点无双亲结点，即该结点是一个根结点。

#define Maxnode 100 /* 树中结点的最大个数 */ typedef struct { elemtype data； int parent； }NodeType； NodeType T[Maxnode]； A -1 1 B 2 C 3 D 4 E 5 F 6 G 7 H 8 I 9 J J I A C B D H G F E

2. 孩子表示法 一、多重链表法 　　由于树中每个结点都有零个或多个孩子结点，因此，可以令每个结点包括一个结点信息域和多个指针域，每个指针域指向该结点的一个孩子结点，通过各个指针域值反映出树中各结点之间的逻辑关系。在这种表示法中，树中每个结点有多个指针域，形成了多条链表，所以这种方法又常称为多重链表法。 　　在一棵树中，各结点的度数各异，因此结点的指针域个数的设置有两种方法： ① 每个结点指针域的个数等于该结点的度数； ② 每个结点指针域的个数等于树的度数。 二、孩子链表表示法 为树的每个节点建立一个孩子链表。孩子链表表示法是将树按下图所示的形式存储。其主体是一个与结点个数一样大小的一维数组，数组的每一个元素有两个域组成，一个域用来存放结点信息，另一个用来存放指针，该指针指向由该结点孩子组成的单链表的首位置。单链表的结构也由两个域组成，一个存放孩子结点在一维数组中的序号，另一个是指针域，指向下一个孩子。

#define Maxnode 100 /*树中结点的最大个数*/ typedef struct { int childcode；  这种存储表示可描述为： #define Maxnode 100 /*树中结点的最大个数*/ typedef struct { int childcode； struct ChildNode *nextchild； } ChildNode typedef struct { elemtype data； ChildNode *firstchild； }NodeType； NodeType t[Maxnode]； A 1 B 2 C 3 D 4 E 5 F 6 G 7 H 8 I 9 J 1 2 3 4 5 6 7 8 9 J I A C B D H G F E

3. 双亲孩子表示法 双亲表示法仍将各结点的孩子结点分别组成单链表，同时用一维数组顺序存储树中的各结点，数组元素除了包括结点本身的信息和该结点的孩子结点链表的头指针之外，还增设一个域，存储该结点双亲结点在数组中的序号的树 A -1 1 B 2 C 3 D 4 E 5 F 6 G 7 H 8 I 9 J 1 2 3 4 5 J I A C B D H G F E 6 7 8 9

在树中，每个结点除其信息域外，再增加两个分别指向该结点的第一个孩子结点和下一个兄弟结点的指针。在这种存储结构下，树中结点的存储表示可描述为： 4.孩子兄弟表示法 在树中，每个结点除其信息域外，再增加两个分别指向该结点的第一个孩子结点和下一个兄弟结点的指针。在这种存储结构下，树中结点的存储表示可描述为： typedef struct TreeNode { elemtype data； struct TreeNode *fch ， *nsib； }NodeType； J I A C B D H G F E

6.4.2　森林、树与二叉树的转换 1 树转换为二叉树 　　树中每个结点可能有多个孩子，但二叉树中每个结点最多只能有两个孩子。树中每个结点最多只有一个最左的孩子和一个右邻的兄弟。虽然树是无序的，为避免发生混淆，我们约定树中每一个结点的孩子结点也按从左到右的次序。 A F E D C B

将一棵树转换为二叉树的方法是： 树中所有相邻兄弟之间加一条连线。 对树中的每个结点，只保留它与第一个孩子结点之间的连线，删去它与其它孩子结点之间的连线。 以树的根结点为轴心，将整棵树顺时针转动一定的角度，使之结构层次分明。 A F E D C B A F E D C B A F E D C B

2 森林转换为二叉树 森林是若干棵树的集合，只要将森林中各棵树的根视为兄弟，每棵树都用二叉树表示，这样森林也同样可以用二叉树表示。 　　森林是若干棵树的集合，只要将森林中各棵树的根视为兄弟，每棵树都用二叉树表示，这样森林也同样可以用二叉树表示。 森林转换为二叉树的方法如下： 将森林中的每棵树转换成相应的二叉树。 第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子，当所有二叉树连起来后，此时所得到的二叉树就是由森林转换得到的二叉树。 　　如果F＝{ T1,T2,…,Tm}是森林且非空，则转换二叉树B的根root即为森林中第一棵树的根Root（T1）；B的左子树L是从T1中根结点的子树森林F1＝{ T11,T12,…,T1m}转换而成的二叉树；其右子树R是从森林F’＝{ T2,T3,…,Tm}转换而成的二叉树。

A D C B F E G I H A D C B F E G I H A D C B F E G I H 森林及其转换为二叉树的过程 : A D C B F E G I H （a） 一个森林 A D C B F E G I H A D C B F E G I H （b） 森林中每棵树转换为二叉树 （c） 所有二叉树连接后的二叉树

3 二叉树转换为树和森林 可以依据二叉树的根结点有无右分支，将一棵二叉树还原为树或森林，具体方法如下： 3　二叉树转换为树和森林 　　可以依据二叉树的根结点有无右分支，将一棵二叉树还原为树或森林，具体方法如下： 若某结点是其双亲的左孩子，则把该结点的右孩子、右孩子的右孩子，……，都与该结点的双亲结点用虚线连起来； 删去原二叉树中所有的双亲结点与右孩子结点的连线（虚线部分不能删）； 整理由1、2两步所得到的树或森林，使之结构层次分明，将虚线改成实线。 　　若B非空，则森林中第一棵树T1的根ROOT（T1）即为B的根root；T1中根结点的子树森林F1是由B的左子树L转换而成的森林；F中除T1之外其余树组成的森林F’＝{ T2，T3，…，Tm }是由B的右子树R转换而成的森林。

A D C B F E G I H A D C B F E G I H A D C B F E G I H 二叉树还原为树的过程 : A D C B F E G I H A D C B F E G I H （a）二叉树加连线 （b）去掉与右孩子的连线 A D C B F E G I H （c）还原后的树

练习： 对下图中的二叉树进行后序线索化，为每个空指针建立相应的前驱或后继？ A D C B F E G H

将下图中的森林转换为对应的二叉树。 A D C B F E G J K L M N O P I H 将下图中二叉树转换为森林。 A D C B F E G J K L M N O I H

6.4.3 树和森林的遍历 1 树的遍历 在树和森林中，一个结点可能有两棵以上的子树，所以不讨论其中序遍历， 只讨论先序遍历和后序遍历。 　　在树和森林中，一个结点可能有两棵以上的子树，所以不讨论其中序遍历， 只讨论先序遍历和后序遍历。 1 树的遍历 先序遍历 A F E D C B 访问根结点； 按照从左到右的顺序先序遍历根结点的每一棵子树。 A B E C F D 后序遍历 按照从左到右的顺序后序遍历根结点的每一棵子树。 访问根结点； E B F C D A

2 森林的遍历 先序遍历 A D C B 访问森林中第一棵树的根结点； 先序遍历第一棵树的根结点的子树； 先序遍历去掉第一棵树后的子森林。 A B C D E F G H I F E 后序遍历 后序遍历第一棵树的根结点的子树； 访问森林中第一棵树的根结点； 后序遍历去掉第一棵树后的子森林。 B C D A E F H I G G I H

6.6 哈夫曼树及其应用 一、基本术语 1．路径和路径长度： 在一棵树中，从一个结点往下可以达到的孩子或子孙结点之间的通路，称为路径。 6.6 哈夫曼树及其应用 一、基本术语 1．路径和路径长度： 　　在一棵树中，从一个结点往下可以达到的孩子或子孙结点之间的通路，称为路径。 　　通路中分支的数目称为路径长度。 　　若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。 2．结点的权及带权路径长度： 　　若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。 　　从根结点到该结点之间的路径长度与该结点的权的乘积称为结点的带权路径长度。

3．树的带权路径长度： 　　树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为wpl= ，其中n 为叶子结点数目，wi为第i 个叶子结点的权值，li 为第i 个叶子结点的路径长度。 4．哈夫曼树： 　　在一棵二叉树中，对于一组带有确定权值的叶节点，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman tree)。

例 有4个结点，权值分别为7，5，2，4， 构造有4个叶子结点的二叉树 a b c d 7 5 2 4 d c a b 2 4 7 5 WPL=7*2+5*2+2*2+4*2=36 7 a WPL=7*3+5*3+2*1+4*2=46 5 b WPL=7*1+5*2+2*3+4*3=35 2 4 c d

二、Huffman树的构造方法 以权值分别为W1,W2．．．,Wｎ的ｎ各结点，构成n棵二叉树T1,T2,．．．,Tn并组成森林F={T1,T2,．．．Tn},其中每棵二叉树 Ti仅有一个权值为 Wi的根结点； 在F中选取两棵根结点权值最小的树作为左右子树构造一棵新二叉树，并且置新二叉树根结点权值为左右子树上根结点的权值之和（根结点的权值=左右孩子权值之和，叶结点的权值= Wi） 从F中删除这两棵二叉树，同时将新二叉树加入到F中; 重复(2)、(３)直到F中只含一棵二叉树为止，这棵二叉树就是Huffman 树。

例 w={5, 29, 7, 8, 14, 23, 3, 11} 29 14 8 7 15 11 3 5 19 23 42 5 14 29 7 8 23 3 11 14 29 7 8 23 11 3 5 11 3 5 8 19 23 42 29 14 7 15 58 8 7 15 14 29 23 3 5 11 11 3 5 8 19 14 29 23 7 15 11 3 5 8 19 23 42 29 14 7 15 58 100 11 3 5 8 19 29 23 14 7 15 演　示

　　由哈夫曼树构造思想得知，初始森林中共有n棵二叉树，每棵树中都仅有一个孤立的结点，接着将当前森林中的两棵根结点权值最小的二叉树合并成一棵新的二叉树。每合并一次，森林中就减少一棵树。显然要进行n-1次合并，才能使森林中的二叉树的数目，由n棵减少到只剩下一棵最终的哈夫曼树。并且每次合并，都要产生一个新结点。合并n-1次共产生n-1个新结点，并且它们都是具有两个孩子的分支结点。由此可知，最终求得的哈夫曼树中共有2n-1个结点。 哈夫曼结点结构： weight lchild rchild parent

哈夫曼算法可描述为： 将哈夫曼树数组中的2n-1个结点初始化，即将各结点中的三个指针值置为-1，权值置为-1。 读入n个权值放入数组的前n个分量中，它们是初始森林中的n个孤立的根结点。 对森林中的树进行n-1次合并，共产生n-1个新结点，依次放入数组的第i个分量中（n≤i≤2n-2）。合并如下： 在当前森林的所有结点中，选取具有最小权值和次小权值的两个结点，分别用x1和x2记住这两个根结点要数组中的下标； 将根为Htree[x1]和Htree[x2]的两棵树合并，使其成为新结点Ｈtree[i]左右孩子，得到一棵以新结点Htree[i]为根的二叉树。同时修改Htree[x1]和Htree[x2]的双亲域parent，使其指向新结点Htree[i]，将Htree[x1]和Htree[x2]的权值相加后作为新结点Htree[i]的权值。

#define Maxnode Maxleaf*2-1 typedef struct{ #define Maxweight 1000 #define Maxleaf 30 #define Maxnode Maxleaf*2-1 typedef struct{ int weight, parent ,lchild ,rchild; }HNode; Hnode Htree[Maxnode-1]; void HaffmanTree(Hnode Htree[]) { int i,j,k1,k2,x1,x2,n; scanf("%d",&n); for (i=0;i<2*n-1;i++){ Htree[i].weight=0; Htree[i].parent=-1; Htree[i].lchild=-1; Htree[i].rchild=-1; } /*定义最大权值*/ /*哈夫曼树中叶子结点个数*/ /*哈夫曼树中结点个数*/ /*哈夫曼树的结构*/ /*输入叶子结点个数*/ /*数组Htree[ ]初始化*/

scanf("%d",&Htree[i].weight); for (i=0;i<n-1;i++){ k1=k2=Maxweight; x1=x2=0; for (j=0;j<n+i;j++){ if (Htree[j].weight<k1 && Htree[j].parent==-1) {k2=k1; x2=x1; k1=Htree[j].weight; x1=j; }else if(Htree[j].weight<k2 && Htree[j].parent==-1) {k2=Htree[j].weight;x2=j;} } Htree[x1].parent=n+i; Htree[x2].parent=n+i; Htree[n+i].weight=Htree[x1].weight+Htree[x2].weight; Htree[n+i].lchild=x1; Htree[n+i].rchild=x2; /*输入n个叶子结点的权值*/ /*构造哈夫曼树*/ /*x1,x2用来指示权最小的两个结点*/ /* 将找出的两棵子树合并为一棵子树*/ 演　示

三、哈夫曼编码 　　在电报通讯中，电文通常是以二进制0,1序列传送的。因此需要将传送的文字转换成由二进制字符0,1组成的二进制串，我们称之为编码。例如，假设要传送的电文为ABACCDA，电文中只含有A,B,C,D四种字符，可以有以下几种编码： 字符 A B C D 方案1 000 010 100 111 方案2 00 01 10 11 方案3 110 方案4 001 方案1：代码为000010000100100111000，长度为21。 方案2：代码为00010010101100 ，长度为14。 方案3：代码为0110010101110 ，长度为13。

　　具体编码方法如下：设需要编码的字符集合为D={d1，d2,…,dn}，它们在电文中出现的次数或频率集合为{w1,w2,…，wn}，以d1,d2,…,dn作为叶结点，w1,w2,…,wn作为它们的权值，构造一棵哈夫曼树，规定哈夫曼树中的左分支代表0，右分支代表1，则从根结点到每个叶结点所经过的路径分支组成的0和1的序列便为该结点对应字符的编码，我们称之为哈夫曼编码。 　　在建立不等长编码时，必须使任何一个字符的编码都不是另一个字符编码的前缀，这样才能保证译码的唯一性。采用哈夫曼树进行编码，则不会产生上述二义性问题。因为，在哈夫曼树中，每个字符结点都是叶结点，它们不可能在根结点到其它字符结点的路径上，所以一个字符的哈夫曼编码不可能是另一个字符的哈夫曼编码的前缀，从而保证了译码的非二义性。

例如，设一组电文的字符集D及其概率分布W为：D={a,b,c,d，e}，W={0. 12，0. 40，0. 15，0. 08，0

　实现哈夫曼编码的算法可分为两大部分： 　　1．构造哈夫曼树； 　　2．在哈夫曼树上求叶结点的编码。 求哈夫曼编码，实质上就是在已建立的哈夫曼树中，从叶结点开始，沿结点的双亲链域回退到根结点，每回退一步，就走过了哈夫曼树的一个分支，从而得到一位哈夫曼码值，由于一个字符的哈夫曼编码是从根结点到相应叶结点所经过的路径上各分支所组成的0，1序列，因此先得到的分支代码为所求编码的低位码，后得到的分支代码为所求编码的高位码。

　我们可以设置一结构数组HuffCode用来存放各字符的哈夫曼编码信息，数组元素的结构如下：  其中，分量bit为一维数组，用来保存字符的哈夫曼编码，start表示该编码在数组bit中的开始位置。所以，对于第i个字符，它的哈夫曼编码存放在HuffCode[i].bit中的从HuffCode[i].start到n的分量上。 #define MAXBIT 10 typedef struct{ int bit[MAXBIT]; int start; }HCodeType;

HNodeType HuffNode[MAXNODE]; HCodeType HuffCode[MAXLEAF],cd; void HaffmanCode () { HNodeType HuffNode[MAXNODE]; HCodeType HuffCode[MAXLEAF],cd; int i,j, c,p; HuffmanTree (HuffNode); for (i=0;i<n;i++) { cd.start=n-1; c=i; p=HuffNode[c].parent; while(p!=0) { if (HuffNode[p].lchild==c) cd.bit[cd.start]=0; else cd.bit[cd.start]=1; cd.start--; c=p; } /*存放哈夫曼树*/ /*存放哈夫曼编码*/ /*建立哈夫曼树*/ /*依次求每个叶子结点的编码*/ /*由叶结点到树根*/ /*对途经的每个路径求编码*/ /*存放顺序由根到叶结点*/

for (j=cd.start+1;j<n;j++) HuffCode[i].bit[j]=cd.bit[j]; /*保存每个叶结点的哈夫曼编码*/ for (j=cd.start+1;j<n;j++) HuffCode[i].bit[j]=cd.bit[j]; HuffCode[i].start=cd.start; } for (i=0;i<n;i++) { for (j=HuffCode[i].start+1;j<n;j++) printf("%ld",HuffCode[i].bit[j]); printf("\n"); /*保存每个叶结点哈夫曼编码的起始位*/ /*输出每个叶子结点的哈夫曼编码*/

练习： 已知一个文件中仅有8个不同的字符，各字符出现的个数分别为3,4,8,10,16,18,20,21。试重新为各字符编码，以节省存储空间。

练习： 一棵深度为k的满二叉树的结点总数为 ，一棵深度为k的完全二叉树的结点总数的最小值为 最大值为 由a,b,c三个结点构成的二叉树，共有　　种不同的结构。 对于一个具有n个结点的二叉树，当它为一棵　　二叉树时具有最小高度，即为　　，当它为一棵单支树具有　　高度，即为　　 对于具有n个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为　　个，其中　　个用于链接孩子结点，　　个空闲着 在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为　　 假定一棵三叉树的结点数为50，则它的最小高度为　　 用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组R[1..n]中，结点R[i]若有左子女，则左子女是结点　　 在一棵二叉树上第5层的结点数最多为　　

作业： p119 1．已知一棵具有n个结点的完全二叉树被顺序存储在一维数组 A[n]中，试编写一个算法输出A[i]结点的双亲和所有孩子。 2．编写一个计算一棵二叉树T的高度的算法。