第六章树和二叉树[001]

《第六章树和二叉树[001]》由会员分享，可在线阅读，更多相关《第六章树和二叉树[001]（63页珍藏版）》请在金锄头文库上搜索。

1、第六章第六章 树和二叉树树和二叉树6.1 树树6.1.1 树的定义树的定义6.1.2 基本术语基本术语6.2 二叉树二叉树6.2.1 二叉树的定义二叉树的定义6.2.2 二叉树的性质二叉树的性质6. 3 二叉树的存储结构二叉树的存储结构6.3.1 顺序存储结构顺序存储结构6.3.2 链序存储结构链序存储结构6.4 二叉树的遍历与线索化二叉树的遍历与线索化6.4.1 二叉树的遍历二叉树的遍历6.4.2 二叉树的线索化二叉树的线索化6.5.2 森林与二叉树的转换森林与二叉树的转换6.5.3 树和森林的遍历树和森林的遍历6.1 树树6.1.1 树的定义树的定义（1）定）定义 树（Tree）：是）：是

2、n（n0）个）个结点的有限集。点的有限集。 定定义一：（一：（递归定定义）：）： 在任意一棵非空在任意一棵非空树中，有且中，有且仅有一个特定的称有一个特定的称为根（根（root） 的的结点；点； 当当n1时，其余，其余结点可分点可分为m（m0）个互不相交的有限集）个互不相交的有限集 T1, T2, , Tm，其中每一个集合本身又是一棵，其中每一个集合本身又是一棵树。并且。并且 T1, T2, , Tm，称，称为根的子根的子树（SubTree）。）。 定定义二：（形式定二：（形式定义）任何一棵任何一棵树是一个二元是一个二元组Tree = (root, F)。 其中：其中：root是数据元素，称做

3、是数据元素，称做树的根的根结点；点；F是是m（m0）棵）棵树的森林，的森林， F（T1, T2, , Tm），其中），其中Ti = (ri, Fi)称做根称做根root的第的第i棵子棵子树；当；当m0 时，在，在树根和其子根和其子树森林之森林之间存在下列关系：存在下列关系： RF = | i = 1, 2, ,m; m 0（2）表示形式）表示形式 该树有有13个个结点。其中，点。其中，A是是树根，其余根，其余结点分成点分成3个互不相交的子集：个互不相交的子集：T1=B, E, F, K, L，T2=C, G，T3=D, H, I, J, M; T1、T2和和T3都是都是A的子的子树，其本身也是

4、一棵其本身也是一棵树。层次次A 1B C D 2E F G H I J 3K L M 4 图图6.1一般的树一般的树该树又可表示为如下三种形式：该树又可表示为如下三种形式：(a) 嵌套集合表示嵌套集合表示 (c) 凹入表示法凹入表示法 (A(B(E(K, L), F), C(G), D(H(M), I, J) (b) 广义表表示广义表表示 ABCDEFGHIJKLMABCDEFGHIJKLM图图6.2树的其他树的其他3种表示法种表示法 （3）树的抽象数据类型定义）树的抽象数据类型定义 ADT Tree数据数据对象象D：D是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。数据关系数

5、据关系R：若：若D为空集，空集，则称称为空空树； 若若D仅含一个数据元素，含一个数据元素，则R为空集，否空集，否则R=H,H是如下二元关系：是如下二元关系： （1）在）在D中存在唯一的称中存在唯一的称为根的数据元素根的数据元素root，它在关系，它在关系H下无前下无前驱； （2）若）若Droot，则存在存在Droot的一个划分的一个划分D1,D2,Dm(m0), 对任意任意jk(1j,km)有有DjDk，且，且对任意的任意的i(1im)，唯，唯 一存在数据元素一存在数据元素xiDi，有，有H； （3）对应于于Droot的划分，的划分，H, , 有唯一有唯一 的一个划分的一个划分H1, H2,

6、, Hm(m0)，对任意任意jk (1j,km)有有 HjHk，且，且对任意任意i(1im)，Hi是是Di上的二元关系，上的二元关系， (Di, Hi)是一棵符合本定是一棵符合本定义的的树，称，称为根根root的子的子树。基本操作：基本操作： InitTree (&T); 操作结果：构造空树操作结果：构造空树T。 DestroyTree (&T);初始条件：树初始条件：树T存在。存在。操作结果：销毁树操作结果：销毁树T。 CreateTree (&T, definition);初始条件：初始条件：definition给出树给出树T的定义。的定义。操作结果：按操作结果：按definition构造

7、树构造树T。 ClearTree (&T);初始条件：树初始条件：树T存在。存在。操作结果：将树操作结果：将树T清为空树。清为空树。 TreeEmpty(T);初始条件：树初始条件：树T存在。存在。操作结果：若操作结果：若T为空树，则返回为空树，则返回TRUE，否则返回，否则返回FALSE。 TreeDepth(T);初始条件：树初始条件：树T存在。存在。操作结果：返回操作结果：返回T的深度。的深度。 Root(T);初始条件：树初始条件：树T存在。存在。操作结果：返回操作结果：返回T的根。的根。 Value(T, cur_e);初始条件：树初始条件：树T存在，存在，cur_e是是T中某个结点

8、。中某个结点。操作结果：返回操作结果：返回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);初始条件：树初始条件：树T存在，存在，cur_e是是T中某个

9、结点。中某个结点。操作结果：若操作结果：若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不相交。不相交

10、。操作结果：插入操作结果：插入c为为T中中p指结点的第指结点的第i棵子树。棵子树。 DeleteChild(&T, &P, i);初始条件：树初始条件：树T存在，存在，p指向指向T中某个结点，中某个结点，1ip指结点的度。指结点的度。操作结果：删除操作结果：删除T中中p所指结点的第所指结点的第i棵子树。棵子树。 TraverseTree(T, visit();初始条件：树初始条件：树T存在，存在，visit是对结点操作的应用函数。是对结点操作的应用函数。操作结果：按某种次序对操作结果：按某种次序对T的每个结点调用函数的每个结点调用函数visit()一次且至多一次。一次且至多一次。 一旦一旦vi

11、sit()失败，则操作失败。失败，则操作失败。ADT Tree6.1.2 基本术语基本术语 结点结点：包含一个数据元素及若干指向其子树的分支。在树的：包含一个数据元素及若干指向其子树的分支。在树的图形表示中为一个圆圈。图形表示中为一个圆圈。 结点的的度度（Degree）：结点拥有的子树树。）：结点拥有的子树树。 叶子叶子（或（或终端结点终端结点）（）（Leaf）：度为）：度为0的结点。即没有子树的结点。即没有子树的结点。的结点。分支结点分支结点（或（或非终端结点非终端结点）：度不为）：度不为0的结点。的结点。内部结点内部结点：除根结点之外的分支结点。：除根结点之外的分支结点。树的的度度：树内各

12、结点的度的最大值。：树内各结点的度的最大值。孩子孩子（Child）：结点的子树的根，称为该结点的孩子。）：结点的子树的根，称为该结点的孩子。 双亲双亲（Parent）：结点的子树的根，称为该结点的孩子，该）：结点的子树的根，称为该结点的孩子，该结点称为孩子的双亲。结点称为孩子的双亲。兄弟兄弟（Sibling）：同一个双亲的孩子之间互称为兄弟。）：同一个双亲的孩子之间互称为兄弟。子孙子孙：以某结点为根的子树中的任一结点都称为该结点的子孙。：以某结点为根的子树中的任一结点都称为该结点的子孙。祖先祖先：从根到某结点所经分支上的所有结点，称为该结点的祖先。：从根到某结点所经分支上的所有结点，称为该结点

13、的祖先。 森林森林（Forest）：是）：是m（m0）棵互不相交的树的集合。对树中）棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。每个结点而言，其子树的集合即为森林。 层次层次（Level）：从根开始定义起，根为第一层，根的孩子为第二）：从根开始定义起，根为第一层，根的孩子为第二层。若某结点在第层。若某结点在第k层，则其子树的根就在第层，则其子树的根就在第k1层。层。堂兄弟堂兄弟：其双亲在同一层的结点互为堂兄弟。：其双亲在同一层的结点互为堂兄弟。深度深度（高度高度）（）（Depth）：树中结点的最大层次。）：树中结点的最大层次。 有序树有序树：若将树中结点的各子树看成从左至右

14、是有次序的（即不能：若将树中结点的各子树看成从左至右是有次序的（即不能互换），则称该树为有序树，否则称为无序树。在有序树中最左边的子互换），则称该树为有序树，否则称为无序树。在有序树中最左边的子树的根称为第一个孩子，最右边的称为最后一个孩子。树的根称为第一个孩子，最右边的称为最后一个孩子。6.2 二叉树二叉树6.2.1 二叉树的定义二叉树的定义（1）定义）定义 二叉树二叉树（Binary Tree）：是另一种树型结构。）：是另一种树型结构。 特点：特点：每个结点至多只有两棵子树（即二叉树中不存在度大于每个结点至多只有两棵子树（即二叉树中不存在度大于2 的结点）。的结点）。 子树有左右之分，其次

15、序不能任意颠倒。子树有左右之分，其次序不能任意颠倒。（2）图形表示形表示 (a) (b) (c) (d) (e)图图6.3二叉树的二叉树的5种基本形态种基本形态(a) 空二叉树空二叉树(b) 仅有根结点的二叉树仅有根结点的二叉树(c) 右子树为空的二叉树右子树为空的二叉树(d) 左、右子树均非空的二叉树左、右子树均非空的二叉树(e) 左子树为空的二叉树左子树为空的二叉树（3）二叉树的抽象数据类型定义）二叉树的抽象数据类型定义 H，且存在，且存在Dl上的关系上的关系Hr H；H = , , Hl, Hr； （4）(Dl, Hl)是一棵符合本定义的二叉树，称为根的左子树，是一棵符合本定义的二叉树，

16、称为根的左子树，(Dr, Hr) 是一棵符合本定义的二叉树，称为根的右子树。是一棵符合本定义的二叉树，称为根的右子树。基本操作：基本操作： ADT BinaryTree数据对象数据对象D：D是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。数据关系数据关系R： 若若D = ，则，则R =，称称BinaryTree为空二叉树；为空二叉树； 若若D，则，则R=H,H是如下二元关系：是如下二元关系： （1）在）在D中存在唯一的称为根的数据元素中存在唯一的称为根的数据元素root，它在关系，它在关系H下无前驱；下无前驱； （2）若）若Droot，则存在，则存在Droot = Dl, Dr

17、，Dl且且Dm =； （3）若）若Dl，则，则Dl中存在唯一的元素中存在唯一的元素x1，有有H，且存在，且存在Dl 上的关系上的关系Hl H;若若 Dr, ,则则Dr中存在唯一的元素中存在唯一的元素xr, ,有有 InitBiTree (&T);操作结果：构造空二叉树操作结果：构造空二叉树T。 DestroyBiTree (&T);初始条件：二叉树初始条件：二叉树T存在。存在。操作结果：销毁二叉树操作结果：销毁二叉树T。 CreateBiTree (&T, definition);初始条件：初始条件：definition给出二叉树给出二叉树T的定义。的定义。操作结果：按操作结果：按defini

18、tion构造二叉树构造二叉树T。 ClearBiTree (&T);初始条件：二叉树初始条件：二叉树T存在。存在。操作结果：将二叉树操作结果：将二叉树T清为空树。清为空树。 BiTreeEmpty(T);初始条件：二叉树初始条件：二叉树T存在。存在。操作结果：若操作结果：若T为空二叉树，则返回为空二叉树，则返回TRUE，否则返回，否则返回FALSE。 BiTreeDepth(T);初始条件：二叉树初始条件：二叉树T存在。存在。操作结果：返回操作结果：返回T的深度。的深度。 Root(T);初始条件：二叉树初始条件：二叉树T存在。存在。操作结果：返回操作结果：返回T的根。的根。 Value(T,

19、 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);初始条件：二叉树初始条件：二

20、叉树T存在，存在， e是是T中某个结点。中某个结点。操作结果：返回操作结果：返回e的左孩子。若的左孩子。若e无左孩子，则返回无左孩子，则返回“空空”。 RightChild (T, e);初始条件：二叉树初始条件：二叉树T存在，存在， e是是T中某个结点。中某个结点。操作结果：返回操作结果：返回e的右孩子。若的右孩子。若e无右孩子，则返回无右孩子，则返回“空空”。 LeftSibling(T, e);初始条件：二叉树初始条件：二叉树T存在，存在， e是是T中某个结点。中某个结点。操作结果：返回操作结果：返回e的左兄弟。若的左兄弟。若e是是T的左孩子或无左兄弟，则返回的左孩子或无左兄弟，则返回“

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

22、结点的原有左或右子树则成为结点的原有左或右子树则成为c的右子树。的右子树。 DeleteChild(T, P, LR);初始条件：二叉树初始条件：二叉树T存在，存在，p指向指向T中某个结点，中某个结点，LR为为0或或1。操作结果：根据操作结果：根据LR为为0或或1，删除，删除T中中p所指结点的左或右子树。所指结点的左或右子树。 PreOrderTraverse (T, visit();初始条件：二叉树初始条件：二叉树T存在，存在，visit是对结点操作的应用函数。是对结点操作的应用函数。操作结果：先序遍历操作结果：先序遍历T，对每个结点调用函数，对每个结点调用函数visit()一次且仅一次。一

23、次且仅一次。 一旦一旦visit()失败，则操作失败。失败，则操作失败。 InOrderTraverse (T, visit();初始条件：二叉树初始条件：二叉树T存在，存在，visit是对结点操作的应用函数。是对结点操作的应用函数。操作结果：中序遍历操作结果：中序遍历T，对每个结点调用函数，对每个结点调用函数visit()一次且仅一次。一次且仅一次。 一旦一旦visit()失败，则操作失败。失败，则操作失败。 PostOrderTraverse (T, visit();初始条件：二叉树初始条件：二叉树T存在，存在，visit是对结点操作的应用函数。是对结点操作的应用函数。操作结果：后序遍历操

24、作结果：后序遍历T，对每个结点调用函数，对每个结点调用函数visit()一次且仅一次。一次且仅一次。 一旦一旦visit()失败，则操作失败。失败，则操作失败。 LevelOrderTraverse (T, visit();初始条件：二叉树初始条件：二叉树T存在，存在，visit是对结点操作的应用函数。是对结点操作的应用函数。操作结果：层序遍历操作结果：层序遍历T，对每个结点调用函数，对每个结点调用函数visit()一次且仅一次。一次且仅一次。 一旦一旦visit()失败，则操作失败。失败，则操作失败。ADT BinaryTree（4）特殊形态的二叉树）特殊形态的二叉树满二叉树满二叉树：一棵深

25、度为：一棵深度为k且有且有2k1个结点的二叉树称为满二叉树。个结点的二叉树称为满二叉树。 特点：每一层上的结点数都是最大结点数。特点：每一层上的结点数都是最大结点数。 完全二叉树完全二叉树：深度为：深度为k的，有的，有n个结点的二叉树，当且仅当其每一个结点的二叉树，当且仅当其每一个结点都与深度为个结点都与深度为k的满二叉树中编号从的满二叉树中编号从1至至n的结点一一对应时，称的结点一一对应时，称之为完全二叉树。之为完全二叉树。特点：特点：叶子结点只可能在层次最大的两层上出现；叶子结点只可能在层次最大的两层上出现； 对任一结点，若其右分支下的子孙的最大层次为对任一结点，若其右分支下的子孙的最大层

26、次为l， 则其左分支下的子孙的最大层次必为则其左分支下的子孙的最大层次必为l或或l1。8 9 10 11 12 13 14 15 12 34 5 6 7(a) 满二叉树满二叉树(b) 完全二叉树完全二叉树8 9 10 11 12 12 34 5 6 7图图6.4特殊形态的二叉树特殊形态的二叉树6 7 1 12 3 2 34 5 4 5 6(c) 非完全二叉树非完全二叉树 (d) 非完全二叉树非完全二叉树6.2.2 二叉树的性质二叉树的性质性质一：在二叉树的第性质一：在二叉树的第i层上至多有层上至多有2i-1个结点，个结点，(i1)。性质二：深度为性质二：深度为k的二叉树至多有的二叉树至多有2k

27、1个结点，个结点，(k1)。性质三：对任何一棵二叉树性质三：对任何一棵二叉树T，如果其终端结点数为，如果其终端结点数为n0，度为，度为2的结的结 点数为点数为n2，则，则n0 = n2 + 1。性性质四：具有四：具有n个个结点的完全二叉点的完全二叉树的深度的深度为 。）性质五：如果一棵有性质五：如果一棵有n个结点的完全二叉树（其深度为个结点的完全二叉树（其深度为的结点按层序编号的结点按层序编号(从第从第1层到第层到第 到右到右),则对任一结点则对任一结点i(1in),有有层，每层从左层，每层从左（1）如果）如果i1，则结点，则结点i是二叉树的根，无双亲；如果是二叉树的根，无双亲；如果i1， 则

28、其双亲则其双亲PARENT(i)是结点是结点 。 （2）如果）如果2i n，则结点，则结点i无左孩子（结点无左孩子（结点i为叶子结点）；为叶子结点）； 否则其左孩子否则其左孩子LCHILD(i)是结点是结点2i。（3）如果）如果2i1 n，则结点，则结点i无右孩子；否则其右孩子无右孩子；否则其右孩子 RCHILD(i)是结点是结点2i1。6. 3 二叉树的存储结构二叉树的存储结构6.3.1 顺序存储结构顺序存储结构 /-二叉树的顺序存储表示二叉树的顺序存储表示-#defineMAX_TREE_SIZE100 /二叉树的最大结点数二叉树的最大结点数typedefTElemType SqBiTre

29、eMAX_TREE_SIZE; /0号单元存储根结点号单元存储根结点SqBiTree bt; 用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素，即将完全二叉树上编号为点元素，即将完全二叉树上编号为i的结点元素存储在如上定义的一维数组中下标的结点元素存储在如上定义的一维数组中下标为为i1的分量中。的分量中。 例如，图例如，图6.5所示为图所示为图6.4(b)所示完全二叉树和图所示完全二叉树和图6.4(c)所示二叉树的顺序存储所示二叉树的顺序存储结构。结构。 图图6.5二叉树的顺序存储结构二叉树的顺序存储结构

30、1 2 3 4 5 6 7 8 9 10 11 121 2 3 4 5 0 0 0 0 6 7(a)完全二叉树完全二叉树(b)一般二叉树一般二叉树图中以图中以“0”表表示不存在示不存在此结点此结点结点结构结点结构 lchild data rchild其中，其中，data：数据域；：数据域； lchild：左指针域，指向该结点的左孩子；：左指针域，指向该结点的左孩子； rchild：右指针域，指向该结点的右孩子。：右指针域，指向该结点的右孩子。6.3.2 链序存储结构链序存储结构（1）二叉链表）二叉链表定义定义 二叉链表二叉链表：用上述结点结构所得二叉树的存储结构称之为二叉链表。：用上述结点结构

31、所得二叉树的存储结构称之为二叉链表。图形表示图形表示 A AB BC CD DC D C DA AB BE F E F G G(a)单支树的二叉链表单支树的二叉链表 (b)二叉链表二叉链表图图6.7二叉链表存储结构二叉链表存储结构易知，在含有易知，在含有n个结点的二叉链个结点的二叉链表中有表中有n1个空链域。个空链域。typedef struct BiTNode TElemType data;struct BiTNode *lchild, *rchild;/左右孩子指针左右孩子指针 BiTNode, * BiTree二叉链表的存储表示二叉链表的存储表示Status CreateBiTree (

32、BiTree &T);/按先后次序输入二叉树中结点的值（一个字符），空格字符表示空树，按先后次序输入二叉树中结点的值（一个字符），空格字符表示空树，/构造二叉链表表示的二叉树构造二叉链表表示的二叉树T。 Status PreOrderTraverse (BiTree T, Status ( * Visit )( TElemType e);/采用二叉链表存储结构，采用二叉链表存储结构，Visit是对结点操作的应用函数。是对结点操作的应用函数。/先序遍历先序遍历T，对每个结点调用函数，对每个结点调用函数Visit()一次且仅一次。一次且仅一次。/一旦一旦Visit()失败，则操作失败。失败，则操作

33、失败。 Status InOrderTraverse (BiTree T, Status ( * Visit )( TElemType e);/采用二叉链表存储结构，采用二叉链表存储结构，Visit是对结点操作的应用函数。是对结点操作的应用函数。/中序遍历中序遍历T，对每个结点调用函数，对每个结点调用函数Visit()一次且仅一次。一次且仅一次。/一旦一旦Visit()失败，则操作失败。失败，则操作失败。/-基本操作的函数原型说明（部分）基本操作的函数原型说明（部分）-lchild data parent rchild Status PostreOrderTraverse (BiTree T,

34、 Status ( * Visit )( TElemType e);/采用二叉链表存储结构，采用二叉链表存储结构，Visit是对结点操作的应用函数。是对结点操作的应用函数。/后序遍历后序遍历T，对每个结点调用函数，对每个结点调用函数Visit()一次且仅一次。一次且仅一次。/一旦一旦Visit()失败，则操作失败。失败，则操作失败。 Status LevelOrderTraverse (BiTree T, Status ( * Visit )( TElemType e);/采用二叉链表存储结构，采用二叉链表存储结构，Visit是对结点操作的应用函数。是对结点操作的应用函数。/层序遍历层序遍历T

35、，对每个结点调用函数，对每个结点调用函数Visit()一次且仅一次。一次且仅一次。/一旦一旦Visit()失败，则操作失败。失败，则操作失败。其中，其中，data：数据域；：数据域； lchild：左指针域，指向该结点的左孩子；：左指针域，指向该结点的左孩子； rchild：右指针域，指向该结点的右孩子；：右指针域，指向该结点的右孩子； parent：双亲指针域，指向该结点的双亲结点。：双亲指针域，指向该结点的双亲结点。（2）三叉链表）三叉链表结点结构结点结构定义定义 三叉链表三叉链表：用上述结点结构所得二叉树的存储结构称之为三叉链表：用上述结点结构所得二叉树的存储结构称之为三叉链表 图形表示

36、图形表示图图6.8三叉链表存储结构三叉链表存储结构 A B C DE FGA B C DE FG6.4 二叉树的遍历与线索化二叉树的遍历与线索化6.4.1 二叉树的遍历二叉树的遍历 遍历二叉树遍历二叉树（traversing binary tree）：按某条搜索路径巡访树中的每）：按某条搜索路径巡访树中的每个结点，使得每个结点均被访问一次，而且仅被访问一次。个结点，使得每个结点均被访问一次，而且仅被访问一次。 例如，图例如，图6.9所示的二叉树表示下述表达式：所示的二叉树表示下述表达式：a + b * (cd)e / f。先序遍历：先序遍历：+ a * bc d / e f表达式的前缀表示（波

37、兰式）表达式的前缀表示（波兰式）中序遍历：中序遍历：a + b * cde / f表达式的中缀表示表达式的中缀表示后序遍历：后序遍历：a b c d* + e f /表达式的后缀表示（逆波兰式）表达式的后缀表示（逆波兰式）层序遍历：层序遍历：+ / a * e f bcd图图6.9( a + b * (cd)e / f )表达式的二叉树表达式的二叉树- + / a * e fb -c d（1）递归算法）递归算法先序遍历先序遍历二叉树的操作定义为：二叉树的操作定义为：若二叉树为空，则空操作；否则若二叉树为空，则空操作；否则访问根结点；访问根结点；先序遍历左子树；先序遍历左子树；先序遍历右子树。先

38、序遍历右子树。中序遍历中序遍历二叉树的操作定义为：二叉树的操作定义为：若二叉树为空，则空操作；否则若二叉树为空，则空操作；否则中序遍历左子树；中序遍历左子树； 访问根结点；访问根结点；中序遍历右子树。中序遍历右子树。后序遍历后序遍历二叉树的操作定义为：二叉树的操作定义为：若二叉树为空，则空操作；否则若二叉树为空，则空操作；否则后序遍历左子树；后序遍历左子树； 后序遍历右子树；后序遍历右子树；访问根结点。访问根结点。层序遍历层序遍历二叉树的操作定义为：二叉树的操作定义为：若二叉树为空，则空操作；否则若二叉树为空，则空操作；否则按从上到下，从左到右的次序访问各结点。按从上到下，从左到右的次序访问各

39、结点。Status PreOrderTraverse (BiTree T, Status ( * Visit )( TElemType e) /采用二叉链表存储结构，采用二叉链表存储结构，visit是对数据元素操作的应用函数。是对数据元素操作的应用函数。/先序遍历二叉树先序遍历二叉树T的递归算法，对每个数据元素调用函数的递归算法，对每个数据元素调用函数Visit。/最简单的最简单的Visit函数是：函数是：/Status PrintElement (TElemType e) /输出元素输出元素e的值的值/printf ( e );/实用时，加上格式串实用时，加上格式串/return OK;/调

40、用实例：调用实例：PreOrderTraverse (T, PrintElement);if (T) if (Visit (Tdata) if (PreOrderTraverse (Tlchild, Visit)if (PreOrderTraverse (Trchild, Visit) return OK;return ERROR;elsereturn OK; / PreOrderTraverse若定义二叉树的存储结构为二叉链表，则有先序遍历二叉树的递归算法若定义二叉树的存储结构为二叉链表，则有先序遍历二叉树的递归算法6.1如下：如下：（2）非递归算法）非递归算法以中序遍历为例说明二叉树遍历的

41、非递归算法。以中序遍历为例说明二叉树遍历的非递归算法。 仿照递归算法执行过程中递归工作栈的状态变化状况可直接写成相应仿照递归算法执行过程中递归工作栈的状态变化状况可直接写成相应的非递归算法：的非递归算法：工作记录中包含两项，其一是递归调用的语句编号，其二是指向根工作记录中包含两项，其一是递归调用的语句编号，其二是指向根 结点的指针，则当栈顶记录中的指针非空时，应遍历左子树，即指结点的指针，则当栈顶记录中的指针非空时，应遍历左子树，即指 向左子树树根的指针进栈；向左子树树根的指针进栈； 若栈顶记录中的指针值为空，则应退至上一层，若是从左子树返回若栈顶记录中的指针值为空，则应退至上一层，若是从左子

42、树返回, 则应访问当前层即栈顶记录中指针所指的根结点；则应访问当前层即栈顶记录中指针所指的根结点；若是从右子树返回，则表明当前层的遍历结束，应继续退栈。若是从右子树返回，则表明当前层的遍历结束，应继续退栈。由上述分析可得两个中序遍历二叉树的非递归算法如下所示：由上述分析可得两个中序遍历二叉树的非递归算法如下所示：算法算法6.2如下：如下： Status InOrderTraverse (BiTree T, Status ( * Visit )( TElemType e) /采用二叉链表存储结构，采用二叉链表存储结构，visit是对数据元素操作的应用函数。是对数据元素操作的应用函数。/中序遍历二

43、叉树中序遍历二叉树T的非递归算法，对每个数据元素调用函数的非递归算法，对每个数据元素调用函数Visit。InitStack (S);Push (S, T);/根指针进栈根指针进栈while (!StackEmpty (S) ) while (GetTop(S, p) & & p)Push (S, plchild);/向左走到尽头向左走到尽头Pop (S, p);if (!StackEmpty (S) ) /访问结点，向右一步访问结点，向右一步Pop (S, p);if (!Visit (pdata) )return ERROR;Push (S, prchild); / if / whilere

44、turn OK; / InOrderTraverse算法算法6.3如下：如下： Status InOrderTraverse (BiTree T, Status ( * Visit )( TElemType e) /采用二叉链表存储结构，采用二叉链表存储结构，visit是对数据元素操作的应用函数。是对数据元素操作的应用函数。/中序遍历二叉树中序遍历二叉树T的非递归算法，对每个数据元素调用函数的非递归算法，对每个数据元素调用函数Visit。InitStack (S);P = T;while (p | |!StackEmpty (S) ) if (p) /根指针进栈，遍历左子树根指针进栈，遍历左子

45、树Push (S, p);p = plchild; / ifelse /根指针退栈，访问根结点，遍历右子树根指针退栈，访问根结点，遍历右子树Pop (S, p);if (!Visit (pdata) )return ERROR;p = prchild); / else / whilereturn OK; / InOrderTraverse（3）二叉树的建立）二叉树的建立算法算法6.4是一个按先序序列建立二叉树的二叉链表的过程。是一个按先序序列建立二叉树的二叉链表的过程。 算法算法6.4如下：如下： Status CreateBiTree (BiTree &T) /按先序次序输入二叉树中结点的值

46、（一个字符），按先序次序输入二叉树中结点的值（一个字符），/空格字符表示空树，构造二叉链表表示的二叉树空格字符表示空树，构造二叉链表表示的二叉树T。scanf (&ch);if (ch = = )T = NULL; else if (!(T = (BiTNode *) malloc (sizeof (BiTNode) ) ) )exit (OVERFLOW);Tdata = ch;/生成根结点生成根结点CreateBiTree (Tlchild);/构造左子树构造左子树CreateBiTree (Trchild);/构造右子树构造右子树return OK; / CreateBiTree图图6.

47、10 二叉树二叉树例如，对图例如，对图6.10所示二叉树，按下列次序顺序读入字符：所示二叉树，按下列次序顺序读入字符：A B C D E F G A B CD EG F6.4.2 二叉树的线索化二叉树的线索化 当以二叉链表作为存储结构时，只能找到结点的左、右孩子信息，而不能直当以二叉链表作为存储结构时，只能找到结点的左、右孩子信息，而不能直接得到结点在任一序列（先序、中序或后序序列）中的前驱和后继信息，这种接得到结点在任一序列（先序、中序或后序序列）中的前驱和后继信息，这种信息只有在遍历的动态过程中才能得到。为了保存这种在遍历过程中得到的信信息只有在遍历的动态过程中才能得到。为了保存这种在遍历

48、过程中得到的信息，我们利用二叉链表中的空链域（由于结点没有左子树或右子树），来存放息，我们利用二叉链表中的空链域（由于结点没有左子树或右子树），来存放结点的前驱和后继信息。结点的前驱和后继信息。作如下规定：作如下规定： 若结点有左子树，则其若结点有左子树，则其lchild域指示其左孩子，否则令域指示其左孩子，否则令lchild域指示其前驱；域指示其前驱； 若结点有右子树，则其若结点有右子树，则其rchild域指示其右孩子，否则令域指示其右孩子，否则令rchild域指示其后继。域指示其后继。 （1）线索链表的结点结构）线索链表的结点结构lchild LTag data RTag rchild其中

49、：其中：data：数据域；：数据域； lchild：左指针域，指向该结点的左孩子；：左指针域，指向该结点的左孩子； rchild：右指针域，指向该结点的右孩子；：右指针域，指向该结点的右孩子； 0 lchild域指示结点的左孩子域指示结点的左孩子 LTag = 1 lchild域指示结点的前驱域指示结点的前驱 0 rchild域指示结点的右孩子域指示结点的右孩子 RTag = 1 rchild域指示结点的后继域指示结点的后继（2）线索链表的定义）线索链表的定义 线索链表线索链表：以上述结点结构构成的二叉链表作为二叉树的存储结构，称之：以上述结点结构构成的二叉链表作为二叉树的存储结构，称之为线索

50、链表。为线索链表。（3）相关术语）相关术语线索化线索化：对二叉树以某种次序遍历使其变为线性二叉树的过程。：对二叉树以某种次序遍历使其变为线性二叉树的过程。线索二叉树线索二叉树（Threaded Binary Tree）：加上线索的二叉树。）：加上线索的二叉树。线索线索：在线索链表中指向结点前驱和后继的指针。：在线索链表中指向结点前驱和后继的指针。（4）图形表示）图形表示-+ /a * e fb -c d-+ /NIL NILa * e fb -c d(a) ( a + b * (cd)e / f )表达式的二叉树表达式的二叉树(b) 中序线索二叉树中序线索二叉树图图6.11线索二叉树及其存储结

51、构线索二叉树及其存储结构thrt 0 1bt0 0 0 0 0 / 0 1 a 1 0 * 0 1 e 1 1 f 10 01 b 11 c 11 d 1(c) 中序线索链表中序线索链表图中，实线为指针（指向左、右子树），虚线为线索（指向前驱和后继）。图中，实线为指针（指向左、右子树），虚线为线索（指向前驱和后继）。（5）C语言描述语言描述 /-二叉树的二叉线索存储表示二叉树的二叉线索存储表示-typedef enum PointerTag Link, Thread;/Link = = 0:指针，指针，Thread = = 1:线索线索typedef struct BiThrNode TEle

52、mTypedata;struct BiThrNode *lchild, *rchild;/左右孩子指针左右孩子指针PointerTagLTag, RTag;/左右标志左右标志 BiThrNode, * BiThrTree;（6）遍历算法）遍历算法 仿照线性表的存储结构，在二叉树的线索链表上也添加一个头结点，并令其仿照线性表的存储结构，在二叉树的线索链表上也添加一个头结点，并令其lchild域的指针指向二叉树的根结点，其域的指针指向二叉树的根结点，其rchild域的指针指向中序遍历时访问的最域的指针指向中序遍历时访问的最后一个结点；反之，令二叉树中序序列中的第一个结点的后一个结点；反之，令二叉树

53、中序序列中的第一个结点的lchild域指针和最后一域指针和最后一个结点个结点rchild域的指针均指向头结点。这就为二叉树建立了一个双向线索链表，域的指针均指向头结点。这就为二叉树建立了一个双向线索链表，既可从第一个结点起顺后继进行遍历，也可从最后一个结点起顺前驱进行遍历。既可从第一个结点起顺后继进行遍历，也可从最后一个结点起顺前驱进行遍历。下述算法正是以双向线索链表为存储结构时对二叉树进行遍历的算法。下述算法正是以双向线索链表为存储结构时对二叉树进行遍历的算法。算法算法6.5如下：如下： Status InOrderTraverse_Thr (BiThrTree T, Status ( *

54、Visit )( TElemType e) /T指向头结点，头结点的左链指向头结点，头结点的左链lchild指向根结点，可参加线索化算法。指向根结点，可参加线索化算法。/中序遍历二叉线索树中序遍历二叉线索树T的非递归算法，对每个数据元素调用函数的非递归算法，对每个数据元素调用函数Visit。p = Tlchild;/p指向根结点指向根结点while (p != T) /空树或遍历结束时，空树或遍历结束时，p = = Twhile (pLTag = =Link)p = plchild;if (!Visit (pdata) )return ERROR;/访问其左子树为空的结点访问其左子树为空的结点

55、while (pRTag = = Thread & & prchild != T) p = prchild;Visit (pdata);/访问后继结点访问后继结点p = prchild;return OK; / InOrderTraverse_Thr（7）二叉树的线索化算法）二叉树的线索化算法算法算法6.6如下：如下： Status InOrderThreading (BiThrTree &Thrt, BiThrTree T) /中序遍历二叉线索树中序遍历二叉线索树T，并将其中序线索化，并将其中序线索化，Thrt指向头结点。指向头结点。if (!(Thrt = (BiThrTree) mall

56、oc (sizeof (BiThrNode)exit (OVERFLOW);ThrtLTag = Link;ThrtRTag = Thread;/建头结点建头结点Thrtrchild = Thrt;/右指针回指右指针回指if (!T)/若二叉树空，则左指针回指若二叉树空，则左指针回指Thrtlchild = Thrt;else Thrtlchild = T;pre = Thrt;InThreading (T);/中序遍历进行中序线索化中序遍历进行中序线索化prerchild = Thrt;preRTag = Thread;/最后一个结点线索化最后一个结点线索化Thrtrchild = pre;

57、 / elsereturn OK; / InOrderThreading指针指针pre始终指向刚刚访问过的结点始终指向刚刚访问过的结点,若指针若指针p指向当前访问的结点指向当前访问的结点,则则pre指向它的前驱指向它的前驱 算法算法6.7如下：如下： void InThreading (BiThrTree p) if (p) InThreading (plchild);/左子树线索化左子树线索化if (! plchild) /前驱线索前驱线索pLTag = Thread;plchild = pre;if (! prerchild) /后继线索后继线索preRTag = Thread;prerc

58、hild = p;pre = p;InThreading (prchild);/右子树线索化右子树线索化 / if / InThreading线索化的过程是在遍历过程中修改二叉链表中线索化的过程是在遍历过程中修改二叉链表中的空指针为指向前驱或后继的线索的过程。的空指针为指向前驱或后继的线索的过程。 6.5 树和森林树和森林6.5.1 树的存储结构树的存储结构（1）双亲表示法）双亲表示法C语言描述语言描述 假设以一组连续空间存储树的结点，同时在每个结点中附设一个指示器假设以一组连续空间存储树的结点，同时在每个结点中附设一个指示器指示其双亲结点在链表中的位置。指示其双亲结点在链表中的位置。 #de

59、fineMAX_TREE_SIZE100 typedef struct PTNode /结点结构结点结构TElemTypedata;int parent;/双亲位置域双亲位置域 PTNode typedef struct /树结构树结构PTNodenodesMAX_TREE_SIZE;intr, n;/根的位置和结点数根的位置和结点数 PTree;图形表示 数组下标图图6.12树的双亲表示法示例树的双亲表示法示例RABCDEFGKH数组下标数组下标0 R -11 A 02 B 03 C 04 D 15 E 16 F 37 G 68 H 69 K 6（2）孩子表示法）孩子表示法定义定义 孩子表示

60、法：把每个结点的孩子结点排列起来，看成是一个线性表，孩子表示法：把每个结点的孩子结点排列起来，看成是一个线性表，且以单链表作存储结构，则且以单链表作存储结构，则n个结点有个结点有n个孩子链表（叶子的孩子链表为个孩子链表（叶子的孩子链表为空表）。而空表）。而n个头指针又组成一个线性表，为了便于查找，可采用顺序存个头指针又组成一个线性表，为了便于查找，可采用顺序存储结构。储结构。 C语言描述语言描述typedef struct CTNode /孩子结点孩子结点int child;struct CTNode *next; * ChildPtrtypedef struct TElemType data

61、;ChildPtr firstchild;/孩子链表头指针孩子链表头指针 CTBox;typedef struct CTBox nodesMAX_TREE_SIZE;int n, r;/结点数和根的位置；结点数和根的位置； CTree RABCDEFGKH 图形表示图形表示(a) 原树原树 (b) 孩子链表孩子链表0 A 3 51 B2 C 63 D4 R 0 1 25 E6 F 7 8 97 G8 H9 K 上图上图(c)是把双亲表示法和孩子表示法结合起来，即将双亲表示和孩是把双亲表示法和孩子表示法结合起来，即将双亲表示和孩子链表合在一起的存储结构。子链表合在一起的存储结构。(c) 带双亲的

62、孩子链表带双亲的孩子链表图图6.13树的另外两种表示法树的另外两种表示法0 4 A 3 5 1 4 B2 4 C 6 3 0 D4 -1 R 0 1 26 2 F 7 8 95 0 E7 6 G8 6 H9 6 K（3）孩子兄弟表示法）孩子兄弟表示法定义定义 孩子兄弟表示法：又称二叉树表示法，或二叉链表表示法。即以二叉孩子兄弟表示法：又称二叉树表示法，或二叉链表表示法。即以二叉链表作树的存储结构。链表中的两个域分别指向该结点的第一个孩子结点链表作树的存储结构。链表中的两个域分别指向该结点的第一个孩子结点和下一个兄弟结点。和下一个兄弟结点。C语言描述语言描述typedef struct CSNo

63、de TElemType data;struct CSNode *firstchild, *nextsibling; CSNode , * CSTreeRABCDEFGKH 图形表示图形表示图图6.14树的二叉链表表示法树的二叉链表表示法 R ABDEFGKHC6.5.2 森林与二叉树的转换森林与二叉树的转换（1）森林转换成二叉树）森林转换成二叉树 如果如果F = T1, T2, ,Tm是森林，则可按如下规则转换成一棵二叉树是森林，则可按如下规则转换成一棵二叉树B = (root, LB, RB)。 若若F为空，即为空，即m0，则，则B为空树；为空树； 若若F非空，即非空，即m0，则，则B的根

64、的根root即为森林中第一棵树的根即为森林中第一棵树的根ROOT(T1)； B的左子树的左子树LB是从是从T1中根结点的子树森林中根结点的子树森林F1 = T11, T12, ,T1m转换而转换而 成的二叉树成的二叉树;其右子树其右子树RB是从森林是从森林F = T2, T3, ,Tm转换而成的二叉树。转换而成的二叉树。（2）二叉树转换成森林）二叉树转换成森林 如果如果B = (root, LB, RB)是一棵二叉树，则可按如下规则转换成森林是一棵二叉树，则可按如下规则转换成森林F = T1, T2, ,Tm。 若若B为空，则为空，则F为空；为空；若若B非空，则非空，则F中第一棵树中第一棵树T

65、1的根的根ROOT(T1)即为二叉树即为二叉树B的根的根root；T1中中 的根结点的子树森林的根结点的子树森林F1是由是由B的左子树的左子树LB转换而成的森林；转换而成的森林；F中除中除T1之外之外 其余树组成的森林其余树组成的森林F = T2, T3, ,Tm是由是由B的右子树的右子树RB转换而成的森林。转换而成的森林。例，图例，图6.15展示了森林与二叉树之间的对应关系。展示了森林与二叉树之间的对应关系。图图6.15 森林与二叉树的对应关系森林与二叉树的对应关系 森林与二叉树对应森林与二叉树对应 A B C DEF 树与二叉树对应树与二叉树对应 A BCD树根相连树根相连EFGH IJG

66、JIHB E A JIHCDGF6.5.3 树和森林的遍历树和森林的遍历树的遍历方法：树的遍历方法： 先根（次序）遍历，即：先访问树的根结点，然后依次先根遍历根的每先根（次序）遍历，即：先访问树的根结点，然后依次先根遍历根的每 棵子树；棵子树； 后根（次序）遍历，即：先依次后根遍历每棵子树，然后访问根结点。后根（次序）遍历，即：先依次后根遍历每棵子树，然后访问根结点。例如，对图例如，对图6.16的树进行遍历，可得树的序列为：的树进行遍历，可得树的序列为： 先根遍历：先根遍历：A B C D E后根遍历：后根遍历：B D C E A 图图6.16 ACDEB森林的遍历方法：森林的遍历方法： 先序

67、遍历森林先序遍历森林 若森林非空，则可按下述规则遍历之：若森林非空，则可按下述规则遍历之：1访问森林中第一棵树的根结点；访问森林中第一棵树的根结点；2先序遍历第一棵树中根结点的子树森林；先序遍历第一棵树中根结点的子树森林；3先序遍历除去第一棵树之后剩余的树构成的森林。先序遍历除去第一棵树之后剩余的树构成的森林。中序遍历森林中序遍历森林 若森林非空，则可按下述规则遍历之：若森林非空，则可按下述规则遍历之：1中序遍历森林中第一棵树的根结点的子树森林；中序遍历森林中第一棵树的根结点的子树森林； 2访问第一棵树的根结点；访问第一棵树的根结点；3中序遍历除去第一棵树之后剩余的树构成的森林。中序遍历除去第

68、一棵树之后剩余的树构成的森林。例如，对图例如，对图6.15中森林进行遍历，得到森林的序列为：中森林进行遍历，得到森林的序列为：先序遍历：先序遍历： A B C D E F G H I J中序遍历：中序遍历： B C D A F E H J I G6.6 赫夫曼树及其应用赫夫曼树及其应用6.6.1 最优二叉树（赫夫曼树最优二叉树（赫夫曼树）（1）基本概念）基本概念路径路径：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。 路径长度路径长度：路径上分分支数目。：路径上分分支数目。 树树的路径长度：从树根到每一结点的路径长

69、度之和。：从树根到每一结点的路径长度之和。 结点结点的带权带权路径长度：指从该结点到树根之间的路径长度与结点上权的乘积。：指从该结点到树根之间的路径长度与结点上权的乘积。 树树的带权带权路径长度：树中所有叶子结点的带权路径长度之和，通常记作：树中所有叶子结点的带权路径长度之和，通常记作： 最优二叉树最优二叉树（或（或赫夫曼树赫夫曼树）：带权路径长度）：带权路径长度WPL最小的二叉树。最小的二叉树。 例例1，图，图6.17中中3棵二叉树，都有棵二叉树，都有4个叶子结点个叶子结点a、b、c、d，分别带权，分别带权7、5、2、4，它们的带权路径长度分别为：，它们的带权路径长度分别为： (a) WPL

70、 = 7252224236(b) WPL = 7353214246(c) WPL = 7152234335图图6.17具有不同带权路径长度的二叉树具有不同带权路径长度的二叉树 2 7 e a7 5 2 4 4 5a b c d d b 7 5 2 4a b c d (a) (b) (c)例例2，利用赫夫曼树得到最佳判定树（见书，利用赫夫曼树得到最佳判定树（见书P144）。）。 （2）赫夫曼树的构造）赫夫曼树的构造赫夫曼算法：赫夫曼算法： 根据给定的根据给定的n个权值个权值w1, w2, , wn构成构成n棵二叉树的集合棵二叉树的集合F = T1, T2, , Tn， 其中每棵二叉树其中每棵二叉

71、树Ti中只有一个带权为中只有一个带权为wi的根结点，其左右子树均空。的根结点，其左右子树均空。 在在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且 置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。 在在F中删除这两棵树，同时将新得到的二叉树加入中删除这两棵树，同时将新得到的二叉树加入F中。中。 重复重复和和，直到，直到F只含一棵树为止。这棵树便是赫夫曼树。只含一棵树为止。这棵树便是赫夫曼树。 例如，图例如，图6.18展示了图展示了图6.17

72、的赫夫曼树的构造过程。其中，根结点上标注的数字的赫夫曼树的构造过程。其中，根结点上标注的数字是所赋的权。是所赋的权。 7 5 2 4a b c d (a) (b)7 5 6a bc db7 11 c da18 bc da (c) (d) 图图6.18 赫夫曼树的构造过程赫夫曼树的构造过程 6.6.2 赫夫曼编码赫夫曼编码（1）前缀编码）前缀编码 前缀编码前缀编码：任一个字符的编码都不是另一个字符的编码的前缀，这种编码：任一个字符的编码都不是另一个字符的编码的前缀，这种编码称做前缀编码。称做前缀编码。 约定：在二叉树中，左分支表示字符约定：在二叉树中，左分支表示字符0，右分支表示字符，右分支表示

73、字符1，则可以从根，则可以从根结点到叶子结点的路径上分支字符组成的字符串作为该叶子结点字符的编码。结点到叶子结点的路径上分支字符组成的字符串作为该叶子结点字符的编码。 例如，假设有图例如，假设有图6.19所示的二叉树，其所示的二叉树，其4个叶子结点分别表示个叶子结点分别表示A、B、C、D这这4个字符。个字符。 由图由图6.19所得所得A、B、C、D的二进制前缀编码分别为的二进制前缀编码分别为0、10、110、111 编码编码 A(0) 0 1 B(10) A C(110) 0 1 D(111)B C D 图图6.19前缀编码示例前缀编码示例（2）赫夫曼编码）赫夫曼编码 由此可见，设计电文总长最

74、短的二进制前缀编码即为以由此可见，设计电文总长最短的二进制前缀编码即为以n种字符出现的频率种字符出现的频率作权作权,设计一棵赫夫曼树的问题设计一棵赫夫曼树的问题,由此得到的二进制前缀编码便称为由此得到的二进制前缀编码便称为赫夫曼编码赫夫曼编码。 假设每种字符在电文中出现的次数为假设每种字符在电文中出现的次数为wi，其编码长度为，其编码长度为li，电文中只有，电文中只有n种种。对应到二叉树上，若置。对应到二叉树上，若置wi为叶子结点的权为叶子结点的权,li字符，则电文总长为字符，则电文总长为恰为从根到叶子的路径长度，则恰为从根到叶子的路径长度，则恰为二叉树上带权路径长度。恰为二叉树上带权路径长度

75、。（3）赫夫曼树和赫夫曼编码的存储表示）赫夫曼树和赫夫曼编码的存储表示typedef struct unsignedintweight;unsignedintparent, lchild, rchild; HTNode, * HuffmanTree/动态分配数组存储赫夫曼树动态分配数组存储赫夫曼树typedef char * HuffmanCode;/动态分配数组存储赫夫曼编码表动态分配数组存储赫夫曼编码表（4）求赫夫曼编码的算法）求赫夫曼编码的算法 void HuffmanCoding (HuffmanTree &HT, HuffmanCode &HC, int *w, int n) /w存

76、放存放n个字符的权值个字符的权值(均均0)构造赫夫曼树构造赫夫曼树HT，/并求出并求出n个字符的赫夫曼编码个字符的赫夫曼编码HC。if (n = 1)return;m = 2 * n 1;HT = (HuffmanTree) malloc (m + 1) * sizeof (HTNode); /0号单元未用号单元未用for (p = HT, i = 1; i = n; +i, +p ,+w)*p = *w, 0, 0, 0;for (; i = m; +i, +p)*p = 0, 0, 0, 0;for (i = n+1; i = m; +i) /建赫夫曼树建赫夫曼树/在在HT1.i-1选择选

77、择parent为为0且且weight最小的两个结点，最小的两个结点，/其序号分别为其序号分别为s1和和s2 Select (HT, i 1, s1, s2); HTs1.parent = i; HTs2.parent = i; HTi.lchild = s1; HTi.rchild = s2; HTi.weight = HTs1.weight + HTs2.weight; / for算法算法6.8如下：如下：向量向量HT的前的前n个个分量表示叶子结分量表示叶子结点，最后一个分点，最后一个分量表根结点。量表根结点。 /- - - - - 从叶子到根逆向求每个字符的赫夫曼编码从叶子到根逆向求每个字

78、符的赫夫曼编码 - - - - - - - HC = (HuffmanCode)malloc(n + 1)*sizeof(char*); /分配分配n个字符编码的头指针向量个字符编码的头指针向量cd = (char *) malloc (n * sizeof (char); /分配求编码的工作空间分配求编码的工作空间cdn 1 = “0”; /编码结束符编码结束符for (i = 1; i = n; +i) /逐个字符求赫夫曼编码逐个字符求赫夫曼编码 start = n 1; /编码结束符位置编码结束符位置 for (c = i, f = HTi.parent; f != 0; c = f,

79、f = HTf.parent) /从叶子到根逆向求编码从叶子到根逆向求编码 if (HTf.lchild = = c) cd start = 0; else cd start = 1; HCi = (char *) malloc (n start) * sizeof (char); /为第为第i个字符编码分配空间个字符编码分配空间 strcpy (HCi, &cdstart); /从从cd复制编码复制编码(串串)到到HC / forfree (cd); /释放工作空间释放工作空间 / HuffmanCoding 在算法在算法6.8中，求每个字符的赫夫曼编码是从叶子到根逆向处理的。也可以从中，求

80、每个字符的赫夫曼编码是从叶子到根逆向处理的。也可以从根出发，遍历整棵赫夫曼树，求得各个叶子结点所表示的字符的赫夫曼编码如算根出发，遍历整棵赫夫曼树，求得各个叶子结点所表示的字符的赫夫曼编码如算法法6.9所示。所示。算法算法6.9如下：如下： /-无栈非递归遍历赫夫曼树，求赫夫曼编码无栈非递归遍历赫夫曼树，求赫夫曼编码-HC = (HuffmanCode) malloc (n + 1) * sizeof (char *);p = m;cdlen = 0;for (i = 1; i = m; +i) HTi.weight = 0;/遍历赫夫曼树时用作结点状态标志遍历赫夫曼树时用作结点状态标志whi

81、le (p) if (HTp.weight = = 0) /向左向左HTp.weight = 1;if (HTp.lchild != 0) p = HTp.lchild;cdcdlen + = “0”; else if (HTp.rchild = = 0) /登记叶子结点的字符的编码登记叶子结点的字符的编码HCp = (char *) malloc (cdlen + 1) * sizeof (char );cdcdlen = “0”;strcpy (HCp, cd);/复制编码复制编码(串串) / else if / ifelse if (HTp.weight = = 1) /向左向左 HTp

82、.weight = 2; if (HTp.rchild != 0) p = HTp.rchild;cdcdlen+ = “1”; else HTp.weight = 0; p = HTp.parent; cdlen;/退到父结点，编码长度减退到父结点，编码长度减1 / else / while（5）例子）例子 已知某系统在通信联络中只可能出现已知某系统在通信联络中只可能出现8种字符，其概率分别为种字符，其概率分别为0.05, 0.29, 0.07, 0.08, 0.14, 0.23, 0.03, 0.11，试设计赫夫曼编码。，试设计赫夫曼编码。 设权设权w5, 29, 7, 8, 14, 23

83、, 3, 11, n = 8，则，则m15，按上述算法可构造一棵赫，按上述算法可构造一棵赫夫曼树如图夫曼树如图6.20所示。其存储结构所示。其存储结构HT的初始状态如图的初始状态如图6.21(a)所示，其终结状态所示，其终结状态如图如图6.21(b)所示，所得赫夫曼编码如图所示，所得赫夫曼编码如图6.21(c)所示。所示。 图图6.20 赫夫曼树赫夫曼树0 1 0 1 0 1 23 29 11 14 0 1 0 1 0 1 0 1 5 3 7 8 HTweight parent lchild rchildweight parent lchild rchild HT1 5 0 0 0 15 9

84、0 02 29 0 0 0 229 14 0 03 7 0 0 0 37 10 0 04 8 0 0 0 48 10 0 05 14 0 0 0 514 12 0 06 23 0 0 0 623 13 0 07 3 0 0 0 73 9 0 08 11 0 0 0 811 11 0 09 0 0 0 98 11 1 710 0 0 0 1015 12 3 411 0 0 0 1119 13 8 912 0 0 0 1229 14 5 1013 0 0 0 1342 15 6 1114 0 0 0 1458 15 2 1215 0 0 0 15 100 0 13 14(a) HT的初态的初态 (b) HT的终态的终态 (c) 赫夫曼编码赫夫曼编码HC图图6.21 存储结构存储结构HC 1 2 3 4 5 6 7 8 0 1 1 0 1 0 1 1 1 0 1 1 1 1 1 1 0 0 0 0 1 1 1 0 1 0