第六章 树和二叉树

1、6.1 树的类型定义树的类型定义6.2 二叉树的类型二叉树的类型定义定义6.3 二叉树的存储结构二叉树的存储结构6.4 二叉树的遍历二叉树的遍历6.5 线索二叉树线索二叉树6.6 树和森林的表示方法树和森林的表示方法6.7 哈夫曼树与哈夫曼编码哈夫曼树与哈夫曼编码第六章第六章 树和二叉树树和二叉树6.1 树的类型定义树的类型定义 A C G T2D H I T3J M B E L KT1 F例子：学校的行政关系、书的层次结构、人类的家族血缘关系等。例子：学校的行政关系、书的层次结构、人类的家族血缘关系等。结点间有明显的层次结构关系结点间有明显的层次结构关系数据对象数据对象 D： D是具有相同特

2、性的数据元素的集合。是具有相同特性的数据元素的集合。 数据关系数据关系 R：若若D为空集，则称为为空集，则称为空树空树 。否则否则: (1) 在在D中中存在唯一存在唯一的称为的称为根根的数据元素的数据元素root； (2) 当当n1时，其余结点可分为时，其余结点可分为m (m0)个互不相个互不相交的有限集交的有限集T1, 2, , Tm，其中每一棵子集本身又是一棵，其中每一棵子集本身又是一棵符合本定义的树，称为根符合本定义的树，称为根root的的子树子树。树的逻辑表示方法树的逻辑表示方法 A C G J B E D F I H M K L 树形表示法树形表示法 H L D K I M C G

3、J E B F 文氏图表示法文氏图表示法 A 括号表示法括号表示法 A(B(E,F),C(G(J),D(H,I(K,L,M) 树根T1T2T3（广义表表示法）（广义表表示法）主要分为三大类：主要分为三大类： 第一类第一类, ,寻找满足某种特定关系的结点寻找满足某种特定关系的结点, ,如寻如寻找当前结点的双亲结点等；找当前结点的双亲结点等； 第二类第二类, ,插入或删除某个结点插入或删除某个结点, ,如在树的当前如在树的当前结点上插入一个新结点或删除当前结点的第结点上插入一个新结点或删除当前结点的第i i个个孩子结点等；孩子结点等； 第三类第三类, ,遍历树中每个结点遍历树中每个结点。树的基本操

4、作：树的基本操作：树的遍历可有三条搜索路径树的遍历可有三条搜索路径:按层次遍历按层次遍历:先根先根(次序次序)遍历遍历:后根后根(次序次序)遍历遍历: 若树不空，则先访问根结点，然后若树不空，则先访问根结点，然后依次先根遍历各棵子树。依次先根遍历各棵子树。 若树不空，则先依次后根遍历各棵若树不空，则先依次后根遍历各棵子树，然后访问根结点。子树，然后访问根结点。 若树不空，则自上而下自左至右若树不空，则自上而下自左至右访问树中每个结点。访问树中每个结点。 A B C DE F G H I J K 先根遍历时顶点先根遍历时顶点的访问次序：的访问次序：A B E F C D G H I J K 后根

5、遍历时顶点后根遍历时顶点的访问次序：的访问次序：E F B C I J K H G D A 层次遍历时顶点层次遍历时顶点的访问次序：的访问次序：A B C D E F G H I J K() 有确定的根；() 树根和子树根之间为有向关系。有向树：有向树：有序树：有序树：子树之间存在确定的次序关系。无序树：无序树：子树之间不存在确定的次序关系。对比对比树型结构树型结构和和线性结构线性结构的结构特点的结构特点线性结构线性结构树型结构树型结构第一个数据元素第一个数据元素 ( (无前驱无前驱) ) 根结点根结点 ( (无前驱无前驱) )最后一个数据元素最后一个数据元素 (无后继无后继)多个叶子结点多个

6、叶子结点 ( (无后继无后继) )其它数据元素其它数据元素( (一个前驱、一个前驱、 一个后继一个后继) )其它数据元素其它数据元素( (一个前驱、一个前驱、 多个后继多个后继) )基基 本本 术术 语语结点结点: :结点的度结点的度: :树的度树的度: :叶子结点叶子结点: :分支结点分支结点: :数据元素+ +若干指向子树的分支分支的个数树中所有结点的度的最大值度为零的结点度大于零的结点DHIJM(从根到结点的)路径路径：孩子孩子结点、双亲双亲结点兄弟兄弟结点、堂兄弟祖先祖先结点、子孙子孙结点结点的层次结点的层次: :树的深度：树的深度： 由从根根到该结点所经分支和结点构成ABCDEFGH

7、IJMKL假设根结点的层次为1，第l 层的结点的子树根结点的层次为l+1树中叶子结点所在的最大层次任何一棵非空树是一个二元组 Tree = （root，F）其中：root 被称为根结点 F 被称为子树森林森林：森林：是m（m0）棵互不相交的树的集合ArootBCDEFGHIJMKLF6.2 二叉树的类型定义二叉树的类型定义 二叉树或为空树空树，或是由一个根结根结点点加上两棵两棵分别称为左子树左子树和右子树的、互不交的互不交的二叉树二叉树组成。ABCDEFGHK根结点左子树右子树二叉树的五种基本形态：二叉树的五种基本形态：N空树空树只含根结点只含根结点NNNLRR右子树为空树右子树为空树L左子树

8、为空树左子树为空树左右子左右子树均不树均不为空树为空树二叉树二叉树的重要特性的重要特性 性质性质 1 ：在二叉树的第 i 层上至多有2i-1 个结点。 (i1)用归纳法证明用归纳法证明： 归纳基归纳基： 归纳假设：归纳假设： 归纳证明：归纳证明：i = 1 层时，只有一个根结点：层时，只有一个根结点： 2i-1 = 20 = 1；假设对所有的假设对所有的 j，1 j i，命题成立；命题成立；二叉树上每个结点至多有两棵子树，二叉树上每个结点至多有两棵子树，则第则第 i 层的结点数层的结点数 = 2i-2 2 = 2i-1 。423167891011121314155第三层上第三层上(i=3)(i

9、=3)，有，有2 23-13-1=4=4个节点。个节点。第四层上第四层上(i=4)(i=4)，有，有2 24-14-1=8=8个节点。个节点。 性质性质 2 ： 深度为 k 的二叉树上至多含 2k-1 个结点（k1）。证明：证明： 基于上一条性质，深度为基于上一条性质，深度为 k 的二叉树上的结点数至多为的二叉树上的结点数至多为 20+21+ +2k-1 = 2k-1 。423167891011121314155此树的深度此树的深度k =4=4，共有，共有2 24 4-1=15-1=15个节点。个节点。 性质性质 3 ： 对任何一棵二叉树，若它含有对任何一棵二叉树，若它含有n0 个叶子结点、个

10、叶子结点、n2 个度为个度为 2 的结点，则必存在关系式：的结点，则必存在关系式：n0 = n2+1。证明：证明：设设 二叉树上结点总数 n = n0 + n1 + n2又又 二叉树上分支总数 b = n1+2n2 而 b = n-1 = n0 + n1 + n2 - 1由此，由此， n0 = n2 + 1 。423167891011121314155n n0 0=8=8n n2 2=7=7两类两类特殊特殊的二叉树：的二叉树：满二叉树满二叉树：指的是深度为k且含有2k-1个结点的二叉树。完全二叉树完全二叉树：树中所含的 n 个结点和满二叉树中编号为编号为 1 至至 n 的结点的结点一一对应。1

11、23456789 10 11 12 13 14 15abcdefghij特点：每一层上都含有最大结点数。特点：每一层上都含有最大结点数。 性质性质 4 ： 具有 n 个结点的完全二叉树的深度为 log2n +1 。证明：证明：设设完全二叉树的深度为 k 则根据第二条性质得 2k-1 n 2k 即 k-1 log2 n n，则该结点无左孩子，则该结点无左孩子， 否则，编号为否则，编号为 2i 的结点为其的结点为其左孩子左孩子结点；结点；(3) 若若 2i+1n，则该结点无右孩子结点，则该结点无右孩子结点， 否则，编号为否则，编号为2i+1 的结点为其的结点为其右孩子右孩子结点结点。4231678

12、910 11125 完全二叉树完全二叉树6.3 二叉树的存储结构二叉树的存储结构二、二叉树的链式二、二叉树的链式 存储表示存储表示一、一、 二叉树的顺序二叉树的顺序 存储表示存储表示#define MAX_TREE_SIZE 100 / 二叉树的最大结点数typedef TElemType SqBiTreeMAX_TREE_SIZE; / 0号单元存储根结点SqBiTree bt;一、一、 二叉树的顺序存储表示二叉树的顺序存储表示用一组连续的存储单元存放二叉树用一组连续的存储单元存放二叉树的数据元素。结点在数组中的相对的数据元素。结点在数组中的相对位置蕴含着结点之间的关系。位置蕴含着结点之间的

13、关系。二叉树二叉树顺序顺序存储结构存储结构 bt16若父结点在数组中若父结点在数组中i下标处，其左孩子在下标处，其左孩子在2*i处，右孩子在处，右孩子在2*i+1处处。11 A B c F E D 1 2 4 8 910 5 6 3 7121314152h-1= 24-1 = 15用一组连续的存储单元存放二叉树的数据用一组连续的存储单元存放二叉树的数据元素。结点在数组中的相对位置蕴含着结元素。结点在数组中的相对位置蕴含着结点之间的关系。点之间的关系。0000FE000DC0BA15141312111098765432100一般二叉树必须按完全二叉树的形式存储，将造成存储的浪费。一般二叉树必须按

14、完全二叉树的形式存储，将造成存储的浪费。typedef TElemType SqBiTreeMAX_TREE_SIZE+1; / 0号单元未用SqBiTree bt例如例如:ABCDEF A B D C E F 0 1 2 3 4 5 6 7 8 9 10 11 12 131401326typedef TElemType SqBiTreeMAX_TREE_SIZE; / 0号单元存储根结点二、二叉树的链式存储表示二、二叉树的链式存储表示1. 1. 二叉链表二叉链表2三叉链表三叉链表3 3双亲链表双亲链表4线索链表线索链表ADEBCF rootlchild data rchild结点结构结点结构

15、:1. 1. 二叉链表二叉链表typedef struct node / 结点结构结点结构 TElemType data;/数据元素数据元素 struct node *lchild, *rchild; / 左右孩子指针左右孩子指针 BTNode;ADEBCF root 2三叉链表三叉链表parent lchild data rchild结点结构结点结构:typedef struct TriTNode / 结点结构结点结构 TElemType data; struct TriTNode *lchild, *rchild; / 左右孩子指针左右孩子指针 struct TriTNode *paren

16、t; /双亲指针双亲指针 TriTNode, *TriTree;0123456B2C0A -1D2E3F4 data parent结点结构结点结构:3 3双亲链表双亲链表LRTagLRRRL typedef struct BPTNode / 结点结构结点结构 TElemType data; int *parent; / 指向双亲的指针 char LRTag; / 左、右孩子标志域 BPTNode typedef struct BPTree / 树结构树结构 BPTNode nodesMAX_TREE_SIZE; int num_node; / 结点数目结点数目 int root; / 根结点的

17、位置根结点的位置 BPTree6.4二叉树的遍历二叉树的遍历一、问题的提出一、问题的提出二、先左后右的遍历算法二、先左后右的遍历算法三、算法的递归描述三、算法的递归描述四、中序遍历算法的非递归描述四、中序遍历算法的非递归描述五五、遍历算法的应用举例遍历算法的应用举例遍历：遍历：按某条搜索路线按某条搜索路线寻访寻访树中树中每个结点每个结点且且只被访问一次只被访问一次。一、问题的提出一、问题的提出“访问访问”的含义可以很广，如：输出结点的信息等。查找某个结点，或对二叉树中全部结点进行某种处理，就需要遍历。查找某个结点，或对二叉树中全部结点进行某种处理，就需要遍历。 “遍历遍历”是任何类型均有的操作

18、，对线性结构而言，只有一条搜索路径(因为每个结点均只有一个后继)，故不需要另加讨论。而二叉树是非线性结构，每个结点有两个后继每个结点有两个后继，则存在如何遍历存在如何遍历即按什么样的搜索路径搜索路径遍历的问题。对对“二叉树二叉树”而言，可以有三条搜索路径而言，可以有三条搜索路径 1先上后下先上后下的按层次遍历； 2先左先左（子树）后右后右（子树）的遍历； 3先右先右（子树）后左后左（子树）的遍历。二、先左后右的遍历算法二、先左后右的遍历算法按按先左后右先左后右的原则，一般使用的原则，一般使用三种遍历：三种遍历：先根遍历先根遍历(D L R):(D L R): 访问根结点，按先序访问根结点，按先

19、序遍历左子树，按先序遍历右子树。遍历左子树，按先序遍历右子树。中根遍历中根遍历(L D R):(L D R): 按中序遍历左子树，访按中序遍历左子树，访问根结点，按中序遍历右子树。问根结点，按中序遍历右子树。后根遍历后根遍历(L R D):(L R D): 按后序遍历左子树，按按后序遍历左子树，按后序遍历右子树，访问根结点。后序遍历右子树，访问根结点。 二叉树为空时，执行空二叉树为空时，执行空操作，即空二叉树已遍历完。操作，即空二叉树已遍历完。遍历算法例：遍历算法例：先序遍历：先序遍历：D L R中序遍历：中序遍历：L D R后序遍历：后序遍历：L R DADBCT1T2T3D L RAD L

20、 RD L RBDCD L R以先序遍历以先序遍历D L RD L R为例演示遍历过程为例演示遍历过程 ABDCBDAC DBCA三、算法的递归描述三、算法的递归描述void Preorder (BTree *b)/采用二叉链表存储结构，先序遍历二叉树采用二叉链表存储结构，先序遍历二叉树b b / / 初始条件：二叉树初始条件：二叉树b b存在，存在， / / 操作结果：先序递归遍操作结果：先序递归遍历历b b，打印每，打印每个结个结点一点一次且仅一次次且仅一次 if (T) / b不空不空 print(“%c”,b-data); /先访问根结点先访问根结点 Preorder(b-lchild

21、); /再先序遍历左子树再先序遍历左子树 Preorder(b-rchild);/最后先序遍历右子树最后先序遍历右子树 A B C E F D G A B C D E F G (a) (b) typedef struct node / 结点结构结点结构 TElemType data;/数据元素数据元素 struct node *lchild, *rchild; / 左右孩子指针左右孩子指针 BTNode;b四、中序遍历算法的非递归描述四、中序遍历算法的非递归描述 A B C E F D G A B C D E F G (a) (b) T void InOrder(BTNode *b) BTNo

22、de *StMaxSize,*p; int top=-1;if (b!=NULL) p=b; while (top-1 | p!=NULL) while (p!=NULL) /扫描扫描*p的所有左结点并进栈的所有左结点并进栈 top+; Sttop=p; p=p-lchild; if (top-1) p=Sttop;top-; /出栈出栈*p结点结点 printf(%c ,p-data); /访问之访问之 p=p-rchild; /扫描扫描*p的右孩子结点的右孩子结点 /end of while(top-1 | p!=NULL) 找找*b的最左下结点的最左下结点b五五、遍历算法的应用举例遍历算

23、法的应用举例1、输出一棵二叉树的所有叶子结点输出一棵二叉树的所有叶子结点2 2、建立二叉树的存储结构、建立二叉树的存储结构3 3、二叉树的构造（由遍历序列确、二叉树的构造（由遍历序列确定二叉树）定二叉树）假设二叉树采用二叉链存储结构存储假设二叉树采用二叉链存储结构存储,试设计一个算试设计一个算法法,输出一棵给定二叉树的所有叶子结点。输出一棵给定二叉树的所有叶子结点。 解：输出一棵二叉树的所有叶子结点的递归模型解：输出一棵二叉树的所有叶子结点的递归模型f()如下：如下： f(b)：不做任何事件：不做任何事件 若若b=NULL f(b)：输出：输出*b结点的结点的data域域 若若*b为叶子结点为

24、叶子结点 f(b)：f(b-lchild);f(b-rchild) 其他情况其他情况 void DispLeaf(BTNode *b)/p166 例例7.8 /输出二叉树中的叶子结点输出二叉树中的叶子结点 if (b!=NULL) if (b-lchild=NULL & b-rchild=NULL) printf(“%c ”,b-data);/访问叶子结点访问叶子结点 else DispLeaf(b-lchild);/输出左子树中的叶子结点输出左子树中的叶子结点 DispLeaf(b-rchild);/输出右子树中的叶子结点输出右子树中的叶子结点 A B C E F D G A B C

25、 D E F G (a) (b) b2 2、建立二叉树的存储、建立二叉树的存储结构结构不同的定义方法相应有不同的不同的定义方法相应有不同的存储结构的建立算法存储结构的建立算法 以字符串的形式以字符串的形式 根根 左子树左子树 右子树右子树定义一棵二叉树定义一棵二叉树例如:ABCD以空白字符“ ”表示A(B( ,C( , ),D( , )空树空树只含一个根结点只含一个根结点的二叉树的二叉树A以字符串“A ”表示以下列字符串表示void CreateBiTree(BiTree &T) /按先序次序输入二叉树中结点的值按先序次序输入二叉树中结点的值( (字符型字符型) )， / / 构造二叉

26、链表表示的二叉树构造二叉链表表示的二叉树T T。 scanf(&ch); / / 输入结点的值输入结点的值 if(ch= ) T=NULL; / / 结点的值为空结点的值为空 else / 结点的值不为空结点的值不为空 T=(BiTree)malloc(sizeof(BTNode); / / 生成根结点生成根结点 if(!T) exit(OVERFLOW); T-data=ch; / / 将值赋给将值赋给T T所指结点所指结点 CreateBiTree(T-lchild); / / 递归构造左子树递归构造左子树 CreateBiTree(T-rchild); / / 递归构造右子树递归

27、构造右子树 typedef struct node / 结点结构结点结构 TElemType data;/数据元素数据元素 struct node *lchild, *rchild; / 左右孩子指针左右孩子指针 BTNode; *BiTreeA B C D A BCD算法执行过程举例如下：ATBCDscanf(&ch); if(ch= ) T=NULL; else T=(BiTree)malloc(sizeof(BTNode); / 生成根结点生成根结点 if(!T) exit(OVERFLOW); T-data=ch; CreateBiTree(T-lchild); / 递归构造左

28、子树递归构造左子树 CreateBiTree(T-rchild); / 递归构造右子树递归构造右子树void CreateBiTree(BiTree &T)typedef struct node / 结点结构结点结构 TElemType data;/数据元素数据元素 struct node *lchild, *rchild; / 左右孩子指针左右孩子指针 BTNode; *BiTree 仅知二叉树的先序序列“abcdefg” 不能唯一确定一棵二叉树，由遍历序列确定二叉树由遍历序列确定二叉树 如果同时已知二叉树的中序序列“cbdaegf”，则会如何？ 二叉树的先序序列二叉树的中序序列左子

29、树左子树左子树左子树 右子树右子树右子树右子树根根根根由二叉树的先序和中序序列确定二叉树由二叉树的先序和中序序列确定二叉树a b c d e f gc b d a e g f例如例如: :aab bccddeeffggabcdefg先序序列中序序列6.5线索二叉树线索二叉树 何谓线索二叉树？何谓线索二叉树？ 线索链表的遍历算法线索链表的遍历算法 如何建立线索链表？如何建立线索链表？一、一、何谓线索二叉树？何谓线索二叉树？遍历二叉树的结果是， 求得结点的一个线性序列。ABCDEFGHK例如:先序先序序列: A B C D E F G H K中序中序序列: B D C A H G K F E后序后

30、序序列: D C B H K G F E A指向该线性序列中的“前驱”和 “后继” 的指针指针，称作“线索线索”与其相应的二叉树，称作 “线索二叉树线索二叉树”包含 “线索” 的存储结构，称作 “线索链线索链表表”A B C D E F G H K D C B E 意义：保存遍历二叉树后得到的线性序列，避免重复遍历。意义：保存遍历二叉树后得到的线性序列，避免重复遍历。对对线索链表线索链表中结点的约定：中结点的约定： 在二叉链表的结点中增加两个标志域增加两个标志域，规定如下：如此定义的二叉树的存储结构称作如此定义的二叉树的存储结构称作“线索链表线索链表”。左标志左标志ltag : 0 表示表示l

31、child指向左孩子结点指向左孩子结点 1 表示表示lchild指向前驱结点指向前驱结点右标志右标志rtag : 0 表示表示rchild指向右孩子结点指向右孩子结点 1 表示表示rchild指向后继结点指向后继结点这样这样,每个结点的存储结构如下：每个结点的存储结构如下：LChildLtagDataRtagRChild 为了实现线索化二叉树为了实现线索化二叉树,将前面二叉树结点的类型将前面二叉树结点的类型定义如下：定义如下： typedef struct node ElemType data;/*结点数据域结点数据域*/ int ltag,rtag; /*增加的线索标记增加的线索标记*/ s

32、truct node *lchild;/*左孩子或线索指针左孩子或线索指针*/ struct node *rchild;/*右孩子或线索指针右孩子或线索指针*/ TBTNode;/*线索树结点类型定义线索树结点类型定义*/ lchildltagdatartagrchild二、线索链表的遍历算法二、线索链表的遍历算法（p184）:由于在线索链表中添加了遍历中得到的“前驱”和“后继”的信息，从而简化了遍历的算法。例如例如: 对中序线索化链表的遍历算法对中序线索化链表的遍历算法 中序遍历的第一个结点中序遍历的第一个结点 ？左子树上处于“最左下最左下”（没有左子树）的结点。 在中序线索化链表中结点的后

33、继在中序线索化链表中结点的后继 ？若若无右子树，则为则为后继线索后继线索所指结点；否则为否则为对其右子树右子树进行中序遍历遍历时访问的第一个结点。第一个结点。 0 1 0 A 0 0 B 1 0 C 0 1 E 1 1 F 1 1 D 0 1 G 1 0 1 0 A 0 0 B 1 0 C 0 1 E 1 1 F 1 1 D 0 1 G 1 Thrt Thrt 0 1 0 A 0 0 B 1 0 C 0 1 E 1 1 F 1 1 D 0 1 G 1 Thrt (a) 中序线索树 (b) 先序线索树 (c) 后序线索树 lchildltagdatartagrchild A B C D E F

34、G 二叉树二叉树void ThInOrder(TBTNode *tb)/ 中序遍历线索二叉树中序遍历线索二叉树tb (头结点头结点)的非递归算法的非递归算法 TBTNode *p=tb-lchild;/*p指向根结点指向根结点*/ while (p!=tb)/非非空树或遍历未结束时空树或遍历未结束时 while (p-ltag=0) p=p-lchild;/*找开始结点找开始结点*/ printf(%c,p-data);/*访问开始结点访问开始结点*/ while (p-rtag=1 & p-rchild!=tb) / p-rchild是线索是线索(后继后继)，且不是遍历的最后一个结点

35、，且不是遍历的最后一个结点 p=p-rchild; / p指向其后继 printf(%c,p-data); / / 若若p-rchildp-rchild不是线索不是线索( (是右孩子是右孩子) )，p p指向右孩子，返回循环，找这指向右孩子，返回循环，找这棵子树中序遍历的第棵子树中序遍历的第1 1个结点个结点 p=p-rchild; 建立线索二叉树建立线索二叉树,或者说或者说,对二叉树线索化对二叉树线索化,实质上就实质上就是遍历一棵二叉树是遍历一棵二叉树,在遍历的过程中在遍历的过程中,检查检查当前结点的左、当前结点的左、右指针域是否为空右指针域是否为空。如果为空如果为空,将它们改为指向前驱结将

36、它们改为指向前驱结点或后继结点的线索。点或后继结点的线索。另外另外,在对一棵二叉树添加线索在对一棵二叉树添加线索时时,我们我们创建一个头结点创建一个头结点,并建立头结点与二叉树的根结并建立头结点与二叉树的根结点的线索点的线索。对二叉树线索化后。对二叉树线索化后,还须建立还须建立最后一个结点最后一个结点与头结点之间的线索。与头结点之间的线索。 下面以中序线索二叉树为例下面以中序线索二叉树为例,讨论建立线索二叉树的讨论建立线索二叉树的算法。算法。 三、如何建立线索链表？三、如何建立线索链表？CreaThread(b)算法是将以二叉链存储的算法是将以二叉链存储的二叉树二叉树b进行进行中序线索化中序线

37、索化,并返回线索化后头结点的指针并返回线索化后头结点的指针root。Thread(p)算法用于对于以算法用于对于以*p为根结点为根结点的二叉树中序线的二叉树中序线索化。在整个算法中索化。在整个算法中p总是总是指向当前指向当前被线索化的被线索化的结点结点,而而pre作为作为全局变量全局变量,指向指向刚刚访问过的结点刚刚访问过的结点,*pre是是*p的前驱结点的前驱结点,*p是是*pre的后继结点。的后继结点。 CreaThread(b)算法思路是：算法思路是：先创建头结点先创建头结点*root,其其lchild域为线索域为线索,rchild域为链指针。将域为链指针。将rchild指针指指针指向向

38、*b,如果如果b二叉树为空二叉树为空,则将其则将其lchild指向自身。否则将指向自身。否则将*root的的lchild指向指向*b结点结点,p指向指向*b结点结点,pre指向指向*root结结点。点。再调用再调用Thread(b)对整个二叉树线索化对整个二叉树线索化。最后加入最后加入指向头结点的线索指向头结点的线索,并并将头结点的将头结点的rchild指针域线索化指针域线索化为指向最后一个结点为指向最后一个结点(由于线索化直到由于线索化直到p等于等于NULL为为止止,所以最后一个结点为所以最后一个结点为*pre)。TBTNode *CreaThread(TBTNode *b) /中序线索化二

39、叉树中序线索化二叉树b TBTNode *root; root=(TBTNode *)malloc(sizeof(TBTNode); /创建头结点创建头结点 root-ltag=0;root-rtag=1; root-rchild=b; if (b=NULL) root-lchild=root;/空二叉树空二叉树 else root-lchild=b;/;/头结点的左孩子指针指向根结点头结点的左孩子指针指向根结点pre=root; / pre(/ pre(前驱前驱) )的初值指向头结点，全局变量的初值指向头结点，全局变量 Thread(b); / / 中序线索化，中序线索化，prepre指向中

40、序遍历的最后一个结点指向中序遍历的最后一个结点pre-rchild=root; /最后处理最后处理, ,加入指向头结点的线索加入指向头结点的线索pre-rtag=1;root-rchild=pre; /头结点右线索化头结点右线索化 return root; Thread(p)算法思路是：类似于中序遍历的递归算算法思路是：类似于中序遍历的递归算法法,在在p指针不为指针不为NULL时时,先对先对*p结点的左子树线索结点的左子树线索化；化；若若*p结点没有左孩子结点结点没有左孩子结点,则将其则将其lchild指针线索化为指针线索化为指向其前驱结点指向其前驱结点*pre,否则表示否则表示lchild指

41、向其左孩子结指向其左孩子结点点,将其将其ltag置为置为1；若若*pre结点的结点的rchild指针为指针为NULL,将其将其rchild指针线索化为指向其后继结点指针线索化为指向其后继结点*p,否则否则rchild表示指向其右孩子结点表示指向其右孩子结点,将其将其rtag置为置为1,再将再将pre指向指向*p；最后对最后对*p结点的右子树线索化。结点的右子树线索化。TBTNode *pre; /全局变量始终指向刚刚访问过的结点全局变量始终指向刚刚访问过的结点void Thread(TBTNode *&p) /对以结点对以结点p为根为根的子树中序线索化的子树中序线索化/ 通过中序遍历进

42、行中序线索化，线索化之后通过中序遍历进行中序线索化，线索化之后pre指向最后一个结点。指向最后一个结点。 if (p!=NULL) Thread(p-lchild); /左子树线索化左子树线索化if (p-lchild=NULL) /前驱线索前驱线索 p-lchild=pre; p-ltag=1; /建立当前结点的前驱线索建立当前结点的前驱线索else p-ltag=0;if (pre-rchild=NULL) /后继线索后继线索 pre-rchild=p;pre-rtag=1;/建立前驱结点的后继线索建立前驱结点的后继线索else pre-rtag=0; pre=p; / / 保持保持pre

43、pre指向指向p p的前驱的前驱Thread(p-rchild); /递归调用右子树线索化递归调用右子树线索化 6.6 树和森林树和森林 的表示方法的表示方法树的三种存储结构树的三种存储结构一、一、双亲表示法双亲表示法二、二、孩子链表表示法孩子链表表示法三、三、树的二叉链表树的二叉链表( (孩子孩子- -兄弟）兄弟） 存储表示法存储表示法ABCDEFG0 A -11 B 02 C 03 D 04 E 2 5 F 26 G 5r=0n=7data parent一、双亲表示法一、双亲表示法: typedef struct PTNode Elem data; int parent; / 双亲位置域双

44、亲位置域 PTNode; typedef struct PTNode nodes MAX_TREE_SIZE; int r, n; / 根结点的位置和结点个数 PTree;结点结构结点结构:树结构树结构:#define MAX_TREE_SIZE 100 typedef struct PTNode Elem data; int parent; / 双亲位置域 PTNode; data parent#define MAX_TREE_SIZE 100结点结构结点结构:C语言的类型描述语言的类型描述: :typedef struct PTNode nodes MAX_TREE_SIZE; int r

45、, n; / 根结点的位置和结点个数 PTree;树结构树结构:ABCDEFG0 A1 B 2 C 3 D 4 E 5 F 6 G r=0n=7 1 2 34 56二、孩子链表表示法二、孩子链表表示法:parent 1 0 0 0 2 2 4datafirstchildtypedef struct CTNode int child; struct CTNode *next; *ChildPtr;孩子结点结构孩子结点结构: child nextC语言的类型描述语言的类型描述: :双亲结点结构双亲结点结构 data firstchildtypedef struct Elem data; Child

46、Ptr firstchild; / 孩子链的头指针 CTBox;树结构树结构:typedef struct CTBox nodesMAX_TREE_SIZE; int n, r; / 结点数和根结点的位置 CTree;ABCDEFG AB C E D F Groot AB C E D F G 三、树的二叉链表三、树的二叉链表 (孩子孩子-兄弟）存储表示法兄弟）存储表示法 firstchild data nextsibling结点结构结点结构typedef struct CSNode Elem data; struct CSNode *firstchild, *nextsibling; CSNo

47、de, *CSTree;CSTree roottypedef struct CSNode Elem data; struct CSNode *firstchild, *nextsibling; CSNode, *CSTree;C语言的类型描述语言的类型描述: :结点结构结点结构: firstchild data nextsibling树、森林与二叉树的相互转换树、森林与二叉树的相互转换1. 树转换为二叉树树转换为二叉树由于二叉树可以用二叉链表表示，为了使一般树也能用二叉链由于二叉树可以用二叉链表表示，为了使一般树也能用二叉链表表示，必须找出树与二叉树之间的关系。表表示，必须找出树与二叉树之间的

48、关系。 这样，给定一棵树，可以找到唯一的一棵二叉树与之对应。这样，给定一棵树，可以找到唯一的一棵二叉树与之对应。(1) 树中所有相邻兄弟之间加一条连线。 (2) 对树中的每个结点，只保留其与第一个孩子结点之间的连线， 删去其与其它孩子结点之间的连线。 (3) 以树的根结点为轴心，将整棵树顺时针旋转一定的角度， 使之结构层次分明。 I A B C DE F G H(b) A B CD E G H FI(a)树转换为二叉树树转换为二叉树ABEFCDGHI(d)ABCDEFGHI(c)注意：注意：树转换为二叉树后，根无右子树。树转换为二叉树后，根无右子树。树与二叉树的对应 树的二叉链表树的二叉链表

49、(孩子孩子-兄弟）兄弟）存储表示法存储表示法二叉树二叉链表二叉树二叉链表存储表示法存储表示法 2. 森林转换为二叉树森林转换为二叉树 （1） 将森林中的每棵树转换成相应的二叉树。 （2） 第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子，当所有二叉树连在一起后，所得到的二叉树就是由森林转换得到的二叉树。 森林转换为二叉树的过程 森林转换后的二叉树，其根结点有右孩子由森林转换成二叉树由森林转换成二叉树的转换规则为:若 F = ，则 B = ；否则， 由 ROOT( T1 ) 对应得到B的根的根 root； 由 (t11, t12, , t1m1 )

50、对应得到 LB； 由 (T2, T3, Tm ) 对应得到 RB。设设森林森林 F = ( T1, T2, , Tm ); T1 = (root，t11, t12, , t1m1);二叉树二叉树 B =(root, LB, RB );由二叉树转换为森林由二叉树转换为森林的转换规则为：若 B = ， 则 F = ；否则，由 root 对应得到 ROOT( T1 )；由LB 对应得到 T1中的子森林（中的子森林（ t11, t12, ，t1m)；由RB 对应得到 (T2, T3, , Tn)。 3. 3. 二叉树还原为树或森林二叉树还原为树或森林（1 1） 若某结点是其双亲的左孩子，则把该结点的右

51、孩子、若某结点是其双亲的左孩子，则把该结点的右孩子、 右孩子的右孩子右孩子的右孩子都与该结点的双亲结点用线连起来。都与该结点的双亲结点用线连起来。 （2 2） 删掉原二叉树中所有双亲结点与右孩子结点的连线。删掉原二叉树中所有双亲结点与右孩子结点的连线。 （3 3） 整理由（整理由（1 1）、（）、（2 2）两步所得到的树或森林。）两步所得到的树或森林。 二叉树到森林的转换示例二叉树到森林的转换示例 设设二叉树二叉树 B =(root, LB, RB );森林森林 F = ( T1, T2, , Tm ); 由此，树的各种操作均可对应二叉树的操作来完成。 应当注意的是，应当注意的是，和树对应的二

52、叉树，其左、右子树的概念已改变为： 左是孩子，右是兄弟。左是孩子，右是兄弟。6.7 哈夫曼树与应用哈夫曼树与应用 最优树的定义最优树的定义 如何构造最优树如何构造最优树 哈夫曼树与应用哈夫曼树与应用 一、最优树的定义一、最优树的定义树的路径长度树的路径长度定义为： 树中每个结点的路径长度之和。 结点的路径长度结点的路径长度定义为： 从根结点到该结点的路径上 分支的数目。 树的带权路径长度树的带权路径长度定义为： 树中所有叶子结点的带权路径长度结点的带权路径长度之和 WPL(T) = wklk (对所有叶子结点)。 在所有含 n 个叶子结点、并带相同权值的 m 叉树中，必存在一棵其带权路径带权路

53、径长度取最小值长度取最小值的树，称为“最优树最优树”。例如：例如：27 9 75492WPL(T)= 72+52+23+43+92 =60WPL(T)= 74+94+53+42+21 =89 54给定权值给定权值w=1,3,5,7来构造一棵哈夫曼树来构造一棵哈夫曼树 。 9 4 1 7 5 3 16 9 4 1 7 5 3 (c) (d) 1 3 5 7 4 5 7 1 3 (a) (b) (1) 根据给定的根据给定的 n 个权值个权值 w1, w2, , wn， 构造构造 n 棵二叉树的集棵二叉树的集合合F = T1, T2, , Tn，其中每棵二叉树中均只含一个带权值为，其中每棵二叉树中均

54、只含一个带权值为 wi 的根结点，其左、右子树为空树；的根结点，其左、右子树为空树； (2) 在在 F 中选取其根结点的权值为最小的两棵二叉树，分别作中选取其根结点的权值为最小的两棵二叉树，分别作为左、右子树构造一棵新的二叉树，并置这棵新的二叉树根结为左、右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和；点的权值为其左、右子树根结点的权值之和；(3) 从从F中删去这两棵树，同时加入刚生成的新树；中删去这两棵树，同时加入刚生成的新树；(4) 重复重复 (2) 和和 (3) 两步，直至两步，直至 F 中只含一棵树为止。中只含一棵树为止。二、二、如何构造最优二叉树（哈夫曼树）如何