第6二叉树part样式编辑母版文本样式

1、 第6章 树和二叉树v6.1 树的类型定义树的类型定义v6.2 二叉树的类型定义二叉树的类型定义v6.3 二叉树的存储结构二叉树的存储结构v6.4 二叉树的遍历二叉树的遍历v6.5 线索二叉树线索二叉树v6.6 树和森林的表示方法树和森林的表示方法v6.7 树和森林的遍历树和森林的遍历v6.8 哈夫曼树与哈夫曼编码哈夫曼树与哈夫曼编码线索二叉树线索二叉树v将二叉树遍历一遍，在遍历过程中便可得到将二叉树遍历一遍，在遍历过程中便可得到结点的前驱和后继，但这种动态访问浪费时结点的前驱和后继，但这种动态访问浪费时间；间；v充分利用二叉链表中的空链域，充分利用二叉链表中的空链域， 将遍历过程将遍历过程中

2、结点的前驱、中结点的前驱、 后继信息保存下来。后继信息保存下来。二叉链表中有多少个空链域二叉链表中有多少个空链域?2n-(n-1)=n+1线索二叉树线索二叉树v对对线索链表线索链表中结点的约定：在二叉链表的结中结点的约定：在二叉链表的结点中增加两个标志域，并作如下规定：点中增加两个标志域，并作如下规定： 若该结点的左子树不空，则若该结点的左子树不空，则Lchild域的指针指向域的指针指向其左子树，且左标志域的值为其左子树，且左标志域的值为“指针指针 Link”；否；否则，则，Lchild域的指针指向其域的指针指向其“前驱前驱”，且左标志，且左标志的值为的值为“线索线索 Thread” 。若该结

3、点的右子树不空，则若该结点的右子树不空，则rchild域的指针指向域的指针指向其右子树，且右标志域的值为其右子树，且右标志域的值为 “指针指针 Link”；否；否则，则，rchild域的指针指向其域的指针指向其“后继后继”，且右标志，且右标志的值为的值为“线索线索 Thread”。 v指向前驱和后继结点的指针叫做指向前驱和后继结点的指针叫做线索线索。v以这种结构组成的二叉链表作为二叉树的存储结构，叫做以这种结构组成的二叉链表作为二叉树的存储结构，叫做线线索链表索链表。v对二叉树以某种次序进行遍历并且加上线索的过程叫做对二叉树以某种次序进行遍历并且加上线索的过程叫做线索线索化化。v线索化了的二叉

4、树称为线索化了的二叉树称为线索二叉树线索二叉树。lchildLtagDataRtagrchild0 lchild域指示结点的左孩子域指示结点的左孩子1lchild域指示结点的遍历前驱域指示结点的遍历前驱0 rchild域指示结点的右孩子域指示结点的右孩子1 rchild域指示结点的遍历后继域指示结点的遍历后继 LTag=RTag=结结点点结结构构typedef struct BiThrNode TElemType data; / /* *结点数据域结点数据域* */ / int LTag, RTag; / /* *增加的线索标记增加的线索标记* */ / struct BiThrNode *l

5、child;/ /* *左孩子或线索指针左孩子或线索指针* */ / struct BiThrNode *rchild;/ /* *右孩子或线索指针右孩子或线索指针* */ /BiThrNode, *BiThrTree; / /* *线索树结点类型定义线索树结点类型定义* */ / lchildLtagDataRtagrchild线索树结点类型定义：线索树结点类型定义：线索树：线索树：ABCDEFGH(a) 二叉 树ABCDEFGH(b )先序线索二叉 树ACDEFGH(c) 中序线索二叉树ABCDEFGH(d ) 后序线索二叉 树BN U LLN U LLN U LLN U LLABDGCE

6、HFDGBAEHCFGDBHEFCA访问线索二叉树访问线索二叉树v由于在线索链表中添加了遍历中得到的“前驱”和“后继”的信息，从而简化了遍历的算法。v遍历线索二叉树的流程： for ( p = firstNode(T); p!=null ; p = Succ(p) ) Visit (p);其中：其中： firstNode(T) 为遍历序列的第一个结点为遍历序列的第一个结点 Succ(p)为为p结点的后继结点的后继访问线索二叉树访问线索二叉树v中序线索二叉树中，查找指定结点的前驱和后继中序线索二叉树中，查找指定结点的前驱和后继找结点的中序前驱结点：找结点的中序前驱结点：结点结点p，无左孩子，无左

7、孩子，左指针指向其前驱，否则左指针指向其前驱，否则p的的左子树左子树“最右下最右下”结点结点。BiThrTree PreNode(BiThrTree p) pre = p-lchild; if(p-LTag = 0) /有左孩子有左孩子 while(pre-RTag = 0) pre = pre-rchild; return pre;ABCDEFGH(a) 二叉树ABCDEFGH(b )先序线索二叉树ACDEFGH(c) 中序线索二叉树ABCDEFGH(d) 后序线索二叉树BNULLNULLNULLNULL访问线索二叉树访问线索二叉树找结点的中序后继结点：找结点的中序后继结点：结点结点p，无右

8、孩子，无右孩子，右指针指向其后继，否则右指针指向其后继，否则p的右子树中的右子树中“最左下最左下”结点结点。BiThrTree PostNode(BiThrTree p) post = p-rchild; if(p-RTag = 0) /有右孩子有右孩子 while(post-LTag = 0) post = post-lchild; return post;ABCDEFGH(a) 二叉树ABCDEFGH(b )先序线索 二叉树ACDEFGH(c) 中序线索二叉树ABCDEFGH(d) 后序线索 二叉树BNULLNULLNULLNULL访问线索二叉树访问线索二叉树v对中序线索化链表的遍历算法对

9、中序线索化链表的遍历算法ABCDEFGH(a) 二叉树ABCDEFGH(b )先序线索 二叉树ACDEFGH(c) 中序线索二叉树ABCDEFGH(d) 后序线索 二叉树BNULLNULLNULLNULLz中序遍历的第一个结点中序遍历的第一个结点 ：左子树上处于“最左下最左下”（没有左子树）的结点z在中序线索化链表中结在中序线索化链表中结点的后继：点的后继：若无右子树，若无右子树，则为后继线索所指结点；则为后继线索所指结点；否则为对其右子树进行中否则为对其右子树进行中序遍历时访问的第一个结序遍历时访问的第一个结点。点。带头结点的线索二叉链表带头结点的线索二叉链表 0 1 0 + 0 1 a 1

10、 1 b 1 Thrt 带头结点的中序线索二叉链表带头结点的中序线索二叉链表v中序遍历线索二叉树中序遍历线索二叉树 / 0:有孩子；有孩子；1：无孩子：无孩子Void InOrderTraverse_Thr( BiThrTree T ) /T:头结点头结点 p = T-lchild; /p指向树根结点指向树根结点 while(p != T) while( p-LTag = 0 ) p=p-lchild; Visit(p-data); / 访问第一个结点访问第一个结点 while( p-RTag=1 & p-rchild!=T ) p = p-rchild; Visit(p-data);

11、 / 访问后继结点访问后继结点 p = p-rchild; 建立线索化链表建立线索化链表v建立线索化链表（以中序为例）建立线索化链表（以中序为例） 0 1 0 + 0 1 a 1 1 b 1 Thrt 对线索树进行遍历，显然其效率要比传统方式高些。对线索树进行遍历，显然其效率要比传统方式高些。如果程序中经常要进行二叉树的遍历或者需要查找在如果程序中经常要进行二叉树的遍历或者需要查找在遍历过程中所的线性序列中前驱和后继，此时应当采遍历过程中所的线性序列中前驱和后继，此时应当采用线索链表表示。用线索链表表示。按某种次序将二叉链表线索按某种次序将二叉链表线索化，实质是在遍历过程中化，实质是在遍历过程

12、中用用线索取代空指针线索取代空指针。树和森林的表示方法树和森林的表示方法v树的存储结构（三种方法）树的存储结构（三种方法） 双亲表示法双亲表示法 孩子表示法孩子表示法 树的二叉链表树的二叉链表(孩子孩子-兄弟）存储表示法兄弟）存储表示法树的树的双亲表示法双亲表示法v双亲表示法：双亲表示法：用一组用一组连续的空间连续的空间来存储树中来存储树中的结点，在保存每个结点的同时附设一个指的结点，在保存每个结点的同时附设一个指示器来示器来指示其双亲结点在表中的位置指示其双亲结点在表中的位置， 其结其结点的结构如下：点的结构如下： DataParent A D B C G E F A -1 B 0 C 0

13、D 0 E 2 F 2 G 2 0 1 2 3 4 5 6 (a) (b) 树的双亲存储结构示意图树的双亲存储结构示意图define MAX_TREE_SIZE 100typedef struct PTNode TElemType data; int parent; PTNode; Typedef struct PTNode nodesMAX_TREE_SIZE; int r, n; /根的位置和结点数根的位置和结点数PTree;双亲表示法的类型说明：双亲表示法的类型说明： data parent结点结构结点结构:树的孩子表示法树的孩子表示法v孩子表示法：孩子表示法：多重链表，即每个结点有多个

14、指针域，多重链表，即每个结点有多个指针域，其中每个指针指向一棵子树的根结点。其中每个指针指向一棵子树的根结点。同构：同构：异构：异构：孩子链表表示法孩子链表表示法v把每个结点的孩子结点排列起来，构成一个单链表，把每个结点的孩子结点排列起来，构成一个单链表， 称为称为孩子链表孩子链表。vn个结点共有个结点共有n个孩子链表，而个孩子链表，而n个结点的数据和个结点的数据和n个孩子链个孩子链表的头指针又组成一个顺序表。表的头指针又组成一个顺序表。 A D B C G E F (a) A B C D E F G 0 1 2 3 4 5 6 (b) 1 2 3 4 5 6 typedef struct C

15、TNode /* 孩子结点的定义孩子结点的定义 */ int Child; /* 该孩子结点在线性表中的位置该孩子结点在线性表中的位置 */ struct CTNode *next; /* 指向下一个孩子结点的指针指向下一个孩子结点的指针 */*ChildPtr;typedef struct /* 顺序表结点的结构定义顺序表结点的结构定义 */ TElemType data; /* 结点的信息结点的信息 */ ChildPtr FirstChild ; /* 指向孩子链表的头指针指向孩子链表的头指针 */CTBox;typedef struct /* 树的定义树的定义 */ CTBox nod

16、esMAX_TREE_SIZE; /* 顺序表顺序表 */ int root, num; /* 根结点的位置和树的结点个数根结点的位置和树的结点个数 */ CTree; 孩子链表表示法的类型说明：孩子链表表示法的类型说明：带双亲的孩子链表：带双亲的孩子链表：树的孩子兄弟表示法树的孩子兄弟表示法v孩子兄弟表示法：孩子兄弟表示法：又称为二叉树表示法或者二叉链又称为二叉树表示法或者二叉链表表示法。即以二叉链表作为树的存储结构。链表表表示法。即以二叉链表作为树的存储结构。链表中结点的两个指针域分别指向该结点的中结点的两个指针域分别指向该结点的第一个孩子第一个孩子结点结点和和下一个兄弟结点下一个兄弟结点

17、。typedef struct CSNode ElemType data; /*结点信息结点信息*/ Struct CSNode *FirstChild, *NextSibling; /*第一个孩子第一个孩子, 下一个兄弟下一个兄弟*/CSNode, *CSTree; 树的孩子兄弟表示法树的孩子兄弟表示法树的树的孩子兄弟链孩子兄弟链存储结构示意图存储结构示意图树、森林与二叉树的相互转换树、森林与二叉树的相互转换v树与二叉树的对应关系树与二叉树的对应关系 二叉树和树都可以使用二叉链表存储二叉树和树都可以使用二叉链表存储规律：规律：当一个树使用二叉链表存储时，其根结点右当一个树使用二叉链表存储时，

18、其根结点右子树必为空子树必为空树转换为二叉树树转换为二叉树 v树转换为二叉树的步骤树转换为二叉树的步骤; (1)在所有相邻兄弟结点之间加一水平连线。在所有相邻兄弟结点之间加一水平连线。 (2)对每个非叶结点对每个非叶结点k,除了其最左边的孩子结点除了其最左边的孩子结点外外,删去删去k与其他孩子结点的连线。与其他孩子结点的连线。 (3)所有水平线段以左边结点为轴心顺时针旋转所有水平线段以左边结点为轴心顺时针旋转45度，使之结构层次分明。度，使之结构层次分明。 树做这样的转换所构成的二叉树是唯一的。树做这样的转换所构成的二叉树是唯一的。树转换为二叉树树转换为二叉树v树转换为二叉树的例子：树转换为二

19、叉树的例子：ABDEFCGHABDEFCGHABDEFCHGDABCE对应ABCDEABCDEEABCDABCDE存储存储解释解释树与二叉树的对应树与二叉树的对应森林转换为二叉树森林转换为二叉树v森林也可以方便地用孩子兄弟链表表示。森森林也可以方便地用孩子兄弟链表表示。森林转换为二叉树的方法如下：林转换为二叉树的方法如下： (1) 将森林中的每棵树转换成相应的二叉树。将森林中的每棵树转换成相应的二叉树。 (2) 第一棵二叉树不动，从第二棵二叉树开始，第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子，根结点的

20、右孩子， 当所有二叉树连在一起后，所当所有二叉树连在一起后，所得到的二叉树就是由森林转换得到的二叉树。得到的二叉树就是由森林转换得到的二叉树。森林与二叉树的对应关系：森林与二叉树的对应关系：二叉树还原为树或森林二叉树还原为树或森林v将一棵二叉树还原为树或森林，具体方法如将一棵二叉树还原为树或森林，具体方法如下：下： (1) 若某结点是其双亲的左孩子，则把该结点的若某结点是其双亲的左孩子，则把该结点的右孩子、右孩子、 右孩子的右孩子右孩子的右孩子都与该结点的双亲都与该结点的双亲结点用线连起来。结点用线连起来。 (2) 删掉原二叉树中所有双亲结点与右孩子结点删掉原二叉树中所有双亲结点与右孩子结点的

21、连线。的连线。 (3) 整理由（整理由（1）、（）、（2）两步所得到的树或森林，）两步所得到的树或森林， 使之结构层次分明。使之结构层次分明。 ABECFGHIJD(a) 添加连线ABECFGHIJD(b) 删除右孩子结点的连线ABCDEFGHIJ(c) 整理二叉树到森林的转换示例二叉树到森林的转换示例树与森林的遍历树与森林的遍历v树的遍历（两种）树的遍历（两种）: 先根遍历先根遍历 后根遍历后根遍历v森林的遍历（两种）森林的遍历（两种）: 先序遍历先序遍历 中序遍历中序遍历树的遍历树的遍历v先根遍历先根遍历若树非空，则遍历方法为若树非空，则遍历方法为: 先访问根结点先访问根结点 再从左到右，

22、再从左到右， 依次先根依次先根遍历根结点的每一棵子树遍历根结点的每一棵子树等同于转换的二叉树进行等同于转换的二叉树进行先序遍历先序遍历ACBDEFGH先根遍历序列先根遍历序列ABECFHGD树的遍历树的遍历v后根遍历后根遍历若树非空，则遍历方法为若树非空，则遍历方法为: 先从左到右，先从左到右， 依次先根依次先根遍历根结点的每一棵子树遍历根结点的每一棵子树 再访问根结点再访问根结点 等同于转换的二叉树进行等同于转换的二叉树进行中序遍历中序遍历ACBDEFGH后根遍历序列后根遍历序列EBHFGCDAv写出树的先根遍历和后根遍历序列写出树的先根遍历和后根遍历序列先根遍历：先根遍历：RADEBCFGHK后根遍历：后根遍历：DEABGHKFCR森林的遍历森林的遍历v先序遍历先序遍历若森林非空，若森林非空， 则遍历方法为：则遍历方法为： 访问森林中第一棵树的根结点。访问森林中第一棵树的根结点。 先序遍历第一棵树的根结点的子树森林。先序遍历第一棵树的根结点的子树森林。 先序遍历除去第一棵树之后剩余的树构成的先序遍历除去第一棵树之后剩余的树构成的森林。森林。 等同于转换的二叉树进行等同于转换的二叉树进行先序遍历先序遍历先序遍历序列为先序遍历序列为ABCDEFGHIJ森林的先序遍历：森林的先序遍历：先序遍历序列为先序遍历序列为ABCDEFGHIJ森林的先序遍历等同于转换的二叉树进行森林的先序遍历