《数据结构：第六章 树和二叉树》由会员分享，可在线阅读，更多相关《数据结构：第六章 树和二叉树（126页珍藏版）》请在金锄头文库上搜索。
1、1第第6章章 树和二叉树树和二叉树 6.1 树的定义和基本术语树的定义和基本术语 6.2 二叉树二叉树 6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树 6.4 树和森林树和森林 6.6 赫夫曼树及其应用赫夫曼树及其应用本章要点l深入掌握树的相关概念、树的表示和树的性质深入掌握树的相关概念、树的表示和树的性质l深入掌握二叉树的相关概念、二叉树的性质和二叉树的存深入掌握二叉树的相关概念、二叉树的性质和二叉树的存储结构储结构l深入掌握二叉树运算的实现过程深入掌握二叉树运算的实现过程l掌握树和森林的相互转换过程掌握树和森林的相互转换过程l深入掌握赫夫曼树的构造过程和赫夫曼编码深入掌握赫夫曼树的构
2、造过程和赫夫曼编码l灵活应用二叉树的特点解决复杂的应用问题灵活应用二叉树的特点解决复杂的应用问题难点：赫夫曼树的构造过程和赫夫曼编码难点：赫夫曼树的构造过程和赫夫曼编码重点：重点： 1、树和二叉树的相关概念、性质、树和二叉树的相关概念、性质 2、树和二叉树的存储结构及其基本运算的实现、树和二叉树的存储结构及其基本运算的实现 3、赫夫曼树的构造过程和赫夫曼编码、赫夫曼树的构造过程和赫夫曼编码本章要点：本章要点：236.1 6.1 树的定义和基本术语树的定义和基本术语一一. . 树的抽象数据类型定义树的抽象数据类型定义二二. . 树的基本术语树的基本术语46.1 6.1 树的定义和基本术语树的定义
3、和基本术语一一. . 树的抽象数据类型定义树的抽象数据类型定义1. 1. 树的定义树的定义树的定义树的定义 树是由树是由树是由树是由n n ( (n n 0) 0)个结点组成的有限集合。个结点组成的有限集合。个结点组成的有限集合。个结点组成的有限集合。 如果如果如果如果n n = 0 = 0，称为，称为，称为，称为空树空树空树空树； 如果如果如果如果n n 0 0，则，则，则，则: : 有且只有一个特定的称之为有且只有一个特定的称之为有且只有一个特定的称之为有且只有一个特定的称之为根根根根(root)(root)的结点，它的结点，它的结点，它的结点，它只有后继，但没有前驱；只有后继，但没有前驱
4、；只有后继，但没有前驱；只有后继，但没有前驱； 除根以外的其它结点划分为除根以外的其它结点划分为除根以外的其它结点划分为除根以外的其它结点划分为mm ( (mm 0) 0)个互不相个互不相个互不相个互不相交的有限集合交的有限集合交的有限集合交的有限集合T T1 1, , T T2 2, , , , T Tmm，每个集合本身又是一，每个集合本身又是一，每个集合本身又是一，每个集合本身又是一棵树，并且称之为根的棵树，并且称之为根的棵树，并且称之为根的棵树，并且称之为根的子树子树子树子树(SubTree)(SubTree)。每棵子树。每棵子树。每棵子树。每棵子树的根结点有且仅有一个的根结点有且仅有一
5、个的根结点有且仅有一个的根结点有且仅有一个直接直接直接直接前驱，但可以有前驱，但可以有前驱，但可以有前驱，但可以有0 0个或个或个或个或多个后继。多个后继。多个后继。多个后继。56.1 6.1 树的定义和基本术语树的定义和基本术语一一. . 树的抽象数据类型定义树的抽象数据类型定义2. 2. 树的表示方法树的表示方法树的表示方法树的表示方法 图图6.1 树的示例树的示例 66.1 6.1 树的定义和基本术语树的定义和基本术语一一. . 树的抽象数据类型定义树的抽象数据类型定义2. 2. 树的表示方法树的表示方法树的表示方法树的表示方法 (a)嵌套集合表示法 (b)广义表表示法 (c)凹入表示法
6、76.1 6.1 树的定义和基本术语树的定义和基本术语二二. . 树的基本术语树的基本术语结点结点: :结点的度结点的度: :树的度树的度: :叶子结点叶子结点: :分支结点分支结点: :数据元素数据元素+ +若干指向子树的分支若干指向子树的分支结点拥有的分支个数结点拥有的分支个数树中所有结点的度的最大值树中所有结点的度的最大值度为零的结点度为零的结点度大于零的结点度大于零的结点DHIJM86.1 6.1 树的定义和基本术语树的定义和基本术语二二. . 树的基本术语树的基本术语( (从根到结点的从根到结点的) )路径：路径：孩子孩子结点结点、双亲双亲结点结点、兄弟兄弟结点结点、堂兄弟堂兄弟祖先
7、祖先结点结点、子孙子孙结点结点结点的层次结点的层次: : 由从由从根根到该结点所经分到该结点所经分支和结点构成。支和结点构成。假设根结点的层次为假设根结点的层次为1,1,第第l 层的结点层的结点的子树根结点的层次为的子树根结点的层次为l+1ABCDEFGHIJMKL树的深度：树的深度： 树中叶子结点所在的最大层次树中叶子结点所在的最大层次96.1 6.1 树的定义和基本术语树的定义和基本术语二二. . 树的基本术语树的基本术语有序树有序树：是指树中结点的各子树是指树中结点的各子树从左至右是有次序从左至右是有次序的（不能互换），的（不能互换），否则称为否则称为无序树无序树。森林森林：是是m m（
8、m0m0）棵互不相交的树的集合。）棵互不相交的树的集合。106.2 6.2 二叉树二叉树二二. . 二叉树的操作二叉树的操作三三. . 二叉树的性质二叉树的性质四四. . 二叉树的存储结构二叉树的存储结构一一. . 二叉树的定义二叉树的定义116.2 6.2 二叉树二叉树一一. . 二叉树的定义二叉树的定义 一棵二叉树是结点的一个有限集合，该一棵二叉树是结点的一个有限集合，该集合集合（1 1）或者为空，）或者为空，（2 2）或者是由一个根结点组成）或者是由一个根结点组成（3 3）或者是由一个根结点加上两棵分别称为）或者是由一个根结点加上两棵分别称为左子树左子树和和右子树右子树的、的、互不相交的
9、互不相交的二叉树组成。二叉树组成。126.2 6.2 二叉树二叉树一一. . 二叉树的定义二叉树的定义ABCDEFGHK根结点根结点左子树左子树右子树右子树特点：特点：1 1）每个结点的度）每个结点的度2 2；2 2）是有序树）是有序树6.2 6.2 二叉树二叉树一一. . 二叉树的定义二叉树的定义图图6.3 二叉树的五种不同形态二叉树的五种不同形态136.2 6.2 二叉树二叉树二二. . 二叉树的操作二叉树的操作14(1)InitBiTree(&T)(1)InitBiTree(&T)(1)InitBiTree(&T)(1)InitBiTree(&T) (2)DestroyBiTree(&T
10、) (2)DestroyBiTree(&T) (2)DestroyBiTree(&T) (2)DestroyBiTree(&T)(3)CreateBiTree(&T(3)CreateBiTree(&T(3)CreateBiTree(&T(3)CreateBiTree(&T，definition)definition)definition)definition)(4)ClearBiTree(&T) (5)BiTreeEmpty(T)(4)ClearBiTree(&T) (5)BiTreeEmpty(T)(4)ClearBiTree(&T) (5)BiTreeEmpty(T)(4)ClearBiT
11、ree(&T) (5)BiTreeEmpty(T)(6)BiTreeDepth(T) (7)(6)BiTreeDepth(T) (7)(6)BiTreeDepth(T) (7)(6)BiTreeDepth(T) (7)Root(t) Root(t) Root(t) Root(t) (8)Value(T,e) (9)Assign(T,&e,value)(8)Value(T,e) (9)Assign(T,&e,value)(8)Value(T,e) (9)Assign(T,&e,value)(8)Value(T,e) (9)Assign(T,&e,value)(10)Parent(T,e) (11
12、)LeftChild(T,e) (10)Parent(T,e) (11)LeftChild(T,e) (10)Parent(T,e) (11)LeftChild(T,e) (10)Parent(T,e) (11)LeftChild(T,e) (12)RightChild(T,e) (13)InsertChild(T,p,LR,c) (12)RightChild(T,e) (13)InsertChild(T,p,LR,c) (12)RightChild(T,e) (13)InsertChild(T,p,LR,c) (12)RightChild(T,e) (13)InsertChild(T,p,L
13、R,c) (14)DeleteChild(T,p,LR) (14)DeleteChild(T,p,LR) (14)DeleteChild(T,p,LR) (14)DeleteChild(T,p,LR) (15)PreOrderTraverse(T,Visit() (15)PreOrderTraverse(T,Visit() (15)PreOrderTraverse(T,Visit() (15)PreOrderTraverse(T,Visit() (16)InOrderTraverse(T,Visit() (16)InOrderTraverse(T,Visit() (16)InOrderTrav
14、erse(T,Visit() (16)InOrderTraverse(T,Visit() (17)PostOrderTraverse(T,Visit()(17)PostOrderTraverse(T,Visit()(17)PostOrderTraverse(T,Visit()(17)PostOrderTraverse(T,Visit()6.2 6.2 二叉树二叉树三三. . 二叉树的性质二叉树的性质15性质性质1 若二叉树的层次从若二叉树的层次从1开始开始, 则在二叉树的则在二叉树的第第 i 层最多有层最多有 2i-1个结点。个结点。(i 1) 证明用数学归纳法证明用数学归纳法性质性质2 深度
15、为深度为k的二叉树最多有的二叉树最多有 2k-1个结点。个结点。(k 1) 证明用求等比级数前证明用求等比级数前k项和的公式项和的公式6.2 6.2 二叉树二叉树三三. . 二叉树的性质二叉树的性质16性质性质3 对任何一棵二叉树对任何一棵二叉树, 如果其叶结点个数为如果其叶结点个数为 n0, 度为度为2的非叶结点个数为的非叶结点个数为 n2, 则有则有 n0n21证明：证明：证明：证明： 若设度为若设度为若设度为若设度为1 1的结点有的结点有的结点有的结点有n n1个，总结点个数为个，总结点个数为个，总结点个数为个，总结点个数为n n，总边，总边，总边，总边数为数为数为数为e e，则根据二叉
16、树的定义，则根据二叉树的定义，则根据二叉树的定义，则根据二叉树的定义， n n = = n n0 0 + + n n1 1 + + n n2 2 e e = 2 = 2n n2 2 + + n n1 1 = = n n 1 1 因此，有因此，有因此，有因此，有 2 2n n2 2 + + n n1 1 = = n n0 0 + + n n1 1 + + n n2 2 1 1 n n2 2 = = n n0 0 - 1 - 1 n n0 0 = = n n2 2 + 1 + 1 6.2 6.2 二叉树二叉树三三. . 二叉树的性质二叉树的性质17定义定义1 满二叉树满二叉树(Full Binar
17、y Tree) 一棵深度为一棵深度为k且有且有2k -1个结点的二叉树称为个结点的二叉树称为满二叉树。满二叉树。如图如图6.4（a）6.2 6.2 二叉树二叉树三三. . 二叉树的性质二叉树的性质18定义定义2 完全二叉树完全二叉树(Complete Binary Tree) 深度为深度为k，有，有n个结点的二叉树，当且仅当个结点的二叉树，当且仅当其每一个结点都与深度为其每一个结点都与深度为k的满二叉树中编号从的满二叉树中编号从1至至n的结点一一对应时，称之为完全二叉树。的结点一一对应时，称之为完全二叉树。 如图如图6.4（b） 或者：若设二叉树的深度为或者：若设二叉树的深度为h，则共有，则共
18、有h层。层。除第除第h层外，其它各层层外，其它各层(0 h-1)的结点数都达到的结点数都达到最大个数，第最大个数，第h层从右向左连续缺若干结点。层从右向左连续缺若干结点。6.2 6.2 二叉树二叉树三三. . 二叉树的性质二叉树的性质19完全二叉树的特点是：完全二叉树的特点是：完全二叉树的特点是：完全二叉树的特点是：1 1）只只只只允允允允许许许许最最最最后后后后一一一一层层层层有有有有空空空空缺缺缺缺结结结结点点点点且且且且空空空空缺缺缺缺在在在在右右右右边边边边，即即即即叶子结点只能在层次最大的两层上出现；叶子结点只能在层次最大的两层上出现；叶子结点只能在层次最大的两层上出现；叶子结点只能
19、在层次最大的两层上出现；2 2）对任一结点，如果其右子树的深度为）对任一结点，如果其右子树的深度为）对任一结点，如果其右子树的深度为）对任一结点，如果其右子树的深度为l l，则其左，则其左，则其左，则其左子树的深度必为子树的深度必为子树的深度必为子树的深度必为l l或或或或l+1l+1。 6.2 6.2 二叉树二叉树三三. . 二叉树的性质二叉树的性质20性质性质4 具有具有n个结点的完全二叉树的深度个结点的完全二叉树的深度为为 log2n + +1证明：证明：设完全二叉树的深度为设完全二叉树的深度为k，则有，则有 2k-1 - - 1 n 2k - - 1 2k-1 n 2k 取对数取对数
20、k-1 log2n 1, 1, 则则则则 i i 的双亲为的双亲为的双亲为的双亲为 i i /2/2 n n 若若若若2*2*i i n n, , 则则则则 i i无左孩子；否则其左孩子结点为无左孩子；否则其左孩子结点为无左孩子；否则其左孩子结点为无左孩子；否则其左孩子结点为2 2i i， 若若若若2*2*i i+1 +1 n n, , 则则则则 i i无右孩子，否则其右孩子结点为无右孩子，否则其右孩子结点为无右孩子，否则其右孩子结点为无右孩子，否则其右孩子结点为2 2i i+1+1，线性结构线性结构树形结构树形结构第一个数据元素第一个数据元素 ( (无前驱无前驱) ) 根结点根结点 ( (无
21、前驱无前驱) )最后一个数据元素最后一个数据元素 ( (无后继无后继) )多个叶子结点多个叶子结点 ( (无后继无后继) ) 其它数据元素其它数据元素( (一个前驱、一个后继一个前驱、一个后继) ) 其它数据元素其它数据元素( (一个前驱、多个后继一个前驱、多个后继) )双亲在同一层的结点双亲在同一层的结点A AB BC CD DE EF FG GH HI IJ JK KL LM M结点结点A A的度：的度：结点结点B B的度：的度：结点结点M M的度：的度：叶子：叶子：结点结点A A的孩子：的孩子：结点结点B B的孩子：的孩子：结点结点I I的双亲：的双亲：结点结点L L的双亲：的双亲：结点
22、结点B B，C C，D D为兄弟为兄弟结点结点K K，L L为兄弟为兄弟树的度：树的度：结点结点A A的层次：的层次：结点结点M M的层次：的层次：树的深度：树的深度：结点结点F F，G G为堂兄弟为堂兄弟结点结点A A是结点是结点F F，G G的祖先的祖先结点结点B B的子孙：的子孙：3 32 20 0B B，C C，D D E E，F F3 3K K，L L，F F，G G，M M，I I ，J JD D E E1 14 4例例例例E E，K K，L L，F F4 4 4 4思考思考：具有：具有3 3个结点的二叉树有多少种个结点的二叉树有多少种形态形态？例：例：11112 23 34 45
23、 56 67 78 89 9101012121 1 i=6 i=6 其双亲为其双亲为|i/2|= 3|i/2|= 3；其左孩子为；其左孩子为2*i=122*i=12; ;i=1 i=1 是树的根是树的根, ,无双亲无双亲; ;其左孩子为其左孩子为2*i=22*i=2, ,右孩子右孩子为为2*i+1=32*i+1=3 . .2*i=1812 2*i+1=19122*i=1812 2*i+1=1912 其无左、右孩子。其无左、右孩子。2*i+1=13122*i+1=1312 其无右孩子。其无右孩子。i=9 i=9 其双亲为其双亲为|i/2|= 4|i/2|= 4 ；6.2 6.2 二叉树二叉树四、
24、二叉树的存储结构四、二叉树的存储结构26顺序存储顺序存储链式存储链式存储6.2 6.2 二叉树二叉树四、二叉树的存储结构四、二叉树的存储结构271. 顺序存储结构（数组表示）顺序存储结构（数组表示） 顺序存储二叉树的具体方法是：在一棵具有顺序存储二叉树的具体方法是：在一棵具有n n个个结点的完全二叉树中，结点的完全二叉树中，从根结点开始编号为从根结点开始编号为1 1，自，自上到下，每层自左至右地给所有结点编号上到下，每层自左至右地给所有结点编号，这样，这样可以得到一个反映整个二叉树结构的线性序列可以得到一个反映整个二叉树结构的线性序列；然后将完全二叉树上编号为然后将完全二叉树上编号为i i的结
25、点依次存储在一的结点依次存储在一维数组中下标为维数组中下标为i-1i-1的元素中。的元素中。 6.2 6.2 二叉树二叉树四、二叉树的存储结构四、二叉树的存储结构281. 顺序存储结构（数组表示）顺序存储结构（数组表示）#define MAX_TREE_SIZE 100typedef TElemType SqBiTreeMAX_TREE_SIZE;SqBiTree bt;二叉树的顺序存储表示二叉树的顺序存储表示6.2 6.2 二叉树二叉树四、二叉树的存储结构四、二叉树的存储结构291. 顺序存储结构（数组表示）顺序存储结构（数组表示）完全二叉树的数组表示完全二叉树的数组表示 一般二叉树的数组表
26、示一般二叉树的数组表示6.2 6.2 二叉树二叉树四、二叉树的存储结构四、二叉树的存储结构301. 顺序存储结构（数组表示）顺序存储结构（数组表示）n由于一般二叉树必须仿照由于一般二叉树必须仿照完全二叉树那样存储，可能完全二叉树那样存储，可能会浪费很多存储空间，单支会浪费很多存储空间，单支树就是一个极端情况。树就是一个极端情况。n一棵深度为一棵深度为k k且只有且只有k k个结个结点的单支树需要长度为点的单支树需要长度为2 2K K-1-1的一维数组的一维数组单支树单支树6.2 6.2 二叉树二叉树四、二叉树的存储结构四、二叉树的存储结构312. 链式存储结构链式存储结构 链式存储是使用链式存
27、储是使用链表链表来存储二叉树中来存储二叉树中的数据元素，链表中的一个结点相应地存的数据元素，链表中的一个结点相应地存储二叉树中的一个结点。储二叉树中的一个结点。 常见的二叉树的链式存储结构有常见的二叉树的链式存储结构有两种两种：二叉链表二叉链表和和三叉链表三叉链表。6.2 6.2 二叉树二叉树四、二叉树的存储结构四、二叉树的存储结构322. 链式存储结构链式存储结构二叉链表二叉链表是指链表中的每个结点包含是指链表中的每个结点包含两个指两个指针域针域和和一个数据域一个数据域，分别用来存储指向二叉，分别用来存储指向二叉树中结点的左右孩子的指针及结点信息。树中结点的左右孩子的指针及结点信息。三叉链表
28、三叉链表是指链表中的每个结点包含是指链表中的每个结点包含三个指三个指针域针域和和一个数据域一个数据域，相比二叉链表多出的一，相比二叉链表多出的一个指针域则用来指向该结点的双亲结点。个指针域则用来指向该结点的双亲结点。6.2 6.2 二叉树二叉树四、二叉树的存储结构四、二叉树的存储结构332. 链式存储结构链式存储结构6.2 6.2 二叉树二叉树四、二叉树的存储结构四、二叉树的存储结构342.链式存储结构链式存储结构typedef struct BiTNodeTElemType data;Struct BiTNode *lchild,*rchild;BiTNode, *BiTree;二叉链表存储
29、表示二叉链表存储表示6.2 6.2 二叉树二叉树四、二叉树的存储结构四、二叉树的存储结构352. 链式存储结构链式存储结构图图6.8二叉树链表表示的示例二叉树链表表示的示例6.3 6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树36遍历二叉树遍历二叉树线索二叉树线索二叉树 “遍历遍历遍历遍历”是任何类型均有的操作，对线性结构是任何类型均有的操作，对线性结构而言，只有一条搜索路径而言，只有一条搜索路径( (因为每个结点均只有一因为每个结点均只有一个后继个后继) )，故不需要另加讨论。而二叉树是非线性，故不需要另加讨论。而二叉树是非线性结构，结构，每个结点有两个后继，则存在如何遍历即按每个结点
30、有两个后继，则存在如何遍历即按什么样的搜索路径遍历的问题。什么样的搜索路径遍历的问题。 遍历：遍历：顺着某一条搜索路径顺着某一条搜索路径巡访巡访二叉树中的结二叉树中的结点，使得每个结点点，使得每个结点均被访问一次均被访问一次，而且，而且仅被访问一仅被访问一次次。即找一个完整而有规律的走法，得到树中所有即找一个完整而有规律的走法，得到树中所有即找一个完整而有规律的走法，得到树中所有即找一个完整而有规律的走法，得到树中所有结点的一个线性排列。结点的一个线性排列。结点的一个线性排列。结点的一个线性排列。 “访问访问访问访问 ”的含义可以很广，的含义可以很广， 如：输出结点的如：输出结点的信息等。信息
31、等。6.3 6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树一、遍历二叉树一、遍历二叉树6.3 6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树一、遍历二叉树一、遍历二叉树38遍历的结果遍历的结果：产生一个关于结点的：产生一个关于结点的线性序列线性序列。设访问设访问根结点根结点记作记作 D D，遍历根的遍历根的左子树左子树记作记作 L L遍历根的遍历根的右子树右子树记作记作 R R则可能的遍历次序有则可能的遍历次序有：先序先序 DLR DLR， 逆先序逆先序DRLDRL中序中序 LDR LDR， 逆中序逆中序RDL RDL 后序后序 LRD LRD， 逆后序逆后序RLDRLD6.3 6
32、.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树一、遍历二叉树一、遍历二叉树39先序遍历先序遍历 (Preorder Traversal)(Preorder Traversal)先序遍历二叉树算法的框架是先序遍历二叉树算法的框架是n若二叉树为空，则空操作；若二叉树为空，则空操作；n否则否则访问根结点访问根结点 (D)(D)；先序遍历左子树先序遍历左子树 (L)(L)；先序遍历右子树先序遍历右子树 (R)(R)。A AD DB BC CD D L L R RA AD D L R L R D D L L R R B B D D C CD D L R L R先序遍历序列：先序遍历序列：A B D
33、CA B D C先序遍历先序遍历: :6.3 6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树一、遍历二叉树一、遍历二叉树41中序遍历中序遍历 (Inorder Traversal)(Inorder Traversal)中序遍历二叉树算法的框架是中序遍历二叉树算法的框架是n若二叉树为空，则空操作；若二叉树为空，则空操作；n否则否则中序遍历左子树中序遍历左子树 (L)(L)；访问根结点访问根结点 (D)(D)；中序遍历右子树中序遍历右子树 (R)(R)。A AD DB BC CL L D D R RB B L L D RD RL L D RD R A A D D C CL L D R D R
34、中序遍历序列：中序遍历序列：B D A CB D A C中序遍历中序遍历: :6.3 6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树一、遍历二叉树一、遍历二叉树43后序遍历后序遍历后序遍历后序遍历 (Postorder Traversal)(Postorder Traversal)(Postorder Traversal)(Postorder Traversal)后序遍历二叉树算法的框架是后序遍历二叉树算法的框架是n若二叉树为空，则空操作；若二叉树为空，则空操作；n否则否则后序遍历左子树后序遍历左子树 (L)(L)；后序遍历右子树后序遍历右子树 (R)(R)；访问根结点访问根结点 (D)
35、(D)。A AD DB BC C L L R R D DL R DL R D L L R DR D A A D D C CL L R DR D后序遍历序列：后序遍历序列： D B C AD B C A后序遍历后序遍历: :B BA AB BC CD DE EF FG GH HK K分分 析析：先序序列：先序序列：中序序列：中序序列：后序序列：后序序列：A A B C DB C D E F G H KE F G H KB D CB D C A A E H G K FE H G K FD C BD C B H K G F E H K G F E A A- -+ +/ /a a* *b b- -e
36、ef fc cd d先序遍历：先序遍历：中序遍历：中序遍历：后序遍历：后序遍历：- -+ +a a * * b b - - c c d d / /e e f f- -+ +a a* *b b- -c cd d/ /e ef f- -+ +a a* *b b- -c c d d/ /e e f f47 由二叉树的先序序列和中序序列可唯一地确定由二叉树的先序序列和中序序列可唯一地确定一棵二叉树。一棵二叉树。例例, 先序序列先序序列 ABHFDECKG 和和中序序列中序序列 HBDFAEKCG , 构造二叉树过构造二叉树过程如下：程如下：6.3 6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树一
37、、遍历二叉树一、遍历二叉树48思考：思考：已知二叉树的先序序列和后序序列，问已知二叉树的先序序列和后序序列，问能否唯一确定这棵二叉树？能否唯一确定这棵二叉树？遍历遍历算法的递归描述算法的递归描述void PreOrdervoid PreOrderTraverseTraverse ( (BiTree T, BiTree T, void void ( *( *V Visit)(TElemTypeisit)(TElemType e)e) ) / / 先序遍历二叉树先序遍历二叉树 if (T) if (T) Visit(T-data) Visit(T-data) ; ; / / 访问结点访问结点 Pr
38、eOrder( PreOrder(T-lchild, VisitT-lchild, Visit); ); / / 遍历左子树遍历左子树 PreOrder( PreOrder(T-rchild, VisitT-rchild, Visit););/ / 遍历右子树遍历右子树 void void p pre(BiTree t)re(BiTree t) if (t!=NULL) if (t!=NULL) printf (%dt,t-data); printf (%dt,t-data); pre(t-lchild); pre(t-lchild); pre(t-rchild); pre(t-rchild)
39、; 主程序主程序p pre( T )re( T )返回返回返回返回pre(T R);pre(T R);返回返回返回返回pre(T R);pre(T R);A AC CB BD DT TB Bprintf(B);printf(B);pre(T pre(T L);L);B BT TA Aprintf(A);printf(A);pre(T L);pre(T L);A AT TD Dprintf(D);printf(D);pre(T L);pre(T L);D DT TC Cprintf(C);printf(C);pre(T L);pre(T L);C C返回返回T T 左是空返回左是空返回pre(T
40、 R);pre(T R);T T 左是空返回左是空返回T T 右是空返回右是空返回T T 左是空返回左是空返回T T 右是空返回右是空返回pre(T R);pre(T R);先序序列：先序序列：A B D CA B D CA B D CA B D C递归算法的执行过程递归算法的执行过程递归算法的执行过程递归算法的执行过程T T T T6.3 6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树一、遍历二叉树一、遍历二叉树51遍历二叉树的非递归算法遍历二叉树的非递归算法中序遍历中序遍历在遍历左子树之前，先把根结点入栈，当在遍历左子树之前，先把根结点入栈，当左子树遍历结束后，从栈中弹出、访问，再左
41、子树遍历结束后，从栈中弹出、访问，再遍历右子树遍历右子树52中序遍历的非递归算法中序遍历的非递归算法Status InOrderTraverse(BiTree T, Status (*Visit)(TElemType e) InitStack(S);/根指针进栈根指针进栈 Push(S, T); while (!StackEmpty(S) while (GetTop(S, p) & p) Push(S, p-lchild); /向左走到尽头向左走到尽头 Pop(S, p);/空指针退栈空指针退栈 if (!StackEmpty(S) /访问结点，向右一步访问结点，向右一步 Pop(S, p);
42、 if (!Visit(p-data) return ERROR; Push(S, p-rchild); return OK;6.3 6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树6.3 6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树53先序建立二叉树的递归算法先序建立二叉树的递归算法（算法（算法6.46.4）Status CreateBiTree(BiTree &T) char ch;scanf(%c,&ch); if (ch= ) T=NULL; else if (!(T=(BiTNode*)malloc(sizeof(BiTNode) exit(OVERFLOW); T-da
43、ta = ch; CreateBiTree(T-lchild); CreateBiTree(T-rchild);return OK;6.3 6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树二、线索二叉树（穿线树、线索树）二、线索二叉树（穿线树、线索树） (Threaded Binary Tree)(Threaded Binary Tree)54 1、问题的提出问题的提出2、线索二叉树定义、线索二叉树定义3、在线索二叉树上找前驱和后继的规律、在线索二叉树上找前驱和后继的规律4、如何建立中序线索二叉树？、如何建立中序线索二叉树？5、线索二叉树的遍历算法、线索二叉树的遍历算法二、二、 线索二叉树
44、线索二叉树55 如何找二叉树上结点的前驱和后继？如何找二叉树上结点的前驱和后继？遍历二叉树的结果是，遍历二叉树的结果是， 求得结点的一个线性序列。求得结点的一个线性序列。ABCDEFGHK例如:先序序列先序序列: : A B C D E F G H K中序序列中序序列: : B D C A H G K F E后序序列后序序列: : D C B H K G F E A56 ADEBCF root先序遍历：先序遍历： A B C D E F 利用二叉链表结点中的利用二叉链表结点中的n+1n+1个空链域：个空链域： 如何在二叉树上记录结点的前驱和后继信息？如何在二叉树上记录结点的前驱和后继信息？57
45、 lchild data rchildltagrtagNULLABDCEF010000111111增加标志域增加标志域如何区别是孩子指针还是前驱或后继指针? 0link1thread6.3 6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树二、线索二叉树（穿线树、线索树）二、线索二叉树（穿线树、线索树）58 1、问题的提出、问题的提出2、线索二叉树定义线索二叉树定义3、在线索二叉树上找前驱和后继的规律、在线索二叉树上找前驱和后继的规律4、如何建立中序线索二叉树？、如何建立中序线索二叉树？5、线索二叉树的遍历算法、线索二叉树的遍历算法6.3 6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树
46、二、线索二叉树（穿线树、线索树）二、线索二叉树（穿线树、线索树）59 线索：指向该线性序列中的线索：指向该线性序列中的线索：指向该线性序列中的线索：指向该线性序列中的“ “前驱前驱前驱前驱” ”和和和和“ “后继后继后继后继” ” 的指针。的指针。的指针。的指针。线索链表：包含线索链表：包含线索链表：包含线索链表：包含 “ “线索线索线索线索” ” 的存储结构。的存储结构。的存储结构。的存储结构。 线索二叉树：加上线索的二叉树。线索二叉树：加上线索的二叉树。线索二叉树：加上线索的二叉树。线索二叉树：加上线索的二叉树。lchild data rchildltagrtag6.3 6.3 遍历二叉树
47、和线索二叉树遍历二叉树和线索二叉树二、线索二叉树（穿线树、线索树）二、线索二叉树（穿线树、线索树）60 线索二叉树线索二叉树线索二叉树线索二叉树，即在一般二叉树的基础上，对每个，即在一般二叉树的基础上，对每个，即在一般二叉树的基础上，对每个，即在一般二叉树的基础上，对每个结点进行考察。若其左子树非空，则其左指针不变，结点进行考察。若其左子树非空，则其左指针不变，结点进行考察。若其左子树非空，则其左指针不变，结点进行考察。若其左子树非空，则其左指针不变，仍指向左子树；若其左子树为空，则让其左指针指向仍指向左子树；若其左子树为空，则让其左指针指向仍指向左子树；若其左子树为空，则让其左指针指向仍指向
48、左子树；若其左子树为空，则让其左指针指向某种遍历顺序下该结点的前驱；若其右子树非空，则某种遍历顺序下该结点的前驱；若其右子树非空，则某种遍历顺序下该结点的前驱；若其右子树非空，则某种遍历顺序下该结点的前驱；若其右子树非空，则其右指针不变，仍指向右子树；若其右子树为空，则其右指针不变，仍指向右子树；若其右子树为空，则其右指针不变，仍指向右子树；若其右子树为空，则其右指针不变，仍指向右子树；若其右子树为空，则让其右指针指向某种遍历顺序下该结点的后继。如果让其右指针指向某种遍历顺序下该结点的后继。如果让其右指针指向某种遍历顺序下该结点的后继。如果让其右指针指向某种遍历顺序下该结点的后继。如果规定遍历
49、顺序为前序，则称为规定遍历顺序为前序，则称为规定遍历顺序为前序，则称为规定遍历顺序为前序，则称为前序线索二叉树前序线索二叉树前序线索二叉树前序线索二叉树；如果；如果；如果；如果规定遍历顺序为中序，则称为规定遍历顺序为中序，则称为规定遍历顺序为中序，则称为规定遍历顺序为中序，则称为中序线索二叉树中序线索二叉树中序线索二叉树中序线索二叉树；如果；如果；如果；如果规定遍历顺序为后序，则称为规定遍历顺序为后序，则称为规定遍历顺序为后序，则称为规定遍历顺序为后序，则称为后序线索二叉树后序线索二叉树后序线索二叉树后序线索二叉树。6.3 6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树二、线索二叉树（穿
50、线树、线索树）二、线索二叉树（穿线树、线索树）61标志域：标志域：标志域：标志域：LTag LTag = 0, = 0, lchildlchild为左孩子指针为左孩子指针为左孩子指针为左孩子指针LTagLTag = 1, = 1, lchildlchild为为为为前驱线索前驱线索前驱线索前驱线索RTagRTag = 0, = 0, rchildrchild为右孩子指针为右孩子指针为右孩子指针为右孩子指针RTagRTag = 1, = 1, rchildrchild为为为为后继指针后继指针后继指针后继指针6.3 6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树二、线索二叉树（穿线树、线索树）
51、二、线索二叉树（穿线树、线索树）62线索二叉树的类型描述线索二叉树的类型描述typedef enum PointerTag Link,Thread;typedef enum PointerTag Link,Thread;/Link=0/Link=0：指针，指向孩子结点：指针，指向孩子结点/Thread=1/Thread=1：线索，指向前驱或后继结点：线索，指向前驱或后继结点typedef struct BiThrNodetypedef struct BiThrNode TElemType data;TElemType data;struct BiThrNode *lchild,*rchild;
52、struct BiThrNode *lchild,*rchild;PointerTag LTag,RTag;PointerTag LTag,RTag; BiThrNode, *BiThrTree; BiThrNode, *BiThrTree;BiThrTree TBiThrTree T；6.3 6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树二、线索二叉树（穿线树、线索树）二、线索二叉树（穿线树、线索树） (Threaded Binary Tree)(Threaded Binary Tree)63中序中序线索二叉树线索二叉树中序遍历： B C A D F EABDCEF0100001111
53、11NULLNULL646.3 6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树二、线索二叉树（穿线树、线索树）二、线索二叉树（穿线树、线索树）65 1、问题的提出、问题的提出2、线索二叉树定义、线索二叉树定义3、在线索二叉树上找前驱和后继的规律在线索二叉树上找前驱和后继的规律4、如何建立中序线索二叉树？、如何建立中序线索二叉树？5、线索二叉树的遍历算法、线索二叉树的遍历算法1).1).在在先序先序线索线索二叉树找前驱和后继二叉树找前驱和后继2).2).在在中序中序线索线索二叉树找前驱和后继二叉树找前驱和后继3).3).在在后序后序线索线索二叉树找前驱和后继二叉树找前驱和后继 4). 线索
54、二叉树上找前驱和后继的规律线索二叉树上找前驱和后继的规律如果是非叶子结点，则：如果是非叶子结点，则： 如果有左孩子，则左孩子是其后继；如果有左孩子，则左孩子是其后继； 如果无左孩子，则右孩子是其后继；如果无左孩子，则右孩子是其后继；如果是叶子结点如果是叶子结点，则右线索所指结点为后继；则右线索所指结点为后继； 如果无左孩子，则左线索所指结点为前驱如果无左孩子，则左线索所指结点为前驱；否则需要遍历；否则需要遍历；NULLABDCEF010000111111先序先序线索二叉树线索二叉树A B C D E F找后继：找后继：找前驱：找前驱：1).1).在在先序先序线索线索二叉树找前驱和后继二叉树找前
55、驱和后继 若无右孩子，则右线索所指结点为后继；若无右孩子，则右线索所指结点为后继； 否则，右孩子的否则，右孩子的“最左下最左下”孩子为后继；孩子为后继；若无左孩子，则左线索所指结点为前驱；若无左孩子，则左线索所指结点为前驱；否则，左孩子的否则，左孩子的“最右下最右下”孩子为前驱；孩子为前驱；找后继：找后继：找前驱：找前驱：NULLABDCEF000001101111NULL中序中序线索二叉树线索二叉树C H B A D F EH112).2).在在中序中序线索线索二叉树找前驱和后继二叉树找前驱和后继如果无右孩子，则右线索所指结点为后继如果无右孩子，则右线索所指结点为后继；否则需要遍历；否则需要
56、遍历；如果如果有有右孩子，则右孩子是其前驱；右孩子，则右孩子是其前驱；如果如果无无右孩子，但有左孩子，则左孩子为前驱；右孩子，但有左孩子，则左孩子为前驱；如果无左孩子，则左线索所指结点为前驱；如果无左孩子，则左线索所指结点为前驱；后序后序线索二叉树线索二叉树C B F E D A找后继：找后继：找前驱：找前驱：ABDCEF010000111111NULL3).3).在在后序后序线索线索二叉树找前驱和后继二叉树找前驱和后继 4). 线索二叉树上找前驱和后继的一般规律线索二叉树上找前驱和后继的一般规律先序先序线索二叉树找后继方便，线索二叉树找后继方便， 找前驱可能需要遍历。找前驱可能需要遍历。中序
57、中序线索二叉树找前驱和后继都方便线索二叉树找前驱和后继都方便后序后序线索二叉树找前驱方便，线索二叉树找前驱方便， 找后继可能需要遍历。找后继可能需要遍历。6.3 6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树二、线索二叉树（穿线树、线索树）二、线索二叉树（穿线树、线索树）71 1、问题的提出、问题的提出2、线索二叉树定义、线索二叉树定义3、在线索二叉树上找前驱和后继的规律、在线索二叉树上找前驱和后继的规律4、如何建立中序线索二叉树？（自学）如何建立中序线索二叉树？（自学）5、线索二叉树的遍历算法、线索二叉树的遍历算法6.3 6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树二、线索二叉
58、树（穿线树、线索树）二、线索二叉树（穿线树、线索树）72 1、问题的提出、问题的提出2、线索二叉树定义、线索二叉树定义3、在线索二叉树上找前驱和后继的规律、在线索二叉树上找前驱和后继的规律4、如何建立中序线索二叉树？、如何建立中序线索二叉树？5、线索二叉树的遍历算法线索二叉树的遍历算法5、中序线索二叉树的遍历算法、中序线索二叉树的遍历算法 如果已经通过遍历如果已经通过遍历(前序，中序和后序前序，中序和后序) 得到得到线索二叉树。线索二叉树。 那么，对线索化的二叉树进行遍那么，对线索化的二叉树进行遍历就比对一般二叉树进行遍历更加有效和方便。历就比对一般二叉树进行遍历更加有效和方便。带头结点的带头
59、结点的中序中序线索二叉树线索二叉树ABDCEF010000111111根结点根结点NULLNULL B C A D F E01头结点头结点T 中序中序线索二叉树的遍历算法线索二叉树的遍历算法 中序遍历的第一个结点中序遍历的第一个结点 ？ 在中序线索二叉树中结点的后继在中序线索二叉树中结点的后继 ？左子树上处于“最左下最左下”（没有左子树）的结点若若无右子树，则则右线索所指结点为后继右线索所指结点为后继否则，否则，右子树的右子树的“最左下最左下”孩子为后继；孩子为后继； 结束的条件结束的条件? ? 树空或者指针指向头结点树空或者指针指向头结点Status InOrderTraverse_Thr(
60、BiThrTree T, void (*Visit)(TElemType e) p = T-lchild; / T指向头结点，p指向根结点 while (p != T) / 空树或遍历结束时，p=T while (p-LTag=Link) p = p-lchild; / 最左下最左下结点结点 Visit(p-data) ； / 访问最左下访问最左下结点结点 while (p-RTag=Thread & p-rchild!=T) p = p-rchild; Visit(p-data); / 访问后继结点访问后继结点 p = p-rchild; / p进至其右子树根或头结点进至其右子树根或头结点
61、return OK； / InOrderTraverse_Thr6.4 6.4 树和森林树和森林77 1、树的三种存储结构树的三种存储结构2、森林与二叉树的转换、森林与二叉树的转换3、树和森林的遍历（自学）、树和森林的遍历（自学）树的三种存储结构树的三种存储结构（1）双亲表示法双亲表示法（2）孩子链表表示法孩子链表表示法（3）孩子孩子- -兄弟表示法兄弟表示法ABCDEFGr=0n=70 A -11 B 02 C 03 D 04 E 2 5 F 26 G 5data parent（1）双亲表示法）双亲表示法: 树树 结点结点 typedef struct PTNode TElemType da
62、ta; int parent; / 双亲位置域 PTNode; data parent#define MAX_TREE_SIZE 100结点结构结点结构:C语言的类型描述语言的类型描述: :typedef struct PTNode nodes MAX_TREE_SIZE; int r, n； / 根结点的位置和结点个数 PTree;树结构树结构:0 A1 B 2 C 3 D 4 E 5 F 6 G 0 1 2 3 4 5 6 r = 0 n = 7ABCDEFG64 5 1 2 3（2）孩子链表表示法）孩子链表表示法:1 1。树。树2 2。孩子链表的头结点。孩子链表的头结点3 3。孩子链表结
63、点。孩子链表结点 data firstchildchild nextchildtypedef struct CTBox nodesMAX_TREE_SIZE; int n, r; / 结点数和根结点的位置 CTree;树树:typedef struct CTNode int child; struct CTNode *next; *ChildPtr;孩子孩子链表链表结点结点: typedef struct TElemType data; ChildPtr firstchild; / 孩子链的头指针 CTBox;孩子孩子链表链表 头头结点结点:ABCDEFG二叉树二叉树 AB C E D F G
64、 ABCEDFG树树二叉链表表示二叉链表表示 firstchild data nextsibling（3）树的孩子）树的孩子-兄弟表示法兄弟表示法C语言的类型描述语言的类型描述: :typedef struct CSNode Elem data; struct CSNode *firstchild, *nextsibling; CSNode, *CSTree;二叉结点二叉结点: firstchild data nextsiblingn双亲表示法双亲表示法q用结构数组用结构数组树的顺序存储方式树的顺序存储方式q类型定义：类型定义：q找双亲方便，找孩子难找双亲方便，找孩子难n孩子链表表示法孩子链表
65、表示法q顺序和链式结合的表示方法顺序和链式结合的表示方法q找孩子方便，找双亲难找孩子方便，找双亲难n孩子兄弟表示法孩子兄弟表示法q找孩子容易，若增加找孩子容易，若增加parentparent域，则找双亲也较域，则找双亲也较方便。方便。森林与二叉树的转换森林与二叉树的转换（1） 树转换为二叉树树转换为二叉树（2）二叉树还原成树）二叉树还原成树（3） 森林转换成二叉树森林转换成二叉树转换对应的二叉树转换对应的二叉树树树ABCDE二叉链表存储表示二叉链表存储表示ABCEDABCEDABCEAABCED图图6.166.16举例：举例：ABECDFGHIABEDCIIFG（1） 树转换为二叉树树转换为二
66、叉树树转换为二叉树的步骤树转换为二叉树的步骤:加线：加线：在兄弟结点之间加一连线；在兄弟结点之间加一连线；抹线：抹线：对任何结点，除了其最左的孩子对任何结点，除了其最左的孩子 外，抹掉该结点原先与其孩子之外，抹掉该结点原先与其孩子之 间的连线；间的连线；旋转：旋转：将水平的连线和原有的连线，以将水平的连线和原有的连线，以 树根结点为轴心，按顺时针方向树根结点为轴心，按顺时针方向 粗略地旋转粗略地旋转450。举例：举例：ABEDCI HFGABECDFGH I（2） 二叉树还原成二叉树还原成树树二叉树还原成树的步骤二叉树还原成树的步骤加线：加线：如果如果p结点是双亲结点的左孩子结点是双亲结点的左
67、孩子; 则将则将p结点的右孩子结点的右孩子,右孩子的右右孩子的右 孩子孩子,沿着右分支搜索到的沿着右分支搜索到的 所有右孩子都分别与所有右孩子都分别与p结点的双结点的双 亲用线连接起来亲用线连接起来;抹线：抹线：抹掉原二叉树中所有双亲结点与抹掉原二叉树中所有双亲结点与 右孩子的连线；右孩子的连线；调整：调整： 将结点按层次排列将结点按层次排列,形成树的结构形成树的结构.ABDCEFIHGJABCDHGIJEFABCDEFHGIJ举例：举例：（3） 森林转换成二叉树森林转换成二叉树 森林转换成二叉树的步骤森林转换成二叉树的步骤:转换：转换：将森林中的每一棵树转换成二将森林中的每一棵树转换成二 叉
68、树叉树;连线：连线：将各棵转换后的二叉树的根结将各棵转换后的二叉树的根结 点相连；点相连；旋转：旋转：将添加的水平线和原有的连线将添加的水平线和原有的连线, 以第一棵树的根结点为轴心以第一棵树的根结点为轴心,按按 顺时针方向旋转顺时针方向旋转450。森林转化成二叉树的规则森林转化成二叉树的规则 若森林若森林F为空为空，即，即n = 0，则，则 对应的二叉树对应的二叉树B为空二叉树。为空二叉树。 若若F不空不空，则，则 对应二叉树对应二叉树B的的根根root (B)是是F中第一棵树中第一棵树T1的根的根root (T1)； 其其左子树为左子树为B (T11, T12, , T1m)，其中，其中，
69、T11, T12, , T1m是是root (T1)的子树；的子树； 其其右子树为右子树为B (T2, T3, , Tn)，其中，其中，T2, T3, , Tn是除是除T1外其它树构成的森林。外其它树构成的森林。6.6 6.6 赫夫曼树及其应用赫夫曼树及其应用95 n最优树的定义最优树的定义n如何构造最优树如何构造最优树n最优树的应用最优树的应用1、最优树的定义、最优树的定义树的路径长度树的路径长度： 树的根到每个结点的路径长度之和。树的根到每个结点的路径长度之和。 路径长度路径长度： 路径上分支的数目。路径上分支的数目。 路径路径： 从树中一个结点到另一个结点之从树中一个结点到另一个结点之间
70、的分支所构成的通路间的分支所构成的通路 。 结点的带权路径长度结点的带权路径长度： 从树根到该结点之间的长度与从树根到该结点之间的长度与结点权值的乘积结点权值的乘积 ( l * w ) 。 树的带权路径长度树的带权路径长度： 树中所有叶子树中所有叶子结点的带权路径长度结点的带权路径长度之和之和 WPL(T) = wk lk 27 9 75492WPL(T)= 7 2+5 2+2 3+4 3+9 2 =60WPL(T)= 7 4+9 4+5 3+4 2+2 1 =89 54 在所有含在所有含 n 个叶子结点、并带相个叶子结点、并带相同权值的同权值的 m 叉树中，必存在一棵其叉树中，必存在一棵其带
71、权路径长度取最小值带权路径长度取最小值的树，称为的树，称为“最优树最优树”。最优树可能不止一个！最优树可能不止一个！具有不同带权路径长度的扩充二叉树具有不同带权路径长度的扩充二叉树赫夫曼树赫夫曼树 带权路径长度达到最小的二叉树即为赫夫曼树带权路径长度达到最小的二叉树即为赫夫曼树（最优二叉树）。（最优二叉树）。 在赫夫曼树中，权值大的结点离根最近。在赫夫曼树中，权值大的结点离根最近。6.6 6.6 赫夫曼树及其应用赫夫曼树及其应用101 n最优树的定义最优树的定义n如何构造最优树如何构造最优树n最优树的应用最优树的应用赫夫曼算法赫夫曼算法 如何构造一棵赫夫曼树如何构造一棵赫夫曼树 (1) 由给定
72、的由给定的n个权值个权值w0, w1, w2, , wn-1，构造，构造具有具有n棵二叉树的森林棵二叉树的森林F = T0, T1, T2, , Tn-1，其，其中每一棵二叉树中每一棵二叉树Ti只有一个带有权值只有一个带有权值wi的根结点，的根结点，其左、右子树均为空。其左、右子树均为空。 (2) 重复以下步骤重复以下步骤, 直到直到F中仅剩下一棵树为止：中仅剩下一棵树为止： 在在F中选取两棵根结点的权值最小的二叉树中选取两棵根结点的权值最小的二叉树, 做为左、右子树构造一棵新的二叉树。置新的二做为左、右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的叉树的根结点的权
73、值为其左、右子树上根结点的权值之和。权值之和。 在在F中删去这两棵二叉树。中删去这两棵二叉树。 把新的二叉树加入把新的二叉树加入F。例如例如: : 已知权值已知权值 W= 5, 6, 2, 9, 7 956275276976713952767139527952716671329哈夫曼树 wpl6272532392 65可以证明哈夫曼树是最可以证明哈夫曼树是最优树优树例如例如: : 已知权值已知权值 W= 5, 6, 2, 7, 7,7 75627WPL = 63+7472142 18710885276713342077147671334205277714WPL = 63+7373142 187
74、10886.6 6.6 赫夫曼树及其应用赫夫曼树及其应用106 n最优树的定义最优树的定义n如何构造最优树如何构造最优树n最优树的应用最优树的应用n在解决某些判定问题时，利用赫在解决某些判定问题时，利用赫夫曼树可以得到最佳判定算法夫曼树可以得到最佳判定算法 n用于通讯和数据传送时的赫夫曼用于通讯和数据传送时的赫夫曼编码编码3、最优树的应用、最优树的应用 假设电文由假设电文由A,B,C,D四个字符组成四个字符组成.它们的编码分别为它们的编码分别为00,01,10和和11. 则电文则电文ABACCDA 的编码为的编码为00010010101100, 总长为总长为14位位. 为减少编码长度为减少编码
75、长度,重新设重新设 A,B,C,D四个四个字符的编码为字符的编码为0,00,1和和01. 则电文编码为则电文编码为000011010,总长为总长为9位位.3、最优树的应用、最优树的应用ABA0000AAAABB BAA 前缀编码前缀编码指的是，任何一个字符任何一个字符的编码都不是同一字符集中另一个字的编码都不是同一字符集中另一个字符的编码的前缀符的编码的前缀。0 00 1 01 0 100 101 11 A B C D00 01 10 11 是是前缀编码前缀编码不是不是前缀编码前缀编码是是前缀编码前缀编码(2) 0 00 1 01 不是前缀编码前缀编码(3) 0 100 101 11 是前缀编
76、码前缀编码A B C D(1) 00 01 10 11 是前缀编码前缀编码ABCD0111000001 1011(1)ABCD011011010010101(3)BCD010100011(2)AABCD0111000001 1011(1)ABCD011011010010101(3)那一种电报编那一种电报编码的总长更短？码的总长更短？1 1。假设概率相同。假设概率相同, ,且均为且均为k k wpl(1)=k*2*4wpl(1)=k*2*48k8k wpl(3)=k*1+k*3*2+k*2wpl(3)=k*1+k*3*2+k*29k9k2 2。概率不同。概率不同, ,且且A A为为0.5,B0.
77、5,B为为0.1,C0.1,C为为0.1,D0.1,D为为0.30.3wpl(1)=0.5*2+0.1*2*2+0.3*2wpl(1)=0.5*2+0.1*2*2+0.3*22 2Wpl(3)=0.5*1+0.1*2*3+0.3*2Wpl(3)=0.5*1+0.1*2*3+0.3*21.71.7 利用赫夫曼树可以构造一种不等利用赫夫曼树可以构造一种不等长的二进制编码，并且构造所得的长的二进制编码，并且构造所得的赫夫曼编码赫夫曼编码是一种是一种最优前缀编码最优前缀编码，使所传使所传电文的总长度最短电文的总长度最短。举例举例: 已知某系统在通讯联络中只可能已知某系统在通讯联络中只可能 出现八种字符
78、出现八种字符A,B,C,D,E,F,G,H, 其概率其概率 分别为分别为: 0.05, 0.29, 0.07, 0.08, 0.14, 0.23,0.03,0.11 试设计试设计赫夫曼编码赫夫曼编码.设权设权 w = 5, 29, 7, 8, 14, 23, 3, 11 A B C D E F G H设权设权 w = 5, 29, 7, 8, 14, 23, 3, 11 29 5 7 8 3142311 5 38 8 71511191429234229581000000111100011100010011001111011011101111举例举例: 已知某系统在通讯联络中只可能已知某系统在通
79、讯联络中只可能 出现八种字符出现八种字符A,B,C,D,E,F,G,H, 其概率其概率 分别为分别为: 0.05, 0.29, 0.07, 0.08, 0.14, 0.23,0.03,0.11 试设计试设计赫夫曼编码赫夫曼编码.赫夫曼编码赫夫曼编码: 0110, 10, 1110, 1111, 110, 00, 0111, 010设权设权 w = 5, 29, 7, 8, 14, 23, 3, 11 A B C D E F G H数据文件压缩数据文件压缩: : 已知一个由已知一个由A,B,C,D,E,F,G,HA,B,C,D,E,F,G,H等八个字符组成的文件等八个字符组成的文件包含包含100
80、100个字符，如果对这八个字符都按等长编码：个字符，如果对这八个字符都按等长编码： 000,001,010,011,100,101,110000,001,010,011,100,101,110，111 111 则文件包含的总位数为：则文件包含的总位数为：10031003300 300 位位 现已知八个字符在文件中出现的个数分别为现已知八个字符在文件中出现的个数分别为: : 5,29,7,8,14,23,3,115,29,7,8,14,23,3,11 如果采用赫夫曼编码如果采用赫夫曼编码: : 0110,0110,1010,1110,1110,11111111,110,110,0000,0111
81、,0111,010010 则文件的总位数为：则文件的总位数为： 545429229274748484143143232232+34+113=271 +34+113=271 位位 压缩率为压缩率为1010typedef struct unsigned int weight;unsigned int parent,lchild,rchild; HTNode, *HuffmanTree;typedef char *HuffmanCode;建立赫夫曼树及求赫夫曼编码的算法建立赫夫曼树及求赫夫曼编码的算法void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC
82、,int *w, int n) HuffmanTree p;char *cd;int i,s1,s2,start; unsigned int c,f; if (n=1) return; / n为字符数目，m为结点数目 int m=2*n-1; HT = (HuffmanTree)malloc(m+1)*sizeof(HTNode); / 0号单元未用 for (p=HT, i=1; iweight = *w; p-parent=0; p-lchild=0;p-rchild=0; / *p = *w,0,0,0 ; for (; iweight = 0; p-parent=0; p-lchild
83、=0; p-rchild=0; /*p= 0,0,0,0 ; for (i=n+1; i=m;+i) / 建赫夫曼树建赫夫曼树 Select(HT,i-1,s1,s2);HTs1.parent=i; HTs2.parent = i;HTi.lchild = s1; HTi.rchild = s2;HTi.weight = HTs1.weight + HTs2.weight; /从叶子到根逆向求赫夫曼编码 HC= (HuffmanCode)malloc(n+1)*sizeof(char *); cd = (char*)malloc(n*sizeof(char); cdn-1=0; for (i=
84、1;i=n;+i) start = n-1; for (c=i,f=HTc.parent; f!=0; c=f,f=HTf.parent) if (HTf.lchild =c) cd-start=0; else cd-start=1; HCi=(char *)malloc(n-start)*sizeof(char); strcpy(HCi,&cdstart); printf(%sn,HCi); free(cd);121n树树1 1、树的几个基本术语：、树的几个基本术语：树、结点的度、树的树、结点的度、树的度、分支结点、叶子结点、结点的层数等度、分支结点、叶子结点、结点的层数等2 2、树的、树的
85、4 4种表示：种表示：树形表示、嵌套集合表示、树形表示、嵌套集合表示、凹入表示、广义表表示法凹入表示、广义表表示法3 3、树的性质、树的性质4 4、树的存储结构：、树的存储结构：顺序存储和链式存储顺序存储和链式存储5 5、树的遍历树的遍历: :先根遍历、后根遍历、层次遍历先根遍历、后根遍历、层次遍历本章总结：本章总结：122n二叉树二叉树1 1、二叉树的几个基本术语：、二叉树的几个基本术语：二叉树、满二叉二叉树、满二叉树、完全二叉树树、完全二叉树2 2、二叉树的性质、二叉树的性质3 3、二叉树的存储结构：、二叉树的存储结构：顺序存储和链式存储顺序存储和链式存储4 4、线索二叉树、线索二叉树5
86、5、二叉树的、二叉树的3 3种遍历：种遍历：先序遍历、中序遍历、先序遍历、中序遍历、后序遍历后序遍历本章总结：本章总结：123n树和森林树和森林1 1、树与二叉树的相互转换、树与二叉树的相互转换2 2、森林与二叉树的相互转换、森林与二叉树的相互转换本章总结：本章总结：n赫夫曼树赫夫曼树1 1、赫夫曼树的定义、赫夫曼树的定义2 2、构造赫夫曼树的算法、构造赫夫曼树的算法3 3、赫夫曼树的应用、赫夫曼树的应用124思考题：思考题：1 1、一棵度为、一棵度为2 2的树与一棵二叉树有何区别。的树与一棵二叉树有何区别。 2 2、已知用一维数组存放的一棵完全二叉树：、已知用一维数组存放的一棵完全二叉树：A
87、BCDEFGHIJKLABCDEFGHIJKL，写出该二叉树的先序、中序和后序遍历序，写出该二叉树的先序、中序和后序遍历序列。列。 3 3、假设一棵二叉树的先序序列为、假设一棵二叉树的先序序列为EBADCFHGIKJEBADCFHGIKJ，中序序列，中序序列为为ABCDEFGHIJKABCDEFGHIJK，请写出该二叉树的后序遍历序列。，请写出该二叉树的后序遍历序列。 4 4、给定一组权值（、给定一组权值（5 5，9 9，1111，2 2，7 7，1616），试设计相应），试设计相应的哈夫曼树。的哈夫曼树。 5 5、给定一棵用二叉链表表示的二叉树，其中的指针、给定一棵用二叉链表表示的二叉树，其
88、中的指针t t指向指向根结点，试写出从根开始，按层次遍历二叉树的算法，同根结点，试写出从根开始，按层次遍历二叉树的算法，同层的结点按从左至右的次序访问。层的结点按从左至右的次序访问。 算法题：算法题：1 1、顺序存储方式的二叉树的建立算法。、顺序存储方式的二叉树的建立算法。2 2、已知先根序列递归建立的二叉树，要求输入、已知先根序列递归建立的二叉树，要求输入的序列字数要补齐。的序列字数要补齐。3 3、已知二叉树的中根序列和先根序列，构造建、已知二叉树的中根序列和先根序列，构造建立相应的二叉链表。立相应的二叉链表。4 4、二叉树的遍历算法（利用递归和非递归算法、二叉树的遍历算法（利用递归和非递归算法完成前序、中序、后序的遍历）。完成前序、中序、后序的遍历）。125第六章内容到此结束
