第08章 数和二叉树

1、第第8 8章章 树和二叉树树和二叉树 树树 二叉树二叉树 二叉树设计二叉树设计 二叉树遍历二叉树遍历 线索二叉树线索二叉树 哈夫曼树哈夫曼树 等价问题等价问题 树与二叉树的转换树与二叉树的转换 树的遍历树的遍历 主要知识点主要知识点 8.1 8.1 树树 树是由树是由n(n0)个结点组成的有限集合个结点组成的有限集合T。n=0的树称为空的树称为空 树；对树；对n0的树，有的树，有:(1)仅有仅有一个特殊的结点称为根结点一个特殊的结点称为根结点，根，根 结点没有前驱结点；结点没有前驱结点；(2)当当n1时，除根结点外其余的结点分为时，除根结点外其余的结点分为 m(m0)个个互不相交互不相交的有限

2、集合的有限集合T1,T2，Tm，其中每个集合，其中每个集合 Ti本身又是一棵结构和树类似的子树。本身又是一棵结构和树类似的子树。 注：注：树的定义具有树的定义具有递归性递归性，即，即“树中还有树树中还有树”。 结点：结点：由数据元素和构造数据元素之由数据元素和构造数据元素之 间关系的指针组成间关系的指针组成 A BC GEI D HFJ FLK 结点的度结点的度：结点所拥有的子树的个数结点所拥有的子树的个数 叶结点叶结点：度为度为0 0的结点，也称作的结点，也称作 终端结点终端结点 分支结点分支结点：度不为度不为0 0的结点的结点 孩子结点孩子结点：树中一个结点的子树的根结点树中一个结点的子树

3、的根结点 双亲结点双亲结点：若树中某结点有孩子结点，则这个结点就若树中某结点有孩子结点，则这个结点就 称作它的孩子结点的双亲结点称作它的孩子结点的双亲结点 兄弟结点兄弟结点：具有相同的双亲结点的结点具有相同的双亲结点的结点 树的度树的度：树中所有结点的度的最大值树中所有结点的度的最大值 结点的层次：结点的层次：从根结点到树中某结点所经路径上的分支数从根结点到树中某结点所经路径上的分支数 树的深度：树的深度：树中所有结点的层次的最大值树中所有结点的层次的最大值 无序树：无序树：树中任意一个结点的各孩子结点之间的次序树中任意一个结点的各孩子结点之间的次序 构成无关紧要的树构成无关紧要的树 有序树：

4、有序树：树中任意一个结点的各孩子结点有严格排列树中任意一个结点的各孩子结点有严格排列 次序的树次序的树 森林：森林：m（m0）棵树的集合）棵树的集合 (1)(1)直观表示法直观表示法 (2)(2)形式化表示法形式化表示法 (3)(3)凹入表示法凹入表示法 T=（D，R） DF = D1D2Dm （1i,jm, DiDj=） R=, i=1,2,n-1 A A B B C C D D E E F F G G H H I I J J K K L L 数据集合数据集合: 树的结点集合，每个结点由数据元素和构造数树的结点集合，每个结点由数据元素和构造数 据元素之间关系的指针组成。据元素之间关系的指针组

5、成。 操作集合操作集合: （1 1）创建创建MakeTree(TMakeTree(T) ) （2 2）撤消撤消DestroyTree(TDestroyTree(T) ) （3 3）双亲结点双亲结点Parent(T, currParent(T, curr) ) （4 4）左孩子结点左孩子结点LeftChild(T, currLeftChild(T, curr) ) （5 5）右兄弟结点右兄弟结点RightSibling(T, currRightSibling(T, curr) ) （6 6）遍历树遍历树Traverse(T, Visit()Traverse(T, Visit() 树的结点之间的逻

6、辑关系主要有双亲树的结点之间的逻辑关系主要有双亲- -孩子关系，孩子关系， 兄弟关系。因此，从结点之间的逻辑关系分，树的存兄弟关系。因此，从结点之间的逻辑关系分，树的存 储结构主要有：储结构主要有：双亲表示法、孩子表示法、双亲孩子双亲表示法、孩子表示法、双亲孩子 表示法和孩子兄弟表示法表示法和孩子兄弟表示法四种组合。四种组合。 指针有指针有常规指针常规指针和和仿真指针仿真指针 4 H 2G 1F 1E 1D 0C 0B -1A I4 data parentdata parent 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 A B DEF HI C G (1)(1)双

7、亲表示法双亲表示法 (a)一棵树一棵树 （b)仿真指针的双亲表示法存储结构仿真指针的双亲表示法存储结构 树及其使用仿真指针的双亲表示法树及其使用仿真指针的双亲表示法 (2)(2)孩子表示法孩子表示法 常规指针的孩子表示法常规指针的孩子表示法 root B A C DEFG HI 双亲孩子表示法存储结构双亲孩子表示法存储结构 (3)(3)双亲孩子表示法双亲孩子表示法 4 H 2G 1F 1E 1D 0C 0B -1A I4 data parent head 0 1 2 3 4 5 6 7 8 child next 87 12 345 6 (4)(4)孩子兄弟表示法孩子兄弟表示法 常规指针的孩子兄

8、弟表示法常规指针的孩子兄弟表示法 root BC DEFG HI A 8.2 8.2 二叉树二叉树 一、二叉树：一、二叉树：是是n(n0)个结点的有限集合。个结点的有限集合。n=0的树称为空二的树称为空二 叉树；叉树；n0的二叉树由一个根结点以及两棵互不相交的、的二叉树由一个根结点以及两棵互不相交的、 分别称为分别称为左子树和右子树左子树和右子树的二叉树组成的二叉树组成 。 逻辑结构：逻辑结构： 一对二（一对二（1:2） 基本特征基本特征: 每个结点最多只有两棵子树（不存在度大于每个结点最多只有两棵子树（不存在度大于2的结点）；的结点）； 左子树和右子树左子树和右子树次序不能颠倒次序不能颠倒。

9、所以下面是两棵不同。所以下面是两棵不同 的树的树 注意注意：二叉树不是有序树二叉树不是有序树 B A C E D F G B A C E D F G 二、满二叉树：二、满二叉树：在一棵二叉树中，如果所有分支结点都存在左在一棵二叉树中，如果所有分支结点都存在左 子树和右子树，并且所有叶子结点都在同一层上，这样的子树和右子树，并且所有叶子结点都在同一层上，这样的 二叉树称为满二叉树。二叉树称为满二叉树。 三、完全二叉树：三、完全二叉树：如果一棵深度为如果一棵深度为k k，有，有n n个结点的二叉树中各个结点的二叉树中各 结点能够与深度为结点能够与深度为k k的顺序编号的满二叉树从的顺序编号的满二叉

10、树从0 0到到n-1n-1标号的标号的 结点相对应的二叉树称为完全二叉树。如下图所示结点相对应的二叉树称为完全二叉树。如下图所示 B A C EDFG HIJKLMNO (a)满二叉树满二叉树 B A C EDFG HIJ (b)完全二叉树完全二叉树 问题问题: :一个高度为一个高度为h h的完全二叉树最多有多少个结点的完全二叉树最多有多少个结点? ?最最 少有多少个结点少有多少个结点? ? 数据集合：数据集合：二叉树的结点集合，每个结点由数据元素和构造数二叉树的结点集合，每个结点由数据元素和构造数 据元素之间关系的指针组成。据元素之间关系的指针组成。 操作集合：操作集合： （1 1）创建）创

11、建MakeTree(TMakeTree(T) ) （2 2）撤消）撤消DestroyTree(TDestroyTree(T) ) （3 3）左插入结点）左插入结点InsertLeftNode(currInsertLeftNode(curr, x), x) （4 4）右插入结点）右插入结点InsertRightNode(currInsertRightNode(curr, x), x) （5 5）左删除子树）左删除子树DeleteLeftTree(currDeleteLeftTree(curr) ) （6 6）右删除子树）右删除子树DeleteRightTree(currDeleteRightTr

12、ee(curr) ) （7 7）遍历二叉树）遍历二叉树Traverse(T, Visit() 性质性质1 性质性质2 =-1，表示没有一个结点；，表示没有一个结点；=0，表示只有，表示只有 一个根结点。一个根结点。 性质性质3 3 对于一棵非空的二叉树，如果叶结点个数为对于一棵非空的二叉树，如果叶结点个数为n n0 0，度，度 为为2 2的结点数为的结点数为n n2 2，则有，则有 n n0 0= n= n2 2+1+1。 证明：设证明：设n n为二叉树的结点总数，为二叉树的结点总数，n n1 1为二叉树中度为为二叉树中度为1 1的结的结 点个数，则有：点个数，则有： n = nn = n0

13、0 + n + n1 1 + n + n2 2 另外，在二叉树中，除根结点外的所有结点都有一个另外，在二叉树中，除根结点外的所有结点都有一个 惟一的进入分支，设惟一的进入分支，设M M为二叉树中所有结点的进入分支数，为二叉树中所有结点的进入分支数， 则有：则有： M = n - 1M = n - 1 从二叉树的结构可知，二叉树的所有进入分支是由度为从二叉树的结构可知，二叉树的所有进入分支是由度为 1 1的结点和度为的结点和度为2 2的结点发出的，每个度为的结点发出的，每个度为1 1的结点发出一的结点发出一 个分支，每个度为个分支，每个度为2 2的结点发出两个分支，所以又有：的结点发出两个分支，

14、所以又有： M = nM = n1 1 + 2 + 2 n n2 2 因此有：因此有： n n - 1 = n - 1 = n1 1 + 2 + 2 n n2 2 再把再把 n=nn=n0 0+n+n1 1+n+n2 2 代入，则可以得到 代入，则可以得到 n n0 0 = n = n2 2 + 1 + 1。 性质性质4 具有具有n n个结点的完全二叉树的深度个结点的完全二叉树的深度k k为大于或等于为大于或等于 lb(n+1)-1lb(n+1)-1的最小整数。的最小整数。 证明：由性质证明：由性质2 2和完全二叉树的定义可知，对于有和完全二叉树的定义可知，对于有n n个结点的个结点的 深度为

15、深度为k k的完全二叉树有：的完全二叉树有：2 2k k-1 n 2-1 n 2k+1 k+1-1 -1 移项有：移项有：2 2k k n+1 2 n+1 2k+1 k+1 对不等式求对数，有：对不等式求对数，有：k lb(n+1) k+1k lb(n+1) k+1 因为因为lb(n+1)lb(n+1)介于介于k k和和k+1k+1之间且大于之间且大于k k，而二叉树的深度又，而二叉树的深度又 只能是整数，所以必有只能是整数，所以必有k k为大于或等于为大于或等于lb(n+1)-1lb(n+1)-1的最小整数。的最小整数。 可简写为可简写为k=k= lb(n+1)-1lb(n+1)-1 。例如

16、，。例如， 2.02.0 =2=2， 2.12.1 =3=3。 若结点个数若结点个数n=0n=0，则有深度，则有深度k=-1k=-1，满足，满足k=k= lb(0+1)-1lb(0+1)-1 =-1=-1； 若结点个数若结点个数n=1n=1，则有深度，则有深度k=0k=0，满足，满足k=k= lb(1+1)-1lb(1+1)-1 =0=0； 若结点个数若结点个数n=2n=2，则有深度，则有深度k=1k=1，满足，满足k=k= lb(2+1)-1lb(2+1)-1 = = 0.xx0.xx =1 =1； 若结点个数若结点个数n=3n=3，则有深度，则有深度k=1k=1，满足，满足k=k= lb(

17、3+1)-1lb(3+1)-1 =1=1。 对于一棵有对于一棵有n个结点的完全二叉树，按照从上至下和从个结点的完全二叉树，按照从上至下和从 左至右的顺序对所有结点从左至右的顺序对所有结点从0开始顺序编号开始顺序编号,则对于序号为则对于序号为i的的 结点结点(0i 0，则其双亲是结点，则其双亲是结点(i-1)/2(“/”表示整除）表示整除） ；如果；如果i=0， 则结点则结点i是根结点，无双亲。是根结点，无双亲。 (2)如果如果2i+1n ，其左孩子是结点，其左孩子是结点2i+1；如果；如果2i+1n，则结，则结 点点i无左孩子无左孩子。 (3)如果如果2i2n，其右孩子是结点，其右孩子是结点2

18、i2；如果；如果2i2n，则，则 结点结点i无右孩子无右孩子。 二叉树的存储结构主要有三种：顺序存储结构、链式存储二叉树的存储结构主要有三种：顺序存储结构、链式存储 结构和仿真指针存储结构。结构和仿真指针存储结构。 1.1. 二叉树的顺序存储结构二叉树的顺序存储结构 完全二叉树的结点可按从上至下和从左至右的次序存储完全二叉树的结点可按从上至下和从左至右的次序存储 在一维数组中，其结点之间的关系可由公式计算得到，这就在一维数组中，其结点之间的关系可由公式计算得到，这就 是二叉树的顺序存储结构。下面两棵树在数组中的存储结构是二叉树的顺序存储结构。下面两棵树在数组中的存储结构 分别为：分别为： B

19、A C EDFG HIJKLMNO A BCDONMLKJIHGFE 1204357611810912 13 14 对于一般的非完全二叉树对于一般的非完全二叉树显然不能直接使用二叉树的顺序存显然不能直接使用二叉树的顺序存 储结构。可以首先在非完全二叉树中增添一些并不存在的空结点储结构。可以首先在非完全二叉树中增添一些并不存在的空结点 使之变成完全二叉树的形态，然后再用顺序存储结构存储。使之变成完全二叉树的形态，然后再用顺序存储结构存储。 B A C EDFG HIJ A BCDJIHGFE 1204357689 B A C DE G F B A C DE GF (a)一般二叉树一般二叉树 (b

20、)完全二叉树形态完全二叉树形态 (c) 在数组中的存储形式在数组中的存储形式 A BC GFED 1204357611810912 数组数组 下标下标 2. 二叉树的链式存储结构二叉树的链式存储结构 二叉树的链式存储结构是用指针建立二叉树中结点之间的关系。二叉树的链式存储结构是用指针建立二叉树中结点之间的关系。 二叉树最常用的的链式存储结构是二叉链。二叉树最常用的的链式存储结构是二叉链。二叉链存储结构的每二叉链存储结构的每 个结点包含三个域，分别是数据域个结点包含三个域，分别是数据域data、左孩子指针域、左孩子指针域leftChild 和右孩子指针域和右孩子指针域rightChild。二叉链

21、存储结构中每个结点的图示。二叉链存储结构中每个结点的图示 结构为：结构为： rightChild dataleftChild 二叉链存储结构的二叉树也有不带头结点和带头结点两种。二叉链存储结构的二叉树也有不带头结点和带头结点两种。 带头结点的二叉链存储结构的二叉树见下图带头结点的二叉链存储结构的二叉树见下图(b)(b)，不带头结点的，不带头结点的 二叉链存储结构的二叉树如下图二叉链存储结构的二叉树如下图(a)(a)所示。所示。 图图8-10 8-10 二叉链存储结构的二叉树二叉链存储结构的二叉树 root A BC D EF G root A BC D EF G (a)(a)不带头结点的二叉树

22、不带头结点的二叉树 (b)(b)带头结点的二叉树带头结点的二叉树 3.3.二叉树的仿真指针二叉树的仿真指针 二叉树的仿真指针存储二叉树的仿真指针存储结构结构是用数组存储二叉树中的结点，是用数组存储二叉树中的结点， 数组中每个结点除数据元素域外，再增加仿真指针域用于仿数组中每个结点除数据元素域外，再增加仿真指针域用于仿 真常规指针建立二叉树中结点之间的关系。真常规指针建立二叉树中结点之间的关系。 二叉树的仿真二叉链存储结构二叉树的仿真二叉链存储结构 8.3.28.3.2二叉链结构的二叉树设计二叉链结构的二叉树设计 typedef struct Node DataType data; struct

23、 Node *leftChild; struct Node *rightChild; BiTreeNode; / /* *初始化初始化* */ / void Initiate(BiTreeNode *root) *root = (BiTreeNode *)malloc(sizeof(BiTreeNode); (*root)-leftChild = NULL; (*root)-rightChild = NULL; / /* *左子树插入结点左子树插入结点* */ / BiTreeNode *InsertLeftNode(BiTreeNode *curr, DataType x) BiTreeNo

24、de *s, *t; if(curr = NULL) return NULL; t = curr-leftChild; s = (BiTreeNode *)malloc(sizeof(BiTreeNode); s-data = x; s-leftChild = t; s-rightChild = NULL; curr-leftChild = s; return curr-leftChild; / /* *删除左子树删除左子树* */ / BiTreeNode *DeleteLeftTree(BiTreeNode *curr) if(curr = NULL | curr-leftChild =

25、NULL) return NULL; Destroy( curr-leftChild = NULL; return curr; 例例8-1 8-1 编写一个建立如图编写一个建立如图8-108-10（b b）所示的带头结点的二）所示的带头结点的二 叉链存储结构二叉树的程序。叉链存储结构二叉树的程序。 #include #include typedef char DataType; #include Bitree.h“ Void main(void) BiTreeNode *root, *p, *pp; Initiate( p = InsertLeftNode(root, A); p = Inse

26、rtLeftNode(p, B); p = InsertLeftNode(p, D); p = InsertRightNode(p, G); p = InsertRightNode(root-leftChild, C); InsertLeftNode(p, E); InsertRightNode(pp, F); 8.4 8.4 二叉树遍历二叉树遍历 1.1.二叉树遍历的基本方法二叉树遍历的基本方法 从二叉树的定义知，一棵二叉树由三部分组成：根结点、从二叉树的定义知，一棵二叉树由三部分组成：根结点、 左子树和右子树。若规定左子树和右子树。若规定D,L,RD,L,R分别代表分别代表“访问根结点访问

27、根结点”、 “遍历根结点的左子树遍历根结点的左子树”和和“遍历根结点的右子树遍历根结点的右子树”，根据，根据 遍历算法对访问根结点处理的位置，称下面三种遍历算法分遍历算法对访问根结点处理的位置，称下面三种遍历算法分 别为别为前序遍历（前序遍历（DLRDLR）、中序遍历（）、中序遍历（LDRLDR）和后序遍历）和后序遍历 （LRDLRD）。 8.4.1 8.4.1 二叉树遍历二叉树遍历 前序遍历（前序遍历（DLRDLR）递归算法为：）递归算法为： 若二叉树为空则算法结束；否则：若二叉树为空则算法结束；否则： （1 1）访问根结点；）访问根结点； （2 2）前序遍历根结点的左子树；）前序遍历根结点

28、的左子树； （3 3）前序遍历根结点的右子树。）前序遍历根结点的右子树。 对于图对于图8-78-7（b b）所示的二叉树，前序遍历访问结点的次序为：）所示的二叉树，前序遍历访问结点的次序为： A B D G C E FA B D G C E F 中序遍历（中序遍历（LDRLDR）递归算法为：）递归算法为： 若二叉树为空则算法结束；否则：若二叉树为空则算法结束；否则： （1 1）中序遍历根结点的左子树；）中序遍历根结点的左子树； （2 2）访问根结点；）访问根结点； （3 3）中序遍历根结点的右子树。）中序遍历根结点的右子树。 对于图对于图8-78-7（b b）所示的二叉树，中序遍历访问结点）所

29、示的二叉树，中序遍历访问结点的次序的次序为：为： D G B A E C FD G B A E C F 后序遍历（后序遍历（LRDLRD）递归算法为：）递归算法为： 若二叉树为空则算法结束；否则：若二叉树为空则算法结束；否则： （1 1）后序遍历根结点的左子树；）后序遍历根结点的左子树； （2 2）后序遍历根结点的右子树；）后序遍历根结点的右子树； （3 3）访问根结点。）访问根结点。 对于图对于图8-78-7（b b）所示的二叉树，后序遍历访问结点的）所示的二叉树，后序遍历访问结点的 次序为：次序为： G D B E F C AG D B E F C A 此外，二叉树还有此外，二叉树还有层序

30、遍历层序遍历。层序遍历的要求是：按。层序遍历的要求是：按 二叉树的层序次序（即二叉树的层序次序（即从根结点层至叶结点层从根结点层至叶结点层），同一层），同一层 中按中按先左子树再右子树先左子树再右子树的次序遍历二叉树。的次序遍历二叉树。 它的特点是，在所有未被访问结点的集合中，排列在它的特点是，在所有未被访问结点的集合中，排列在 已访问结点集合中最前面结点的左子树的根结点将最先被已访问结点集合中最前面结点的左子树的根结点将最先被 访问，然后是该结点的右子树的根结点。这样，如果把已访问，然后是该结点的右子树的根结点。这样，如果把已 访问的结点放在一个队列中，那么，所有未被访问结点的访问的结点放在

31、一个队列中，那么，所有未被访问结点的 访问次序就可以由存放在队列中的已访问结点的出队列次访问次序就可以由存放在队列中的已访问结点的出队列次 序决定。因此序决定。因此可以借助队列实现二叉树的层序遍历可以借助队列实现二叉树的层序遍历。 二叉树的层序遍历算法如下：二叉树的层序遍历算法如下： （1 1）初始化设置一个队列；）初始化设置一个队列； （2 2）把根结点指针入队列；）把根结点指针入队列； （3 3）当队列非空时，循环执行步骤（）当队列非空时，循环执行步骤（3.a3.a）到步骤（）到步骤（3.c3.c）；）； （3.a3.a）出队列取得一个结点指针，访问该结点；）出队列取得一个结点指针，访问该

32、结点； （3.b3.b）若该结点的左子树非空，则将该结点的左子树指）若该结点的左子树非空，则将该结点的左子树指 针入队列；针入队列； （3.c3.c）若该结点的右子树非空，则将该结点的右子树指）若该结点的右子树非空，则将该结点的右子树指 针入队列；针入队列； （4 4）结束。）结束。 2.2.二叉树的遍历方法和二叉树的结构二叉树的遍历方法和二叉树的结构 二叉树是非线性结构，每个结点会有零个、一个或两个二叉树是非线性结构，每个结点会有零个、一个或两个 孩子结点，一个二叉树的遍历序列不能决定一棵二叉树，但孩子结点，一个二叉树的遍历序列不能决定一棵二叉树，但 某些不同的遍历序列组合可以惟一确定一棵二

33、叉树。可以证某些不同的遍历序列组合可以惟一确定一棵二叉树。可以证 明，明，给定一棵二叉树的前序遍历序列和中序遍历序列可以惟给定一棵二叉树的前序遍历序列和中序遍历序列可以惟 一确定一棵二叉树的结构一确定一棵二叉树的结构。 当对一个二叉树用一种特定的遍历方法来遍历时，当对一个二叉树用一种特定的遍历方法来遍历时， 其遍历序列一定是线性的，且是惟一的。其遍历序列一定是线性的，且是惟一的。 8.4.2 8.4.2 二叉链存储结构下二叉树遍历的实现二叉链存储结构下二叉树遍历的实现 void PreOrder(BiTreeNode *t, void Visit(DataType item) /*前序遍历二叉

34、树前序遍历二叉树t，访问操作为，访问操作为Visit()函数函数*/ if(t != NULL) Visit(t-data); PreOrder(t-leftChild, Visit); PreOrder(t-rightChild, Visit); 为了通用性，把访问操作设计成前序遍历二叉树函数的为了通用性，把访问操作设计成前序遍历二叉树函数的 一个函数虚参一个函数虚参 Visit()。 void InOrder(BiTreeNode *t, void Visit(DataType item) /*中序中序t */ if(t != NULL) InOrder(t-leftChild, Visi

35、t); Visit(t-data); InOrder(t-rightChild, Visit); void PostOrder(BiTreeNode *t, void Visit(DataType item) /*后序后序 */ if(t != NULL) PostOrder(t-leftChild, Visit); PostOrder(t-rightChild, Visit); Visit(t-data); 二叉树撤消操作函数二叉树撤消操作函数 二叉树的撤消操作实际上是二叉树遍历操作的一个具二叉树的撤消操作实际上是二叉树遍历操作的一个具 体应用。由于二叉树中每个结点允许有左孩子结点和右孩体应

36、用。由于二叉树中每个结点允许有左孩子结点和右孩 子结点，所以在释放某个结点的存储空间前必须先释放该子结点，所以在释放某个结点的存储空间前必须先释放该 结点左孩子结点的存储空间和右孩子结点的存储空间，因结点左孩子结点的存储空间和右孩子结点的存储空间，因 此，二叉树撤消操作必须是此，二叉树撤消操作必须是后序遍历后序遍历的具体应用。撤消操的具体应用。撤消操 作算法实现如下：作算法实现如下： void Destroy(BiTreeNode *root) if(*root) != NULL if(*root) != NULL free(*root); 8.4.3 8.4.3 二叉树遍历的应用二叉树遍历的

37、应用 1 1 打印二叉树打印二叉树 把二叉树逆时针旋转把二叉树逆时针旋转90900 0C C，按照二叉树的凹入表，按照二叉树的凹入表 示法打印二叉树。可把此函数设计成递归函数。由于示法打印二叉树。可把此函数设计成递归函数。由于 把二叉树逆时针旋转把二叉树逆时针旋转90900 0C C后，在屏幕上方的首先是右后，在屏幕上方的首先是右 子树，然后是根结点，最后是左子树，所以子树，然后是根结点，最后是左子树，所以打印二叉打印二叉 树算法是一种特殊的中序遍历算法。树算法是一种特殊的中序遍历算法。 void PrintBiTree(BiTreeNode *bt, int n) int i; if(bt

38、= NULL) return; PrintBiTree(bt-rightChild, n+1); for(i = 0; i 0) printf(-); printf(%cn, bt-data); PrintBiTree(bt-leftChild, n+1); 在二叉树中查找数据元素操作的要求是：在在二叉树中查找数据元素操作的要求是：在btbt为根结点为根结点 指针的二叉树中查找数据元素指针的二叉树中查找数据元素x x，若查找到数据元素，若查找到数据元素x x时返回时返回 该结点的指针；若查找不到数据元素该结点的指针；若查找不到数据元素x x时返回空指针。时返回空指针。 在二叉树在二叉树btbt

39、中查找数据元素中查找数据元素x x算法可设计成先序遍历算法算法可设计成先序遍历算法 ，此时查找结点的次序是：首先在根结点查找，然后在左子，此时查找结点的次序是：首先在根结点查找，然后在左子 树查找，最后在右子树查找。但是，和常规递归算法不同的树查找，最后在右子树查找。但是，和常规递归算法不同的 是，此算法当一个分支上的结点比较完仍未查找到数据元素是，此算法当一个分支上的结点比较完仍未查找到数据元素x x 时，要返回到该结点的双亲结点处继续查找。因此，此算法时，要返回到该结点的双亲结点处继续查找。因此，此算法 是一个回溯算法是一个回溯算法 。 2 2 查找数据元素查找数据元素 BiTreeNod

40、e *Search(BiTreeNode *bt, DataType x) BiTreeNode *p; if(bt = NULL) return NULL; if(bt-data = x) return bt; if(bt-leftChild != NULL) p = Search(bt-leftChild, x); if(p != NULL) return p; if(bt-rightChild != NULL) p = Search(bt-rightChild, x); if(p != NULL) return p; return NULL; 例例8-2 8-2 编写一个程序，首先建立如

41、图编写一个程序，首先建立如图8-108-10（b b）所示的带头）所示的带头 结点的二叉链存储结构二叉树，然后打印该二叉树，最后结点的二叉链存储结构二叉树，然后打印该二叉树，最后 输出分别按照前序遍历二叉树次序、中序遍历二叉树次序输出分别按照前序遍历二叉树次序、中序遍历二叉树次序 和后序遍历二叉树次序访问各结点的序列信息。和后序遍历二叉树次序访问各结点的序列信息。 设计：设计： 输出显示函数设计：按照某种遍历方法输出显示二叉树各输出显示函数设计：按照某种遍历方法输出显示二叉树各 结点的信息，其实就是把上述各遍历二叉树函数中的结点的信息，其实就是把上述各遍历二叉树函数中的 Visit()Visi

42、t()函数设计成输出显示结点信息的函数。函数设计成输出显示结点信息的函数。Visit()Visit()函函 数设计如下：数设计如下： void Visit(DataType item) printf(%c , item); 3.3.应用举例应用举例 8.4.4.8.4.4.非递归的二叉树遍历算法非递归的二叉树遍历算法 所有递归算法都可以借助堆栈转换成循环结构的非递归算所有递归算法都可以借助堆栈转换成循环结构的非递归算 法，通常有两种方法：一种方法是法，通常有两种方法：一种方法是形式化模拟转换形式化模拟转换，另一种方，另一种方 法是法是根据要求解问题的特点设计借助堆栈的循环结构算法根据要求解问题

43、的特点设计借助堆栈的循环结构算法。 非递归的二叉树前序遍历算法如下非递归的二叉树前序遍历算法如下： （1 1）初始化设置一个堆栈；）初始化设置一个堆栈； （2 2）把根结点指针入栈；）把根结点指针入栈； （3 3）当堆栈非空时，循环执行步骤（）当堆栈非空时，循环执行步骤（3.a3.a）到步骤（）到步骤（3.c3.c）；）； （3.a3.a）出栈取得一个结点指针，访问该结点；）出栈取得一个结点指针，访问该结点； （3.b3.b）若该结点的右子树非空，则将该结点的右子树指）若该结点的右子树非空，则将该结点的右子树指 针入栈；针入栈； （3.c3.c）若该结点的左子树非空，则将该结点的左子树指）若该

44、结点的左子树非空，则将该结点的左子树指 针入栈；针入栈； （4 4）结束。）结束。 问题问题： （1 1）这个算法和哪个算法相似？这个算法和哪个算法相似？ （2 2）为什么相似？）为什么相似？ （3 3）非递归的二叉树前序遍历算法有什么用途？）非递归的二叉树前序遍历算法有什么用途？ 8.5 8.5 线索二叉树线索二叉树 线索二叉树是另一种线索二叉树是另一种分步遍历分步遍历二叉树的方法。它二叉树的方法。它既可以既可以 从前向后从前向后分步遍历二叉树，分步遍历二叉树，又可以从后向前又可以从后向前分步遍历二叉树。分步遍历二叉树。 当按某种规则遍历二叉树时，保存遍历时得到的结点的当按某种规则遍历二叉树

45、时，保存遍历时得到的结点的 后继结点信息和前驱结点信息的最常用的方法是建立线索二后继结点信息和前驱结点信息的最常用的方法是建立线索二 叉树。叉树。 对二叉链存储结构的二叉树分析可知，在有对二叉链存储结构的二叉树分析可知，在有n n个结点的个结点的 二叉树中必定存在二叉树中必定存在n+1n+1个空链域。个空链域。 规定规定：当某结点的左指针为空时，令该指针指向按某：当某结点的左指针为空时，令该指针指向按某 种方法遍历二叉树时得到的该结点的前驱结点；当某结点种方法遍历二叉树时得到的该结点的前驱结点；当某结点 的右指针为空时，令该指针指向按某种方法遍历二叉树时的右指针为空时，令该指针指向按某种方法遍

46、历二叉树时 得到的该结点的后继结点。仅仅这样做会使我们不能区分得到的该结点的后继结点。仅仅这样做会使我们不能区分 左指针指向的结点到底是左孩子结点还是前驱结点，右指左指针指向的结点到底是左孩子结点还是前驱结点，右指 针指向的结点到底是右孩子结点还是后继结点。因此我们针指向的结点到底是右孩子结点还是后继结点。因此我们 再在结点中增加两个线索标志位来区分这两种情况。再在结点中增加两个线索标志位来区分这两种情况。 指向结点的前驱结点 指向结点的左孩子结点 leftChild leftChild leftThread 1 0 指向结点的后继结点 指向结点的右孩子结点 rightChild rightC

47、hild drightThrea 1 0 每个结点的结构就如下所示：每个结点的结构就如下所示： leftThreadleftChilddatarightChildrightThread 结点中指向前驱结点和后继结点的指针称为结点中指向前驱结点和后继结点的指针称为线索。线索。在二叉在二叉 树的结点上加上线索的二叉树称作树的结点上加上线索的二叉树称作线索二叉树。线索二叉树。对二叉树以某对二叉树以某 种方法（如前序、中序或后序方法）遍历使其变为线索二叉树种方法（如前序、中序或后序方法）遍历使其变为线索二叉树 的过程称作按该方法的过程称作按该方法对二叉树进行的线索化。对二叉树进行的线索化。 线索标志位

48、定义如下：线索标志位定义如下： A D G E C F (a) B 01 0A0 0B10C0 1D01E11F1 1G1 (b) 01 0A0 0B10C0 1D01E11F1 1G 1 (d) 01 0A0 0B10C0 1D01E11F1 1G1 (c) root root root 线索二叉树线索二叉树 b b中序中序 c c前序前序 d d后序后序 一旦建立了某种方式的线索二叉树后，用户程序就可以一旦建立了某种方式的线索二叉树后，用户程序就可以 像操作双向链表一样操作该线索二叉树。像操作双向链表一样操作该线索二叉树。 例如，一旦建立了中序线索二叉树后，用户程序就可以例如，一旦建立了中

49、序线索二叉树后，用户程序就可以 设计一个正向循环结构遍历该二叉树的所有结点，循环初始设计一个正向循环结构遍历该二叉树的所有结点，循环初始 定位在中序线索二叉树的第一个结点位置，每次循环使指针定位在中序线索二叉树的第一个结点位置，每次循环使指针 指向当前结点的中序遍历的后继结点位置，当指针指向中序指向当前结点的中序遍历的后继结点位置，当指针指向中序 线索二叉树的最后一个结点位置后循环过程结束；或者用户线索二叉树的最后一个结点位置后循环过程结束；或者用户 程序可以设计一个反向循环结构遍历该二叉树的所有结点，程序可以设计一个反向循环结构遍历该二叉树的所有结点， 循环初始定位在中序线索二叉树的最后一个

50、结点位置，每次循环初始定位在中序线索二叉树的最后一个结点位置，每次 循环使指针指向当前结点的中序遍历的前驱结点位置，当指循环使指针指向当前结点的中序遍历的前驱结点位置，当指 针指向中序线索二叉树的第一个结点位置前循环过程结束。针指向中序线索二叉树的第一个结点位置前循环过程结束。 这种算法设计要求分别设计三个函数：这种算法设计要求分别设计三个函数： First()：定位在第一个结点位置定位在第一个结点位置； Next()：移动到下一个结点位置；移动到下一个结点位置； End()：是否已经到最后下一个结点位置；是否已经到最后下一个结点位置； 当然，还需要一个根据二叉树构造线索二叉树的函数当然，还需

51、要一个根据二叉树构造线索二叉树的函数。 typedef struct ThreadBiNode *root; ThreadBiNode *current; int nextComplete; ThreadBiTree; void ThreadInitiate(ThreadBiTree *tree, ThreadBiNode *root) tree-root = root; tree-current = root; if(root = NULL) tree-nextComplete = 1; else tree-nextComplete = 0; void First(ThreadBiTree

52、*tree) /定位在定位在中序线索二叉树的第一个结点中序线索二叉树的第一个结点 tree-current = tree-root; /定位根结点定位根结点 while(tree-current-leftThread = 0/找到最左子树结找到最左子树结 点点 tree-current = tree-current-leftChild; if(tree-current = tree-root) tree-nextComplete = 1; else tree-nextComplete = 0; void Next(ThreadBiTree *tree) /定位在中序线索二叉树当前结点的下一个结

53、点定位在中序线索二叉树当前结点的下一个结点 ThreadBiNode *p = tree-current-rightChild; if(tree-nextComplete = 1)return; if(tree-current-rightThread = 0)/若有右孩子结点若有右孩子结点 while(p-leftThread = 0) p = p-leftChild; /找到最左子树结点找到最左子树结点 tree-current = p; if(tree-current = tree-root) tree-nextComplete = 1; int EndOfNext(ThreadBiTre

54、e *tree) /判断是否已到中序线索二叉树的最后一个结点判断是否已到中序线索二叉树的最后一个结点 return tree-nextComplete; 例例8-3 8-3 编写一个程序，首先建立如图编写一个程序，首先建立如图8-108-10（a a）所示的不）所示的不 带头结点的二叉树，然后中序线索化该二叉树，最后用带头结点的二叉树，然后中序线索化该二叉树，最后用 循环结构输出该中序线索化二叉树各结点的序列信息。循环结构输出该中序线索化二叉树各结点的序列信息。 void main(void) ThreadBiNode *root; ThreadBiTree tree; MakeCharTre

55、e( CreatInThread( printf(二叉树中序正向遍历序列为：二叉树中序正向遍历序列为：); ThreadInitiate( /*循环初始化循环初始化*/ for(First( !EndOfNext( Next( 8.6 8.6 哈夫曼树哈夫曼树 1.1.哈夫曼树的基本概念哈夫曼树的基本概念 从从A A结点到结点到B B结点所经过的分支序列叫做从结点所经过的分支序列叫做从A A结点到结点到B B结点的结点的 路径；路径；从从A A结点到结点到B B结点所经过的分支个数叫做从结点所经过的分支个数叫做从A A结点到结点到B B结点结点 的的路径长度；路径长度；从二叉树的根结点到二叉树

56、中所有叶结点的路径从二叉树的根结点到二叉树中所有叶结点的路径 长度之和称作长度之和称作该二叉树的路径长度。该二叉树的路径长度。设二叉树有设二叉树有n n个带权值的个带权值的 叶结点，定义从二叉树的根结点到二叉树中所有叶结点的路径叶结点，定义从二叉树的根结点到二叉树中所有叶结点的路径 长度与相应叶结点权值的乘积之和称作该长度与相应叶结点权值的乘积之和称作该二叉树的带权路径长二叉树的带权路径长 度（度（WPLWPL），），即：即： WPL= n i ii lw 1 其中，其中，wi为第为第i i个叶结点的权值，个叶结点的权值，li为从根结点到第为从根结点到第i个个 叶结点的路径长度。叶结点的路径长

57、度。 1 13 3 5 57 7 7 7 1 1 3 35 5 7 7 1 1 3 3 5 5 5 5 ( (a a) )( (b b) )( (c c) ) ( (d d) ) 7 7 1 13 3 下图所示二叉树带权路径长度分别为下图所示二叉树带权路径长度分别为: （a a）WPL = 1WPL = 12+32+32+52+52+72+72 = 322 = 32 （b b）WPL = 1WPL = 12+32+33+53+53+73+71 = 331 = 33 （c c）WPL = 7WPL = 73+53+53+33+32+12+11 = 431 = 43 （d d）WPL = 1WPL

58、 = 13+33+33+53+52+72+71 = 291 = 29 具有最小带权路径长度的二叉树称作具有最小带权路径长度的二叉树称作哈夫曼（哈夫曼（HuffmanHuffman）树）树 （或称最优二叉树）。（或称最优二叉树）。图（图（d d）的二叉树是一棵哈夫曼树。）的二叉树是一棵哈夫曼树。 定义：由给定的定义：由给定的n n个叶结点权值可以构造很多棵形态不同个叶结点权值可以构造很多棵形态不同 的二叉树，的二叉树，WPLWPL值最小的二叉树称为值最小的二叉树称为哈夫曼树哈夫曼树。 要使一棵二叉树的带权路径长度要使一棵二叉树的带权路径长度WPLWPL值最小，必须使权值值最小，必须使权值 越大的

59、叶结点越靠近根结点。越大的叶结点越靠近根结点。哈夫曼树构造算法为：哈夫曼树构造算法为： （1 1）由给定的）由给定的n n个权值个权值ww1 1,w,w2 2, ,w,wn n 构造构造n n棵只有根结点的棵只有根结点的 二叉树，从而得到一个二叉树森林二叉树，从而得到一个二叉树森林F=TF=T1 1,T,T2 2, ,T,Tn n 。 （2 2）在二叉树森林）在二叉树森林F F中选取根结点的权值最小和次小的两棵中选取根结点的权值最小和次小的两棵 二叉树作为新的二叉树的左右子树构造新的二叉树，新的二二叉树作为新的二叉树的左右子树构造新的二叉树，新的二 叉树的根结点权值为左右子树根结点权值之和。叉

60、树的根结点权值为左右子树根结点权值之和。 （3 3）在二叉树森林）在二叉树森林F F中删除作为新二叉树左右子树的两棵二中删除作为新二叉树左右子树的两棵二 叉树，将新二叉树加入到二叉树森林叉树，将新二叉树加入到二叉树森林F F中。中。 （4 4）重复步骤（）重复步骤（2 2）和（）和（3 3），当二叉树森林），当二叉树森林F F中只剩下一棵中只剩下一棵 二叉树时，这棵二叉树就是所构造的哈夫曼树。二叉树时，这棵二叉树就是所构造的哈夫曼树。 2.2.哈夫曼编码问题哈夫曼编码问题 将传送的文字转换为二进制字符将传送的文字转换为二进制字符0 0和和1 1组成的二进制串的过组成的二进制串的过 程为程为编码