第第6 6章章 树和二叉树树和二叉树6.1 6.1 树的定义和基本术语树的定义和基本术语6.2 6.2 二叉树二叉树6.3 6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树 6.3.1 6.3.1 遍历二叉树遍历二叉树 6.3.2 6.3.2 线索二叉树线索二叉树6.4 6.4 树和森林树和森林6.6 6.6 赫夫曼树及其应用赫夫曼树及其应用6.3.2 6.3.2 线索二叉树线索二叉树1.1.何谓线索二叉树？何谓线索二叉树？ 遍历结果是求得结点的一个线性序列。指向遍历结果是求得结点的一个线性序列。指向该线性序列该线性序列“前驱前驱”和和“后继后继”的指针，称的指针，称“线线索索”；包含；包含“线索线索”的存储结构，称为的存储结构，称为“线索链线索链表表”；与其相应的二叉树，称为；与其相应的二叉树，称为“线索二叉树线索二叉树”；对二叉树以某种次序遍历，使其变为线索二叉；对二叉树以某种次序遍历，使其变为线索二叉树的过程，称为树的过程，称为“线索化线索化”。2.2.线索链表中结点的结构线索链表中结点的结构在二叉链表的结点结构中增加两个在二叉链表的结点结构中增加两个在二叉链表的结点结构中增加两个在二叉链表的结点结构中增加两个标志域标志域，并，并，并，并规定：规定：规定：规定：lchildLTagdataRTag rchild其中：其中：LTagLTag = =0 0 lchildlchild 域指示结点的左孩子域指示结点的左孩子1 1 lchildlchild 域指示结点的前驱域指示结点的前驱RTagRTag = =0 0 rchildrchild 域指示结点的右孩子域指示结点的右孩子1 1 rchildrchild 域指示结点的后继域指示结点的后继二叉树二叉线索存储表示二叉树二叉线索存储表示typedeftypedef enumenum Link, Thread Link, Thread PointerThrPointerThr; ; / Link=0:/ Link=0:指针，指针，Thread=1:Thread=1:线索线索typedeftypedef structstruct BiThrNodeBiThrNode TElemTypeTElemType data; data; StructStruct BiThrNodeBiThrNode * *lchildlchild, *, *rchildrchild; ; / / 左右孩子指针左右孩子指针 PointerThrPointerThr LTagLTag, , RTagRTag; ; / / 左右标志左右标志 BiThrNodeBiThrNode, *, *BiThrTreeBiThrTree; ;3.3.线索二叉树图例线索二叉树图例 线索二叉树及其存储结构线索二叉树及其存储结构 （a a）中序线索二叉树）中序线索二叉树 （b b）中序线索链表中序线索链表12345670 1 00 2 01 3 11 4 10 5 01 6 11 7 1thrt0 1如何在线索树中找结点的后继？如何在线索树中找结点的后继？结合中序线索树结合中序线索树 若其右标志为若其右标志为“1”1”，右链是线索，右链直接，右链是线索，右链直接指示了结点的后继；指示了结点的后继； 若其右标志为若其右标志为“0”0”，右链是指针，其后继为，右链是指针，其后继为右子树中最左下的结点。右子树中最左下的结点。1234567如何在线索树中找结点的前驱？如何在线索树中找结点的前驱？结合中序线索树结合中序线索树 若其左标志为若其左标志为“1”1”，左链为线索，直接指示，左链为线索，直接指示其前驱；其前驱； 若其左标志为若其左标志为“0”0”，左子树中最右下的结点，左子树中最右下的结点为其前驱。为其前驱。1234567线索链表的中序遍历算法线索链表的中序遍历算法Status Status IOTraver_TIOTraver_T( ( BiThrTreeBiThrTree T,StatusT,Status (* (*Visit)(TElemTypeVisit)(TElemType e) ) e) ) /T/T指向头结点，头结点的左链指向头结点，头结点的左链lchildlchild指向根结点，中序遍历指向根结点，中序遍历 /二叉线索树二叉线索树T T的非递归算法，对每个数据元素调用函数的非递归算法，对每个数据元素调用函数VisitVisit。 p = T-p = T-lchildlchild; ; /p/p指向根结点指向根结点 while (p != T) while (p != T) /空树或遍历结束时，空树或遍历结束时，p = = Tp = = T while (p- while (p-LTagLTag=Link) p = p-Link) p = p-lchildlchild; ; if (!Visit(p-data) return ERROR; if (!Visit(p-data) return ERROR; /访问其左子树为空的结点访问其左子树为空的结点 while (p-while (p-RTagRTag=Thread & p-Thread & p-rchildrchild!=T) !=T) p = p- p = p-rchildrchild; Visit(p-data); ; Visit(p-data); /访问后继结点访问后继结点 p = p-p = p-rchildrchild; ; return OK; return OK; / / IOTraver_TIOTraver_T0 1 00 2 01 3 11 4 10 5 01 6 11 7 1T0 1 14.4.如何建立线索化链表？如何建立线索化链表？ 由于由于线索化的实质线索化的实质是将二叉链表中的空指是将二叉链表中的空指针改为指向前驱或后继的线索，而前驱或后继针改为指向前驱或后继的线索，而前驱或后继的信息只有在遍历时才能得到，因此线索化的的信息只有在遍历时才能得到，因此线索化的过程即为过程即为在遍历的过程中修改空指针的过程在遍历的过程中修改空指针的过程。对二叉链表对二叉链表p p进行中序线索化的递归算法进行中序线索化的递归算法( (带头结点带头结点) )Status Status InOrderThreading(BiThrTreeInOrderThreading(BiThrTree & &Thrt,BiThrTreeThrt,BiThrTree T) T)步骤：步骤：1. 1. 生成头结点生成头结点ThrtThrt，如果树非空，头结点指向树根，否如果树非空，头结点指向树根，否则，回指自身；则，回指自身；2. pre = 2. pre = ThrtThrt; ; 调用不带头结点的中序线索化的递归调用不带头结点的中序线索化的递归算法算法; ;3.3.最后一个结点线索化（指向头结点）最后一个结点线索化（指向头结点）void void InThreading(BiThrTreeInThreading(BiThrTree p) p)if (p)if (p)InThreading(pInThreading(p-lchildlchild);); /左子树线索化左子树线索化if (!p-if (!p-lchildlchild) p-) p-lchildlchild=pre; p-=pre; p-ltagltag=Thread;=Thread; / /前驱线索前驱线索if (!pre-if (!pre-rchild)prerchild)pre-rchildrchild= =p;prep;pre- - rtagrtag=Thread;=Thread; / /后继线索后继线索 pre = p; pre = p; /保持保持prepre指向指向p p的前驱的前驱 InThreading(pInThreading(p-rchildrchild);); /右子树线索化右子树线索化 InThreadingInThreading对二叉链表对二叉链表p p进行中序线索化的递归算法进行中序线索化的递归算法( (不带头结点不带头结点) )0 1 00 2 0 3 40 5 0 6 7 pre0 1pStatus Status InOrderThreading(BiThrTreeInOrderThreading(BiThrTree & &Thrt,BiThrTreeThrt,BiThrTree T) T)/中序遍历二叉树中序遍历二叉树T T，并将其中序线索化，并将其中序线索化，ThrtThrt指向头结点。指向头结点。 ThrtThrt=(=(BiThrTree)malloc(sizeof(BiThrNodeBiThrTree)malloc(sizeof(BiThrNode);); if (!Thrt) exit(OVERFLOW); if (!Thrt) exit(OVERFLOW); ThrtThrt-ltagltag=Link;=Link;Thrt-Thrt-rtagrtag=Thread; =Thread; /建立头结点建立头结点 ThrtThrt-rchildrchild= =ThrtThrt; ; if (!T) if (!T) ThrtThrt-lchildlchild= =ThrtThrt; ; /空树，左指针回指自身空树，左指针回指自身 else else /二叉树不为空树，进行线索化二叉树不为空树，进行线索化 ThrtThrt-lchildlchild=T; =T; /头结点的头结点的lchildlchild指向二叉链表根指向二叉链表根 pre=pre=ThrtThrt; ; /pre/pre指向前驱结点指向前驱结点 InThreading(TInThreading(T) ); ;/中序线索化二叉链表中序线索化二叉链表T T pre- pre-rchildrchild=Thrt;=Thrt;pre-pre-rtagrtag=Thread; =Thread; /最后一个结点线索化最后一个结点线索化 ThrtThrt-rchildrchild=pre; =pre; return OK; return OK; Status Status InOrderThreading(BiThrTreeInOrderThreading(BiThrTree & &Thrt,BiThrTreeThrt,BiThrTree T) T) ThrtThrt=(=(BiThrTree)malloc(sizeof(BiThrNodeBiThrTree)malloc(sizeof(BiThrNode);); if (!if (!ThrtThrt) ) exit(OVERFLOWexit(OVERFLOW);); ThrtThrt-ltagltag=Link; =Link; ThrtThrt-rtagrtag=Thread;=Thread; ThrtThrt-rchildrchild= =ThrtThrt; ; if (!T) if (!T) ThrtThrt-lchildlchild= =ThrtThrt; ; /空树，空树，ThrtThrt回指自身回指自身 ThrtLinkThread1elseelse ThrtThrt-lchildlchild=T;=T;/头结点的头结点的lchildlchild指向二叉链表根指向二叉链表根 pre=pre=ThrtThrt; ; /pre/pre指向前驱结点指向前驱结点 InThreading(TInThreading(T););/中序线索化二叉链表中序线索化二叉链表T T pre- pre-rchildrchild=Thrt;=Thrt;pre-pre-rtagrtag=Thread; =Thread; /最后一个结点线索化最后一个结点线索化 ThrtThrt-rchildrchild=pre;=pre; return OK;return OK; Thrt A B D C Epre输出：输出：B C A E D1 10111110000preP=nullTABDECFG例：对下图的树按先序、后序、中序线索化例：对下图的树按先序、后序、中序线索化第第6 6章章 树和二叉树树和二叉树6.1 6.1 树的定义和基本术语树的定义和基本术语6.2 6.2 二叉树二叉树6.3 6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树6.4 6.4 树和森林树和森林 6.4.1 6.4.1 树的存储结构树的存储结构 6.4.2 6.4.2 森林与二叉树的转换森林与二叉树的转换 6.4.3 6.4.3 树和森林的遍历树和森林的遍历6.6 6.6 赫夫曼树及其应用赫夫曼树及其应用6.4.1 6.4.1 树的存储结构树的存储结构三种常用的链表结构：三种常用的链表结构：n双亲表示法双亲表示法n孩子表示法孩子表示法n孩子兄弟表示法孩子兄弟表示法1.1. 双亲表示法双亲表示法即以一组即以一组连续空间连续空间存储树的结点，存储树的结点，同时在每个结点中附设一个同时在每个结点中附设一个指示器指示器指示其双亲结点在链表中的位置。指示其双亲结点在链表中的位置。D DA AC CR RE EB BF FH HG GK K双亲双亲结点结点下标下标9 98 87 76 65 54 43 32 21 10 06 66 66 63 31 11 10 00 00 0-1-1K KH HG GF FE ED DC CB BA AR R树的双亲表存储表示树的双亲表存储表示#define MAX_TREE_SIZE 100 #define MAX_TREE_SIZE 100 typedeftypedef structstruct PTNodePTNode /结点结构结点结构 Elem data;Elem data; intint parent; parent; / / 双亲位置域双亲位置域 PTNodePTNode; ;typedeftypedef structstruct /树结构树结构 PTNodePTNode nodesMAX_TREE_SIZE; nodesMAX_TREE_SIZE; intint r, n; r, n; / / 根结点的位置和结点个数根结点的位置和结点个数 PTreePTree; ;分析：分析： 这种存储结构利用每个结点（除根结点）这种存储结构利用每个结点（除根结点）只有唯一双亲的性质，只有唯一双亲的性质，Parent(T,xParent(T,x）操作可在操作可在常量时间内实现。反复调用常量时间内实现。反复调用ParentParent操作，直到操作，直到遇见无双亲的结点时，便找到了树的根。但在遇见无双亲的结点时，便找到了树的根。但在这种表示方式中，这种表示方式中，求结点的孩子时需遍历整个求结点的孩子时需遍历整个结构结构。2. 2. 孩子孩子表示法表示法 由于树中每个结点可能有多棵子树，则考由于树中每个结点可能有多棵子树，则考虑用虑用多重链表多重链表，即结点有多个指针域，其中每，即结点有多个指针域，其中每个指针指向一棵子树的根结点，此时链表中的个指针指向一棵子树的根结点，此时链表中的结点可以有如下两种结点格式：结点可以有如下两种结点格式：datadatadegreedegreechild1child1child2child2childchildd dy ydatadatachild1child1child2child2childchildd dx x采用第一种格式采用第一种格式 多重链表中的结点是多重链表中的结点是同构同构的，其中的，其中 d dx x 为树为树的度。由于树中很多结点的度小于的度。由于树中很多结点的度小于 d dx x ，所以链所以链表中有很多空链域，造成表中有很多空链域，造成空间浪费空间浪费。datadatachild1child1child2child2childchildd dx x采用第二种格式采用第二种格式 多重链表中的结点多重链表中的结点是是不同构不同构的的，其中，其中 d dy y 为为结点的度，结点的度，drgeedrgee 域的值同域的值同 d dy y ，此时可以节省，此时可以节省存储空间，但操作不方便。存储空间，但操作不方便。datadatadegreedegreechild1child1child2child2childchildd dy y有没有既能节省空间有没有既能节省空间又操作方便的办法呢？又操作方便的办法呢？另一种方式另一种方式 把每个结点的孩子结点排列起来，看成是一把每个结点的孩子结点排列起来，看成是一个线性表，且以单链表作存储结构，则个线性表，且以单链表作存储结构，则 n n个结点个结点有有 n n 个孩子链表（叶子的孩子链表为空个孩子链表（叶子的孩子链表为空) )。而。而 n n 个头指针又组成一个线性表，为便于查找，采用个头指针又组成一个线性表，为便于查找，采用顺序存储结构。顺序存储结构。3 36 65 51 12 20 07 78 89 9K KH HG GE EF FR RD DC CB BA A0 01 12 23 34 45 56 67 78 89 9D DA AC CR RE EB BF FH HG GK K树的孩子链表存储表示树的孩子链表存储表示typedeftypedef structstruct CTNodeCTNode /孩子结点孩子结点 intint child; child; structstruct CTNodeCTNode *next; *next; * *ChildPtrChildPtr; ;typedeftypedef structstruct /双亲结点结构双亲结点结构 Elem data; Elem data; ChildPtrChildPtr firstchildfirstchild; ; / / 孩子链的头指针孩子链的头指针 CTBoxCTBox; ;typedeftypedef structstruct /树结构树结构: : CTBoxCTBox nodesMAX_TREE_SIZE; nodesMAX_TREE_SIZE; intint n, r; n, r; / / 结点数和根结点的位置结点数和根结点的位置 CTreeCTree; ; ; ;分析：分析： 与双亲表示法相反，孩子表示法便于涉及与双亲表示法相反，孩子表示法便于涉及孩子的操作实现，却不适用于孩子的操作实现，却不适用于Parent(TParent(T，x)x)操操作。可根据某种需要，将二者结合起来，即带作。可根据某种需要，将二者结合起来，即带双亲的孩子链表。双亲的孩子链表。3. 3. 孩子兄弟孩子兄弟表示法表示法 或称二叉树表示法，或称二叉链表表示法。或称二叉树表示法，或称二叉链表表示法。即以二叉链表作树的存储结构。链表中结点的即以二叉链表作树的存储结构。链表中结点的两两个链域个链域分别指向该结点的分别指向该结点的第一个孩子结点第一个孩子结点和和下一下一个兄弟结点个兄弟结点。REKCFABGHDD DA AC CR RE EB BF FH HG GK K3. 3. 孩子兄弟孩子兄弟表示法表示法例：例：树的二叉链表（孩子树的二叉链表（孩子 - - 兄弟）存储表示兄弟）存储表示typedeftypedef structstruct CSNodeCSNode Elem data; Elem data; structstruct CSNodeCSNode * *firstchildfirstchild , , * *nextsiblingnextsibling; ; CSNodeCSNode, *, *CSTreeCSTree; ;分析：分析： 这种存储结构便于实现各种树的操作。首这种存储结构便于实现各种树的操作。首先易于实现找结点孩子等的操作。如果为每个先易于实现找结点孩子等的操作。如果为每个结点增设一个结点增设一个(parent)(parent)域，则同样能方便地实域，则同样能方便地实现现Parent(T,x)Parent(T,x)操作。操作。6.4.2 6.4.2 森林和二叉树的转换森林和二叉树的转换1. 1. 树和二叉树的对应关系树和二叉树的对应关系 由于二叉树和树都可用二叉链表作为存储结由于二叉树和树都可用二叉链表作为存储结构，则以二叉链表作为媒介可导出树与二叉树之构，则以二叉链表作为媒介可导出树与二叉树之间的一个对应关系。间的一个对应关系。树转换为二叉树树转换为二叉树方法：方法：1 1）对每个孩子进行从左到右的排序；）对每个孩子进行从左到右的排序；2 2）在兄弟之间加一条连线；）在兄弟之间加一条连线；3 3）对每个结点，除了左孩子外，去除其与其余）对每个结点，除了左孩子外，去除其与其余孩子之间的联系；孩子之间的联系； 4 4）以根结点为轴心，将整个树顺时针转）以根结点为轴心，将整个树顺时针转4545。ABCDEGHFIa aABCDEGHFIb bABCDEGHFIc cABCDEGHFId d2. 2. 森林和二叉树的对应关系森林和二叉树的对应关系 从树的二叉链表表示的定义可知，任何一棵从树的二叉链表表示的定义可知，任何一棵和树对应的二叉树，其和树对应的二叉树，其右子树必空右子树必空。 若把森林中第二棵树的根结点看成是第一棵若把森林中第二棵树的根结点看成是第一棵树的根结点的兄弟，则同样可导出森林和二叉树树的根结点的兄弟，则同样可导出森林和二叉树的对应关系。的对应关系。BCDEGHFIa aBCDEGHFIb bBCDEGHFIc cBCDEGHFId d已知条件：森林和二叉树的对应关系设已知条件：森林和二叉树的对应关系设 森森 林林 F = ( TF = ( T1 1, T, T2 2, , , , T Tn n ); ); T T1 1 = (root = (root，t t1111, t, t1212, , t, , t1m1m); ); 二叉树二叉树 B =( LBT, Node(root), RBT );B =( LBT, Node(root), RBT );由森林转换成二叉树的转换规则为由森林转换成二叉树的转换规则为: :若若 F = F = ，则则 B = ;B = ;否则，由否则，由 Root( TRoot( T1 1 ) ) 对应得到对应得到 Node(root);Node(root); 由由 (t(t1111, t, t1212, , , t, t1m1m ) ) 对应得到对应得到 LBT;LBT; 由由 (T(T2 2, T, T3 3, , , T Tn n ) ) 对应得到对应得到 RBTRBT。由二叉树转换为森林的转换规则为由二叉树转换为森林的转换规则为: :若若 B = , B = , 则则 F = ;F = ;否则，由否则，由 Node(root) Node(root) 对应得到对应得到 Root( TRoot( T1 1 ); ); 由由LBT LBT 对应得到对应得到 ( t( t1111, t, t1212, , ，t t1m1m);T);T1 1除根以外所除根以外所 构成的森林构成的森林 由由RBT RBT 对应得到对应得到 (T(T2 2, T, T3 3, , , , T Tn n) )；除；除T T1 1之外的森林之外的森林6.4.3 6.4.3 树和森林的遍历树和森林的遍历1. 1. 树的遍历树的遍历：有三条搜索路径：有三条搜索路径先根先根( (序序) )遍历：遍历：若树不空，则先访问根结点，若树不空，则先访问根结点， 然后依次先根遍历各棵子树。然后依次先根遍历各棵子树。后根后根( (序序) )遍历：遍历：若树不空，则先依次后根遍历若树不空，则先依次后根遍历 各棵子树，然后访问根结点。各棵子树，然后访问根结点。按层次遍历：按层次遍历： 若树不空，则自上而下自左至若树不空，则自上而下自左至 右访问树中每个结点。右访问树中每个结点。例例对树进行先根遍历，获得的先根序列是：对树进行先根遍历，获得的先根序列是：对树进行后根遍历，获得的后根序列是：对树进行后根遍历，获得的后根序列是：ABCDEGHFIA B E F C D G H IA B E F C D G H IE F B C G H I D AE F B C G H I D A2.2.森林的遍历森林的遍历先序遍历先序遍历( (对森林中的每一棵树进行先根遍历对森林中的每一棵树进行先根遍历) ) 1 1）若森林不空，访问森林中第一棵树的根结点若森林不空，访问森林中第一棵树的根结点； 2 2）先序遍历森林中第一棵树的子树森林先序遍历森林中第一棵树的子树森林； 3 3）先序遍历森林中先序遍历森林中( (除第一棵树外除第一棵树外) )其余树构成的森林其余树构成的森林。后序遍历后序遍历( (对森林中的每一棵树进行后根遍历对森林中的每一棵树进行后根遍历) ) 1 1）若森林不空，后序遍历森林中第一棵树的子树森林若森林不空，后序遍历森林中第一棵树的子树森林； 2 2）访问森林中第一棵树的根结点访问森林中第一棵树的根结点； 3 3）后序遍历森林中后序遍历森林中( (除第一棵树外除第一棵树外) )其余树构成的森林其余树构成的森林。例：例：对森林进行先序遍历，获得的先序序列是：对森林进行先序遍历，获得的先序序列是：对森林进行后序遍历，获得的后序序列是：对森林进行后序遍历，获得的后序序列是：BCDEGHFIB E F C D G H IB E F C D G H IE F B C G H I DE F B C G H I D总结：总结：1. 1. 二叉树的线索化二叉树的线索化2. 2. 树的表示及其遍历操作；树的表示及其遍历操作；3. 3. 建立森林与二叉树的对应关系。建立森林与二叉树的对应关系。 由于在树和森林中，一个结点的孩子的个数由于在树和森林中，一个结点的孩子的个数不定，它们在计算机中的表示以及在各种操作计不定，它们在计算机中的表示以及在各种操作计算机中的算法实现均不易实现，因此将树和森林算机中的算法实现均不易实现，因此将树和森林表示为二叉树，并将对树和森林的操作转化为对表示为二叉树，并将对树和森林的操作转化为对二叉树的操作是通常采用的方法。二叉树的操作是通常采用的方法。1 1）假设一棵二叉树的中序序列为假设一棵二叉树的中序序列为 D C B G E D C B G E A H F A H F I J K I J K 和后序序列为和后序序列为 D C E G B F H K J I A D C E G B F H K J I A 。 画出该二叉树。画出该二叉树。2 2）线索二叉树是一种（）线索二叉树是一种（ ）结构。）结构。 A A、逻辑、逻辑 B B、物理物理 C C、线性线性3 3）试找出分别满足下面条件的所有二叉树。）试找出分别满足下面条件的所有二叉树。 A A、先序序列和中序序列相同；、先序序列和中序序列相同； B B、后序序列和中序序列相同；、后序序列和中序序列相同； C C、先序序列和后序序列相同；、先序序列和后序序列相同；树和二叉树的习题树和二叉树的习题