数据结构第5章 二叉树及应用

1、第五章第五章 二叉树及应用二叉树及应用一种重要的非线性结构一种重要的非线性结构学习要点：学习要点：二叉树的递归概念，这与二叉树各种基本运算具有密切关联。二叉树的递归概念，这与二叉树各种基本运算具有密切关联。满二叉树和完全二叉树概念，二叉树和完全二叉树基本性质。满二叉树和完全二叉树概念，二叉树和完全二叉树基本性质。二叉树的顺序存储与二叉链表存储结构。二叉树的顺序存储与二叉链表存储结构。二叉树遍历的基本思想和基于递归与非递归实现算法。二叉树遍历的基本思想和基于递归与非递归实现算法。线索二叉树概念，二叉树的线索化和遍历。线索二叉树概念，二叉树的线索化和遍历。Huffman树概念与基本算法；树概念与基

2、本算法；Huffman编码和实现算法。编码和实现算法。25.1 二叉树及其基本性质二叉树及其基本性质5.1.1 二叉树基本概念二叉树基本概念“二叉树二叉树”是一个满足下述条件的由结点组成的有限集合是一个满足下述条件的由结点组成的有限集合E： 当当E为空集时，定义其为空二叉树；为空集时，定义其为空二叉树； 当当E非空时，分为两种情形。非空时，分为两种情形。 如果如果E为单元素集合，定义其为一棵为单元素集合，定义其为一棵根二叉树根二叉树； 如果如果E为多于一个结点的集合，则为多于一个结点的集合，则E中应当具有唯一一个结点中应当具有唯一一个结点r称其为根结点，而集合称其为根结点，而集合E=E r也是

3、一棵二叉树，称为也是一棵二叉树，称为r的子二的子二叉树。此时，结点叉树。此时，结点r至多只能有两棵不相交的子二叉树，并且相至多只能有两棵不相交的子二叉树，并且相应子二叉树有左右之分，分别称为应子二叉树有左右之分，分别称为r的的左子树左子树和和右子树右子树。35.1.1 二叉树基本概念二叉树基本概念21、二叉树的特征、二叉树的特征二叉树可以没有任何结点，即是一个空二叉树。二叉树可以没有任何结点，即是一个空二叉树。二叉树中每个结点至多只有两棵子树，而这两棵子树作为结点二叉树中每个结点至多只有两棵子树，而这两棵子树作为结点集合互不相交；集合互不相交；二叉树中结点的两棵子树有左、右之分，次序不能颠倒。

4、二叉树中结点的两棵子树有左、右之分，次序不能颠倒。2、二叉树基本类型、二叉树基本类型4介绍另外一种树型结构：介绍另外一种树型结构： 树的基本概念：树的基本概念：5树（树（Tree）是一个由是一个由n（n0）个结点构成的有限集合）个结点构成的有限集合T。 当当n=0时，称时，称T为为“空树空树”。 当当n0时，时，T中诸元素满足下述条件：中诸元素满足下述条件： 有且仅有一个特定数据元素没有前驱，称其为有且仅有一个特定数据元素没有前驱，称其为T的的根结点根结点。 除根结点外其余数据元素，又可分为除根结点外其余数据元素，又可分为m（0m1，则，则N父结点序号为父结点序号为 （即（即i除以除以2后向下

5、取整）；后向下取整）；（3）若）若2in，则，则N无左子树，否则其左子结点（即左子树的根无左子树，否则其左子结点（即左子树的根结点）序号为结点）序号为2i；（4）若）若2i+1n，则，则N无右子树，否则其右子结点（即右子树无右子树，否则其右子结点（即右子树的根结点）序号为的根结点）序号为2i+1。2/ i练习：练习：1、1000个结点的完全二叉树最大的分支结点编号为个结点的完全二叉树最大的分支结点编号为 。2、n个结点的完全二叉树深度为个结点的完全二叉树深度为 。18500int（log2n）5.2 二叉树存储二叉树存储5.2.1 二叉树顺序存储二叉树顺序存储 预留最大空间预留最大空间 深度为

6、深度为k的二叉树预留的二叉树预留2k+1-1个存储单元，按编号顺序存个存储单元，按编号顺序存储，遇空结点留空位。储，遇空结点留空位。 195.2.1 二叉树顺序存储二叉树顺序存储2适合满（完全）二叉树，求双亲、孩子方便适合满（完全）二叉树，求双亲、孩子方便不适合深度较大、结点不多的二叉树不适合深度较大、结点不多的二叉树205.2.2 二叉树链式存储二叉树链式存储1、二叉链表存储、二叉链表存储 让一个存储结点只包含与其子树的邻接关系，那么就让一个存储结点只包含与其子树的邻接关系，那么就是二叉树的二叉链表存储结构。是二叉树的二叉链表存储结构。215.2.2 二叉树链式存储二叉树链式存储1、二叉链表

7、存储、二叉链表存储222用用C语言定义二叉链表的结构类型如下：语言定义二叉链表的结构类型如下： struct node DataType data; /* 定义数据域，定义数据域，DataType代表实际需要的类型代表实际需要的类型 */ struct node *lch; /* 定义左孩子域，指向左孩子地址定义左孩子域，指向左孩子地址 */ struct node *rch; /* 定义右孩子域，指向右孩子地址定义右孩子域，指向右孩子地址 */ ; typedef struct node bitree; /* 定义二叉树结点类型为定义二叉树结点类型为bitree */1、二叉链表存储、二叉链

8、表存储3算法算法5-1 创建一棵只有根结点的二叉树算法。创建一棵只有根结点的二叉树算法。 创建只有以创建只有以x为根结点的二叉树为根结点的二叉树Bt，x的数据类型为的数据类型为DataType，相，相应结点的应结点的Lchild和和Rchild域均取值域均取值NULL，返回指向根结点的指针。，返回指向根结点的指针。2300Create_Bt(DataType x)01 02 bitree *Bt,*ptr;03 ptr = (bitree *) malloc (sizeof(bitree); /* 申请存储结点申请存储结点 */04 Bt=ptr;05 ptr-data = x;06 ptr-

9、lch = NULL;07 ptr-rch = NULL;08 return (Bt);09 1、二叉链表存储、二叉链表存储4算法算法5-2 在指定左子结点处插入一个新结点。在指定左子结点处插入一个新结点。 已知二叉链表已知二叉链表Bt，在指针，在指针Parent所指结点左子结点处插入一个数所指结点左子结点处插入一个数据元素值为据元素值为x的新结点，使之成为的新结点，使之成为Parnet所指结点新的左子树根结点。所指结点新的左子树根结点。24 bitree *Inl_Bt(bitree *Bt, bitree *Parent, DataType x) if (Parent = NULL) pr

10、intf (位置错！位置错！); return (NULL); ptr = (bitree *) malloc (sizeof(bitree); /* 申请存储结点空间申请存储结点空间 */ ptr-data = x; ptr-lch = NULL; ptr-rch = NULL; if (Parent-lch = NULL) /* Parent所指结点左子树为空所指结点左子树为空 */ Parent-lch = ptr; else /* Parent所指结点左子树非空所指结点左子树非空 */ ptr-lch = Parent-lch; Parent-lch = ptr; return(Bt)

11、 5.2.2 二叉树链式存储二叉树链式存储22、三叉链表存储、三叉链表存储 同时反映当前结点与其左子树的根结点、右子树的根同时反映当前结点与其左子树的根结点、右子树的根结点和与其父结点关联。结点和与其父结点关联。255.2.2 二叉树链式存储二叉树链式存储22、三叉链表存储、三叉链表存储2265.3 二叉树的遍历二叉树的遍历按照某种确定方式对二叉树进行访问，但要求二叉树中每按照某种确定方式对二叉树进行访问，但要求二叉树中每个结点被访问一次且只被访问一次。个结点被访问一次且只被访问一次。1、先序、中序和后序遍历、先序、中序和后序遍历对左、右子树，限定对左、右子树，限定“先访左后访右先访左后访右”

12、，那么访问结点的，那么访问结点的顺序顺序有有三种不同的组合形式：三种不同的组合形式：TLR、LTR、LRT。通常，称通常，称TLR为二叉树的先序（先根）遍历，为二叉树的先序（先根）遍历， LTR为中序为中序（中根）遍历，（中根）遍历， LRT为后序（后根）遍历。为后序（后根）遍历。27例子：例子：以三种遍历方式访问如图所示的二叉树。以三种遍历方式访问如图所示的二叉树。28解：解：先序遍历序列先序遍历序列 A-B-D-H-E-C-F-I-G-J-K中序遍历序列中序遍历序列 D-H-B-E-A-I-F-C-J-G-K后序遍历序列后序遍历序列 H-D-E-B-I-F-J-K-G-C-A例子：例子：已

13、知二叉树已知二叉树先先序遍历序列是序遍历序列是A-B-C-D-E-F-G，中序遍历序，中序遍历序列是列是C-B-D-A-E-G-F。由这两个序列可唯一确定一棵二叉树。由这两个序列可唯一确定一棵二叉树。29解：从先序遍历序列第一个结点可知二叉树根结点是解：从先序遍历序列第一个结点可知二叉树根结点是A。由结点。由结点A在在中序遍历序列里位置可知该根结点左子树包含结点中序遍历序列里位置可知该根结点左子树包含结点C-B-D，右子树，右子树包含结点包含结点E-G-F，如图，如图5-22所示。由中序序列片段所示。由中序序列片段C-B-D可知，可知，B是是A左子树根结点，再结合先序序列片段左子树根结点，再结

14、合先序序列片段B-C-D可知，可知，C和和D分别是分别是B的的左右子结点。由先序序列片段左右子结点。由先序序列片段E-F-G可知，可知，E是是A的右子结点，再由的右子结点，再由先序序列片段先序序列片段F-G和中序序列片段和中序序列片段G-F可知，可知，F不能是不能是E的左子结点，的左子结点，故只能是故只能是E的右子结点，并且的右子结点，并且G是是F的左子结点。的左子结点。30练习：练习：1、已知二叉树先序遍历序列为、已知二叉树先序遍历序列为ABCDEFGH，中序遍历序列为，中序遍历序列为CDBAFEHG，试画出此二叉树。，试画出此二叉树。2、已知二叉树后序遍历序列为、已知二叉树后序遍历序列为D

15、CBFHGEA，中序遍历序列为，中序遍历序列为CDBAFEHG，求先序遍历序列。，求先序遍历序列。315.3 二叉树的遍历二叉树的遍历22、基于递归遍历算法、基于递归遍历算法递归步骤递归步骤（先序遍历先序遍历）：）： 访问根结点；访问根结点； 先序遍历访问左子二叉树；先序遍历访问左子二叉树； 先序遍历访问右子二叉树。先序遍历访问右子二叉树。322、基于递归遍历算法、基于递归遍历算法2算法算法5-4 二叉树先序遍历递归算法。二叉树先序遍历递归算法。 已知二叉树已知二叉树Bt，对其进行先序遍历，若二叉树为空，则为空操作；否则，对其进行先序遍历，若二叉树为空，则为空操作；否则进行如下操作：访问二叉树

16、根结点；先序遍历二叉树的左子树；先序遍历二叉进行如下操作：访问二叉树根结点；先序遍历二叉树的左子树；先序遍历二叉树的右子树。树的右子树。3300 Pret_Bt(bitree *Bt)01 02 if (Bt != NULL)03 04 printf (%c, Bt-data); /* 访问根结点访问根结点 */05 Pret_Bt(Bt-lch); /* 先序遍历左子树先序遍历左子树 */06 Pret_Bt(Bt-rch); /* 先序遍历右子树先序遍历右子树 */07 08 2、基于递归遍历算法、基于递归遍历算法2基于递归调用先序遍历基于递归调用先序遍历:342、基于递归遍历算法、基于递

17、归遍历算法2先序递归算法应用实例先序递归算法应用实例:先序建立二叉树先序建立二叉树bitree *creat() bitree *t; int x; scanf(“%d”,&x); if (x=0) t=NULL; else t=(bitree *) malloc (sizeof(bitree); t-data=x; t-lch=creat(); t-rch=creat(); return t; 2、基于递归遍历算法、基于递归遍历算法2先序递归算法应用实例先序递归算法应用实例:先序建立二叉树先序建立二叉树(续续)主程序调用主程序调用:main() bitree *root; root=crea

18、t(); 例：例：建立如图二叉树应该如何输入？建立如图二叉树应该如何输入？练习：练习： 测试用例：测试用例：1 2 3 0 0 4 0 5 0 0 6 0 0 问：画出建立的二叉树？问：画出建立的二叉树？2、基于递归遍历算法、基于递归遍历算法3算法算法5-5 二叉树中序遍历递归算法。二叉树中序遍历递归算法。 已知二叉树已知二叉树Bt，对其进行中序遍历，若二叉树为空，则为空操作；否则，对其进行中序遍历，若二叉树为空，则为空操作；否则进行如下操作：中序遍历二叉树的左子树；访问二叉树根结点；中序遍历二叉进行如下操作：中序遍历二叉树的左子树；访问二叉树根结点；中序遍历二叉树的右子树。树的右子树。370

19、0 Indt_Bt(bitree *Bt)01 02 if (Bt != NULL)03 04 Indt_Bt(Bt-lch);/* 中序遍历左子树中序遍历左子树 */05 printf (%c, Bt-data);/* 访问根结点访问根结点 */06 Indt_Bt(Bt-rch);/* 中序遍历右子树中序遍历右子树 */07 08 2、基于递归遍历算法、基于递归遍历算法3基于递归调用基于递归调用中中序遍历序遍历:382、基于递归遍历算法、基于递归遍历算法4算法算法5-6 二叉树后序遍历递归算法。二叉树后序遍历递归算法。 已知二叉树已知二叉树Bt，对其进行后序遍历，若二叉树为空，则为空操作；

20、否则，对其进行后序遍历，若二叉树为空，则为空操作；否则进行如下操作：后序遍历二叉树的左子树；后序遍历二叉树的右子树；访问二进行如下操作：后序遍历二叉树的左子树；后序遍历二叉树的右子树；访问二叉树根结点。叉树根结点。3900 Postv_Bt(bitree *Bt)01 02 if (Bt != NULL)03 04 Postv_Bt(Bt-lch); /* 后序遍历左子树后序遍历左子树 */05 Postv_Bt(Bt-rch); /* 后序遍历右子树后序遍历右子树 */06 printf (%c, Bt-data); /* 访问根结点访问根结点 */07 08 2、基于递归遍历算法、基于递归

21、遍历算法4基于递归调用基于递归调用后后序遍历序遍历:405.3 二叉树的遍历二叉树的遍历33、基于非递归遍历算法、基于非递归遍历算法非递归遍历算法中，需要做出三条假设：非递归遍历算法中，需要做出三条假设： 设置一个一维数组设置一个一维数组Ss作为顺序栈以临时保存遍历时遇到的结作为顺序栈以临时保存遍历时遇到的结点信息，其栈顶指针为点信息，其栈顶指针为Ss-top，初始时为，初始时为0。 采用二叉链表结构保存需要遍历的二叉树，起始指针为采用二叉链表结构保存需要遍历的二叉树，起始指针为Bt，每个结点包含每个结点包含Data、Lchild和和Rchild等三个域。等三个域。 对结点进行的对结点进行的“

22、访问访问”理解为将该结点的理解为将该结点的Data域的值打印出域的值打印出来。来。413、基于非递归遍历算法、基于非递归遍历算法2算法算法5-7 先序遍历二叉树的非递归算法。先序遍历二叉树的非递归算法。已知二叉树已知二叉树Bt，顺序栈，顺序栈Ss，要求打印出该二叉树的先序遍历序列。，要求打印出该二叉树的先序遍历序列。4200 Pre_Bt(bitree *Bt)01 02 bitree *p;03 bitree *stack10; /* 定义栈数组定义栈数组 */04 int top=-1; /* 定义栈顶下标定义栈顶下标top并赋初值并赋初值-1 */05 printf(nOutput pr

23、eorder:);06 p= Bt;07 while(p!=NULL | top!=-1)08 if (p!=NULL)09 10 printf(%d ,p-data); /* 访问该结点访问该结点 */11 top=top+1;stacktop=p; /* 访问后入栈访问后入栈 */12 p=p-lch; /* 继续深入左孩子继续深入左孩子 */13 14 else15 16 p=stacktop;top=top-1; /* 遇空出栈，栈顶给遇空出栈，栈顶给p */17 p=p-rch; /* 转向右孩子转向右孩子 */18 19 3、基于非递归遍历算法、基于非递归遍历算法2基于非递归二叉树

24、先序遍历：基于非递归二叉树先序遍历：433、基于非递归遍历算法、基于非递归遍历算法3中序非递归遍历算法流程中序非递归遍历算法流程:v bitree *p; 定义及初始化栈定义及初始化栈;v p=root;v while(p!=NULL | 栈不空栈不空)v if (p!=NULL) v p进栈；进栈；p=p-lch;v elsev 栈顶给栈顶给p并出栈；并出栈；输出输出p；p=p-rch;3、基于非递归遍历算法、基于非递归遍历算法3算法算法5-8 中序遍历二叉树的非递归算法。中序遍历二叉树的非递归算法。已知二叉树已知二叉树Bt，顺序栈，顺序栈Ss，要求打印出该二叉树的中序遍历序列。，要求打印出

25、该二叉树的中序遍历序列。4500 In_Bt(bitree *Bt)01 02 bitree *stack10; /* 定义栈数组定义栈数组 */03 int top=-1; /* 定义栈顶下标定义栈顶下标top并赋初值并赋初值-1 */04 bitree *ptr;05 ptr = Bt;/* ptr是工作指针是工作指针 */06 do07 08 while (ptr != NULL) /* 一直朝左子树深入下去一直朝左子树深入下去 */09 10 top+; /* 调整栈顶指针调整栈顶指针 */11 stacktop = ptr; /* ptr所指结点进栈所指结点进栈 */ 12 ptr

26、= ptr-lch;1314 if (Ss_top !=-1 )15 16 ptr = stacktop ; /* 栈顶元素赋值给栈顶元素赋值给ptr */17 top - ; /* 出栈出栈 */18 printf (%d , ptr-data); /* 访问该结点访问该结点 */19 ptr = ptr-rch; /* 进入右子树访问进入右子树访问 */20 21 while(ptr !=NULL)|(top!=-1);22 3、基于非递归遍历算法、基于非递归遍历算法3基于非递归二叉树中序遍历（基于非递归二叉树中序遍历（1-4趟）：趟）：463、基于非递归遍历算法、基于非递归遍历算法3基于

27、非递归二叉树中序遍历（基于非递归二叉树中序遍历（1-4趟）：趟）：473、基于非递归遍历算法、基于非递归遍历算法4后序遍历二叉树的非递归算法：后序遍历二叉树的非递归算法：已知二叉树已知二叉树Bt，顺序栈，顺序栈Ss，要求打印出该二叉树的后序遍历序列。，要求打印出该二叉树的后序遍历序列。48算法要点：算法要点：由于后序遍历是由于后序遍历是“左、右、根左、右、根”，因此在后序遍历过程中搜索，因此在后序遍历过程中搜索到某个结点时，不是马上访问它，而是将其作为相应子树根结点保到某个结点时，不是马上访问它，而是将其作为相应子树根结点保存在工作栈中，然后沿着其左子树继续深入直到存在工作栈中，然后沿着其左子

28、树继续深入直到“最左下最左下”结点。结点。完成对其左子树访问后，从工作栈顶元素中获得相应根结点信息，完成对其左子树访问后，从工作栈顶元素中获得相应根结点信息，但仍然不能马上进行访问，而是在工作栈中对其进行但仍然不能马上进行访问，而是在工作栈中对其进行第二次保存第二次保存，同时对其右子树进行遍历。在访问完右子树后，从工作栈中得到根同时对其右子树进行遍历。在访问完右子树后，从工作栈中得到根结点信息，由此实现对相应根结点访问。结点信息，由此实现对相应根结点访问。3、基于非递归遍历算法、基于非递归遍历算法4算法算法5-9 后序遍历二叉树的非递归算法后序遍历二叉树的非递归算法4900 Post_Bt(b

29、itree *Bt)01 02 bitree *Ss110;03 int Ss_top = -1; /* 定义信息栈并初始化栈顶指针定义信息栈并初始化栈顶指针 */04 bitree *ptr; /* 定义工作指针定义工作指针ptr */05 int Ss210,flag;06 int Ss2_top = -1;/* 定义标志栈并初始化栈顶指针定义标志栈并初始化栈顶指针 */07 ptr = Bt;3、基于非递归遍历算法、基于非递归遍历算法4算法算法5-9 后序遍历二叉树的非递归算法后序遍历二叉树的非递归算法5008 do09 10 while (ptr != NULL)11 12 Ss1_t

30、op+;/* 调整栈顶指针调整栈顶指针 */13 Ss1Ss1_top = ptr;/* ptr所指结点进栈所指结点进栈 */ 14 Ss2_top+;/* 结点第结点第1次进栈次进栈 */15 Ss2Ss2_top = 0;/* 设其标志为设其标志为0 */16 ptr = ptr-lch;/* 继续往左子树深入继续往左子树深入 */17 18 if (Ss1_top!=-1)19 20 flag = Ss2Ss2_top; /* 次数栈栈顶元素出栈次数栈栈顶元素出栈 */21 Ss2_top-;22 ptr = Ss1Ss1_top; /* 信息栈栈顶元素出栈信息栈栈顶元素出栈 */23

31、Ss1_top-;3、基于非递归遍历算法、基于非递归遍历算法4算法算法5-9 后序遍历二叉树的非递归算法后序遍历二叉树的非递归算法5124 if (flag = 0)/* 结点信息是第结点信息是第1次进栈次进栈 */25 26 Ss1_top+;27 Ss1Ss1_top = ptr;/* 该结点信息第该结点信息第2次进栈次进栈 */28 Ss2_top+;/* 设置相应标志为设置相应标志为1 */29 Ss2Ss2_top = 1;30 ptr = ptr-rch;/* 进入右子树处理进入右子树处理 */31 32 else/* 是第是第2次进栈次进栈 */33 34 printf (%d

32、, ptr-data);/* 访问结点访问结点 */35 ptr = NULL;36 37 38 while (ptr !=NULL)|(Ss1_top!=-1);39 3、基于非递归遍历算法、基于非递归遍历算法4基于非递归二叉树后序遍历第基于非递归二叉树后序遍历第1-3趟运算变化：趟运算变化：52步骤步骤 指针指针 ptr 访问结点访问结点 栈栈 stack1 栈栈stack2 说明说明 后序序列后序序列 初始初始 A A - - 初始化初始化 A? lch=B - - A 0 根结点根结点 A 进栈进栈 B? lch =null - - A,B 0,0 A 左子左子树根树根结点结点 B 进

33、进栈栈 B - - A 0 Ptr=null,栈非空栈非空,B 出出栈栈 B? rch=D A,B 0,1 flag=0,B 二次进栈二次进栈 D? lch =G - - A,B,D 0,1,0 B 右右子结点子结点 D 进栈进栈 G? lch =null A,B,D,G 0,1,0,0 D 左子结左子结点点 G 进栈进栈 - - A,B,D 0, 1,0 D 左子结点左子结点 G 出栈出栈 G? rch =null - - A,B,D,G 0,1,0,1 Gflag=0, G 二次进栈二次进栈 - - Ptr=null,G 出栈出栈 第第 1 趟趟 Null G G A,B,D 0,1,0

34、Gflag=1,访问访问 G G G - - A,B 0, 1 Ptr=null,D 出栈出栈 D? rch =null - - A,B,D 0, 1,1 Dflag=0，D 二次进栈二次进栈 - Prt=null, D 二次出栈二次出栈 第第 2 趟趟 null D A,B 0,1 Dflag=1，访问，访问 D G.D 3、基于非递归遍历算法、基于非递归遍历算法4基于非递归二叉树后序遍历第基于非递归二叉树后序遍历第4趟运算变化：趟运算变化：53步骤步骤 指针指针 ptr 访问结点访问结点 栈栈 stack1 栈栈stack2 说明说明 后序序列后序序列 - 0 Ptr=null,A出栈出栈

35、 D? rch=C - A 1 Aflag=0,A二次进栈二次进栈 C? lch=E A,C 1,0 C 进栈进栈 E? lch=null A,C,E 1,0,0 E 进栈进栈 A,C, 1,0 Ptr=null,E出栈出栈 - - A,C 1,0,1 Eflag=0,E二次进栈二次进栈 第第 4 趟趟 F? rch=null B AC 1.0 Ptr=null,栈不空栈不空,E 出出栈栈 3、基于非递归遍历算法、基于非递归遍历算法4基于非递归二叉树后序遍历第基于非递归二叉树后序遍历第5-7趟运算变化：趟运算变化：54步骤步骤 指针指针 ptr 访问结点访问结点 栈栈 stack1 栈栈sta

36、ck2 说明说明 后序序列后序序列 - - A 1,0 Ptr=null,C出栈出栈 C? rch=F - - A,C 1,1 Cflag=0,C二次进栈二次进栈 - - A,C ,F 1,1,0 F 进栈进栈 F? lch=null - - A,C 1,1 Ptr=null,F 出栈出栈 - - A,C,F 1,1,1 Fflag=0,F 二次进栈二次进栈 null - - A,C, 1,1 Ptr=null, F 二次出栈二次出栈 第第 5 趟趟 F F A,C, 1,1 Fflag=1，访问，访问 F G,D,B,E,F - A 1 Ptr=null,C出栈出栈 G,D,B,E,F 第第

37、 6 趟趟 null C Cflag=1，访问，访问 C G,D,B,E,F,C null - Ptr=null,A出栈出栈 第第 7 趟趟 null A Aflag=1，访问，访问 A G,D,B,E,F,C,A 第第 8 趟趟 null - Do 结束结束 上机：上机：1、用先序、用先序递归方法递归方法建立一棵二叉树；建立一棵二叉树；2、用中序、用中序非递归非递归方法遍历该二叉树。方法遍历该二叉树。555.4 线索二叉树线索二叉树5.4.1 线索与线索二叉树线索与线索二叉树 结合遍历方式特点使用这些空链域来存放相应前驱或后继信结合遍历方式特点使用这些空链域来存放相应前驱或后继信息即前驱或后

38、继的地址。息即前驱或后继的地址。 当前结点左孩子域非空时，保留原指针不变；当左孩子域为空时，当前结点左孩子域非空时，保留原指针不变；当左孩子域为空时，添加该结点在相应历序列中前驱结点地址。添加该结点在相应历序列中前驱结点地址。 当前结点右孩子域非空时，保留原指针不变；当右孩子域为空时，当前结点右孩子域非空时，保留原指针不变；当右孩子域为空时，添加该结点在相应遍历序列中后继结点地址。添加该结点在相应遍历序列中后继结点地址。565.4.1 线索与线索二叉树线索与线索二叉树2一个中序线索二叉树的例子：一个中序线索二叉树的例子：575.4.2 创建线索二叉树创建线索二叉树1、创建线索二叉树结点、创建线

39、索二叉树结点58算法算法5-10（线索二叉树结点结构）（线索二叉树结点结构） 01 struct ThreadNode /* 线索二叉树结点的定义线索二叉树结点的定义 */02 03 DataType info;04struct ThreadNode llink, rlink;05 int ltag, rtag;06 ;07 typedef struct ThreadNode ThreadTree; /* 线索二叉树类型的定义线索二叉树类型的定义 */5.4.2 创建线索二叉树创建线索二叉树22、二叉树的线索化、二叉树的线索化59在中序遍历过程中修改结点的左、右指针域，以保存当前访问结点的在中

40、序遍历过程中修改结点的左、右指针域，以保存当前访问结点的“前驱前驱”和和“后继后继”信息。遍历过程中，附设指针信息。遍历过程中，附设指针pre，并始终保持指针，并始终保持指针pre指向当前访问的、指针指向当前访问的、指针p所指结点的前驱。将给定二叉树扩充为线索二所指结点的前驱。将给定二叉树扩充为线索二叉树的过程称为二叉树的线索化，也就是线索二叉树的创建。叉树的过程称为二叉树的线索化，也就是线索二叉树的创建。线索化实际上就是在遍历过程中线索化实际上就是在遍历过程中在当前结点的空链域中添加前驱或后在当前结点的空链域中添加前驱或后继指针继指针。为了保留遍历过程中访问结点的前驱与后继关系，需要设置一个

41、。为了保留遍历过程中访问结点的前驱与后继关系，需要设置一个工作指针工作指针pre始终指向刚访问过的结点，也就是说，当指针始终指向刚访问过的结点，也就是说，当指针p指向当前访问指向当前访问结点时，结点时，pre就指向就指向p的前驱结点。的前驱结点。5.4.2 创建线索二叉树创建线索二叉树22、二叉树的线索化、二叉树的线索化60算法算法5-11 基于中序遍历的二叉树线索化基于中序遍历的二叉树线索化 00 ThreadTree *thread(ThreadTree *root)01 02 ThreadTree *stack10; /*栈元素的类型是栈元素的类型是ThreadTree指针指针, 深度大

42、于深度大于t的高度的高度 */03 int top=-1;04 ThreadTree *t,*p,*pr;05 pr=root; t=root-llink;06 if (t=NULL) 07 return root;08 p = t;5.4.2 创建线索二叉树创建线索二叉树22、二叉树的线索化、二叉树的线索化61算法算法5-11 基于中序遍历的二叉树线索化基于中序遍历的二叉树线索化 09 do10 11 while (p!=NULL)12 13 top=top+1;14 stacktop=p;15 p= p-llink;16 17 p = stacktop; 18 top=top-1;19 i

43、f (pr!=NULL)20 21 if (pr-rlink=NULL)22 23 pr-rlink = p; /*修改前驱结点的右指针修改前驱结点的右指针*/24 pr-rtag = 1; 25 5.4.2 创建线索二叉树创建线索二叉树22、二叉树的线索化、二叉树的线索化62算法算法5-11 基于中序遍历的二叉树线索化基于中序遍历的二叉树线索化 26 if (p-llink=NULL)27 28 p-llink = pr; 29 p-ltag = 1;30 31 32 pr = p;33 p = p-rlink;34 while ( top!=-1 | p!=NULL );35 pr-rli

44、nk=root;36 pr-rtag=1;37 return(root);38 5.4.2 创建线索二叉树创建线索二叉树33、线索二叉树遍历、线索二叉树遍历63以下以对中序线索化链表为例讨论基于线索的二叉树中序遍历算以下以对中序线索化链表为例讨论基于线索的二叉树中序遍历算法。此时，算法关键点有二：法。此时，算法关键点有二： 怎样获取中序遍历的首结点？怎样获取中序遍历的首结点？从根结点沿着左指针不断向左下搜寻，直到给定二叉树左子树的从根结点沿着左指针不断向左下搜寻，直到给定二叉树左子树的处于处于“最左下最左下”的结点，结点是的结点，结点是“最左下最左下”的含义是该结点再无左子的含义是该结点再无左

45、子结点，亦即该结点的左指针域为空。结点，亦即该结点的左指针域为空。 怎样获取在中序线索化链表中当前结点的后继结点？怎样获取在中序线索化链表中当前结点的后继结点？如果当前结点没有无右子树，则其后继结点即为其右指针域中后如果当前结点没有无右子树，则其后继结点即为其右指针域中后继线索所指结点；如果当前结点存在右子树，则从该右子树根结点开继线索所指结点；如果当前结点存在右子树，则从该右子树根结点开始沿左指针行进，直到右子树始沿左指针行进，直到右子树“最左下最左下”结点，此即为当前结点的后结点，此即为当前结点的后继。继。5.4.2 创建线索二叉树创建线索二叉树33、线索二叉树遍历、线索二叉树遍历264算

46、法算法5-12基于中序线索二叉树中序遍历算法基于中序线索二叉树中序遍历算法00 void thrInOrder(ThreadTree *root ) 01 02 ThreadTree *p;03 p = root-llink;04 if (p=NULL)05 return ;06 while ( p-llink!=NULL & p-ltag=0 )07 p = p-llink; /* 一直到一直到“最左下最左下” */08 while (p!=root) 09 10 printf(%d ,p-info);11 if ( p-rlink!=NULL & p-rtag=0 ) /* 右子树不是线索

47、时右子树不是线索时 */12 13 p = p-rlink;14 while (p-llink!=NULL&p-ltag=0)15 p = p-llink; /* 顺右子树的左子树一直向下顺右子树的左子树一直向下 */16 17 else18 p = p-rlink;19 20 5.5 Huffman编码编码5.5.1 等长与非等长编码等长与非等长编码 所谓编码（所谓编码（code），就是用一组不同的代码表示一个数据），就是用一组不同的代码表示一个数据对象集合中的每个元素的过程。对象集合中的每个元素的过程。1、两种基本编码类型、两种基本编码类型编码三要素：编码三要素： 唯一性：唯一性：发送方传

48、输编码字段，接收方解码后必须具有唯一性，发送方传输编码字段，接收方解码后必须具有唯一性，解码结果与发送原文保持相同；解码结果与发送原文保持相同； 简洁性：简洁性：发送的编码应该尽可能做到简洁短小，减少存储代价和发送的编码应该尽可能做到简洁短小，减少存储代价和提高传输效率。提高传输效率。 前缀性：前缀性：两个编码字节不使用特殊标记如标点符号进行分隔，一两个编码字节不使用特殊标记如标点符号进行分隔，一个编码字节不能是另一个编码字节的前缀，应具有个编码字节不能是另一个编码字节的前缀，应具有“前缀性前缀性”（Prefix Property）；）；655.5.1 等长与非等长编码等长与非等长编码22、最

49、优二叉树与、最优二叉树与Huffman树树二叉树路径长度二叉树路径长度：一棵二叉树的所有从根结点到每个叶结点路径：一棵二叉树的所有从根结点到每个叶结点路径长度之和称为该二叉树的长度之和称为该二叉树的“路径长度路径长度”。叶结点的权叶结点的权：赋给二叉树叶结点一个具有某种意义的实数，则称：赋给二叉树叶结点一个具有某种意义的实数，则称此数为该叶结点的此数为该叶结点的“权权”。二叉树带权路径长度二叉树带权路径长度：设二叉树具有：设二叉树具有n个带权的叶结点，则从根个带权的叶结点，则从根结点到各叶结点的路径长度与相应结点权值乘积之和称为该二结点到各叶结点的路径长度与相应结点权值乘积之和称为该二叉树的叉

50、树的“带权路径长度带权路径长度”，记为：，记为：66nk1WPL= wklk （wk是第是第k个叶结点权值，个叶结点权值， lk是第是第k个叶结点路径长度个叶结点路径长度）“Huffman树树”：由由带有权值的一组相同叶结点所构成二叉树当带有权值的一组相同叶结点所构成二叉树当中，称其中带权路径长度最小的二叉树为是中，称其中带权路径长度最小的二叉树为是“最优二叉树最优二叉树”。5.5.2 Huffman树构建思想树构建思想设有设有n个权值个权值w1、w2、w3、wn，则可按照下述步骤，则可按照下述步骤构造构造Huffman树：树：Step 1. 构造构造n棵只有一个根结点的二叉树森林棵只有一个根

51、结点的二叉树森林 HT = T1，T2，T3，Tn，它们分别以，它们分别以w1、w2、w3、wn作为权值。作为权值。Step 2. 在在HT集合中，选取权值最小和次小的两个根结点作为一集合中，选取权值最小和次小的两个根结点作为一棵新二叉树的左子树和右子树。新二叉树根结点权值是其左、右子棵新二叉树的左子树和右子树。新二叉树根结点权值是其左、右子树根结点权值之和；树根结点权值之和；Step 3. 在在HT集合中，删除已经取为左、右子树的原两棵二叉集合中，删除已经取为左、右子树的原两棵二叉（根）树，并将新构成二叉树添加到（根）树，并将新构成二叉树添加到HT中；中；Step 4. 重复重复Step 2

52、和和Step 2至至HT只剩下一棵二叉树，此即是所只剩下一棵二叉树，此即是所求求Huffman树。树。675.5.2 Huffman树构建思想树构建思想2构造具有四个分别带有权值构造具有四个分别带有权值1、3、5、7的的Huffman树如下图所示：树如下图所示：68练习：练习： 已知有已知有6个叶子，值分别为个叶子，值分别为A、B、C、D、E、F，它们的权值分别为它们的权值分别为4，9，1，3，2，1，试构造哈夫，试构造哈夫曼树（左权曼树（左权右权）。右权）。69练习：练习： 设有设有7个带权结点个带权结点A，B，C，D，E，F，G，其权值分别为，其权值分别为3，7，8，2，5，8，4，试以这

53、，试以这7带权结点为叶子结点，构造一带权结点为叶子结点，构造一棵哈夫曼树（左权棵哈夫曼树（左权右权）。右权）。705.5.3基于顺序存储基于顺序存储Huffman树构造树构造1、Huffman树结点结构树结点结构问题：若哈夫曼树有问题：若哈夫曼树有n0个叶子结点，则所有结点个叶子结点，则所有结点 个。个。712n0-1解：因为树中无度为解：因为树中无度为1的结点，的结点， 由二叉树的性质由二叉树的性质3知：知：n0=n2+1 所以：所以：n=n0+n2=n0+n0-1 =2n0-1u由于最终结果中结点个数已经确定，因此可采用顺序结构由于最终结果中结点个数已经确定，因此可采用顺序结构存储存放所建

54、存储存放所建Huffman树树5.5.3基于顺序存储基于顺序存储Huffman树构造树构造1、Huffman树结点结构树结点结构2问题：结点结构如何构造？问题：结点结构如何构造？7200 struct node01 02 int weight;03 int parent,lch,rch;04 ;05 struct node HtreeMAX;5.5.3基于顺序存储基于顺序存储Huffman树构造树构造22、Huffman树构造算法树构造算法问题：算法如何构造问题：算法如何构造Huffman树？树？73原理：原理：找两找两无双亲无双亲且且权值最小权值最小结点合并，生成新结点，填写结点合并，生成新

55、结点，填写相关信息（相关信息（两结点双亲，新结点权值，新结点左、右孩两结点双亲，新结点权值，新结点左、右孩子子）。）。算法算法5-13 基于顺序存储基于顺序存储Huffman树构造算法树构造算法 00 creat_huff(struct node Htree)01 02 int i,j,min1,min11,min2,min22;03 printf(nInput the count of leaves(10):);04 scanf(%d,&n); /* 读取叶子结点个数读取叶子结点个数n */05 for (i=0;i2*n-1;i+) /* 数组数组Htree初始化初始化 */06 07 H

56、treei.parent=-1;08 Htreei.lch=-1;09 Htreei.rch=-1;10 11 printf(nInput the leavess weight:);12 for (i=0;in;i+) /* 读取各个叶子的权值并赋值到读取各个叶子的权值并赋值到Htree数组数组 */13 scanf(%d,&Htreei.weight);74算法算法5-13 基于顺序存储基于顺序存储Huffman树构造算法树构造算法2 14 for (i=n;i2*n-1;i+) /* 控制控制n-1次二叉树的合并次二叉树的合并 */15 16 min2=min1=MAX; /* min1、

57、min2记录当前最小、次小权值记录当前最小、次小权值 */17 min11=min22=0; /* min11、min22记录当前最小、次小权值记录当前最小、次小权值结点位置结点位置 */18 for (j=0;ji;j+) /* 在在j的范围内，找最小、次小结点的范围内，找最小、次小结点 */19 20 if (Htreej.parent=-1)21 if (Htreej.weightmin1) /* 如当前权值比最小结点还小如当前权值比最小结点还小 */22 23 min22=min11;24 min2=min1; /* 最小结点信息赋给次小最小结点信息赋给次小 */25 min11=j;

58、26 min1=Htreej.weight; /* 当前权值信息赋给最小当前权值信息赋给最小 */27 28 else75算法算法5-13 基于顺序存储基于顺序存储Huffman树构造算法树构造算法3 29 if (Htreej.weightmin2) /* 如当前权值比次小结点小如当前权值比次小结点小 */30 31 min22=j;32 min2=Htreej.weight; /* 当前权值信息赋给次小当前权值信息赋给次小 */33 34 35 Htreemin11.parent=i; /* 设置最小权值结点的设置最小权值结点的parent域域 */36 Htreemin22.parent

59、=i; /* 设置次小权值结点的设置次小权值结点的parent域域 */37 Htreei.weight=Htreemin11.weight+Htreemin22.weight; /* 设置新结点的权值域设置新结点的权值域 */38 Htreei.lch=min11; /* 设置新结点的设置新结点的lch域为最小结点域为最小结点 */39 Htreei.rch=min22; /* 设置新结点的设置新结点的rch域为次小结点域为次小结点 */40 41 Htree2*n-2.parent=-1; /* 最后一个结点为根结点，最后一个结点为根结点，parent域为域为-1 */42 ;765.5.

60、3基于顺序存储基于顺序存储Huffman树构造树构造33、Huffman树算法分析树算法分析77设有叶结点相应权值分别为设有叶结点相应权值分别为1，3，5，7。按照算法构建。按照算法构建Huffman树过程如树过程如下下图所示图所示： weight lch rch parent Htree0 1 -1 -1 -1 Htree1 3 -1 -1 -1 Htree2 5 -1 -1 -1 Htree3 7 -1 -1 -1 Htree4 -1 -1 -1 Htree5 -1 -1 -1 Htree6 -1 -1 -1 （a）初始时）初始时 （b）合并一次后）合并一次后 weight lch rch