数据结构第14讲-线索树与树和森林-Cppt课件

1、第第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.2.线索链表中结点的结构线索链表中结点的结构lchildLTagdataRTag rchild其中：其中：LTag =LTag =0 lchild 0 lchild 域指示结点的左孩子域指示结点的左孩子1 lchild 1 lchild 域指示结点的前驱域指示结点的前驱RTag =RTag =0 rchild 0 rchild 域指

3、示结点的右孩子域指示结点的右孩子1 rchild 1 rchild 域指示结点的后继域指示结点的后继二叉树二叉线索存储表示二叉树二叉线索存储表示typedef enum Link, Thread PointerThr; typedef enum Link, Thread PointerThr; / Link=0: / Link=0:指针，指针，Thread=1:Thread=1:线索线索typedef struct BiThrNodetypedef struct BiThrNode TElemType data; TElemType data; Struct BiThrNode Struct

4、BiThrNode * *lchild, lchild, * *rchild;rchild; / / 左右孩子指针左右孩子指针 PointerThr LTag, RTag; / PointerThr LTag, RTag; / 左右标志左右标志 BiThrNode, BiThrNode, * *BiThrTree;BiThrTree;3.3.线索二叉树图例线索二叉树图例 线索二叉树及其存储结构线索二叉树及其存储结构 （a a中序线索二叉树中序线索二叉树 （b b中序线索链表中序线索链表12345670 1 00 2 01 3 11 4 10 5 01 6 11 7 1thrt0 1如何在线索树

5、中找结点的后继？如何在线索树中找结点的后继？结合中序线索树结合中序线索树 若其右标志为若其右标志为“1”1”，右链是线索，右链直接，右链是线索，右链直接指示了结点的后继；指示了结点的后继； 若其右标志为若其右标志为“0”0”，右链是指针，其后继为，右链是指针，其后继为右子树中最左下的结点。右子树中最左下的结点。1234567如何在线索树中找结点的前驱？如何在线索树中找结点的前驱？结合中序线索树结合中序线索树 若其左标志为若其左标志为“1”1”，左链为线索，直接指示，左链为线索，直接指示其前驱；其前驱； 若其左标志为若其左标志为“0”0”，左子树中最右下的结点，左子树中最右下的结点为其前驱。为其

6、前驱。1234567线索链表的中序遍历算法线索链表的中序遍历算法Status IOTraver_T( BiThrTree T,Status Status IOTraver_T( BiThrTree T,Status ( (* *Visit)(TElemType e) )Visit)(TElemType e) ) /T /T指向头结点，头结点的左链指向头结点，头结点的左链lchildlchild指向根结点，指向根结点，中序遍历中序遍历 /二叉线索树二叉线索树T T的非递归算法，对每个数据元素调用的非递归算法，对每个数据元素调用函数函数VisitVisit。 p = T-lchild; /pp =

7、 T-lchild; /p指向根结点指向根结点 while (p != T) /while (p != T) /空树或遍历结束时，空树或遍历结束时，p = p = = T= T while (p-LTag=Link) p = p-lchild; while (p-LTag=Link) p = p-lchild; if (!Visit(p-data) return ERROR; / if (!Visit(p-data) return ERROR; /访访问其左子树为空的结点问其左子树为空的结点 while (p-RTag=Thread & p-rchild!=T) while (p-RT

8、ag=Thread & p-rchild!=T) p = p-rchild; Visit(p-data); / p = p-rchild; Visit(p-data); /访问后继结点访问后继结点 p = p-rchild; p = p-rchild; return OK; return OK; / IOTraver_T / IOTraver_T0 1 00 2 01 3 11 4 10 5 01 6 11 7 1T0 1 14.4.如何建立线索化链表？如何建立线索化链表？ 由于线索化的实质是将二叉链表中的空指由于线索化的实质是将二叉链表中的空指针改为指向前驱或后继的线索，而前驱或后继

9、针改为指向前驱或后继的线索，而前驱或后继的信息只有在遍历时才能得到，因此线索化的的信息只有在遍历时才能得到，因此线索化的过程即为在遍历的过程中修改空指针的过程。过程即为在遍历的过程中修改空指针的过程。对二叉链表对二叉链表p p进行中序线索化的递归算法进行中序线索化的递归算法( (带头结点带头结点) )Status InOrderThreading(BiThrTree &Thrt,BiThrTree T)Status InOrderThreading(BiThrTree &Thrt,BiThrTree T)步骤：步骤：1. 1. 生成头结点生成头结点ThrtThrt，如果树非空，

10、头结点指向树根，否，如果树非空，头结点指向树根，否则，回指自身；则，回指自身；2. pre = Thrt; 2. pre = Thrt; 调用不带头结点的中序线索化的递归调用不带头结点的中序线索化的递归算法算法; ;3.3.最后一个结点线索化指向头结点）最后一个结点线索化指向头结点）void InThreading(BiThrTree p)void InThreading(BiThrTree p)if (p)if (p)InThreading(p-lchild); /InThreading(p-lchild); /左子树线索化左子树线索化if (!p-lchild) p-lchild=pre;

11、 p-ltag=Thread;if (!p-lchild) p-lchild=pre; p-ltag=Thread; / /前驱线索前驱线索if (!pre-rchild)pre-rchild=p;pre-rtag=Thread;if (!pre-rchild)pre-rchild=p;pre-rtag=Thread; / /后继线索后继线索 pre = p; /pre = p; /保持保持prepre指向指向p p的前驱的前驱 InThreading(p-rchild);InThreading(p-rchild); /右子树线索化右子树线索化 InThreadingInThreading对二

12、叉链表对二叉链表p p进行中序线索化的递归算法进行中序线索化的递归算法( (不带头结点不带头结点) )0 1 00 2 0 3 40 5 0 6 7 pre0 1pStatus InOrderThreading(BiThrTree &Thrt,BiThrTree T)Status InOrderThreading(BiThrTree &Thrt,BiThrTree T)/中序遍历二叉树中序遍历二叉树T T，并将其中序线索化，并将其中序线索化，ThrtThrt指向头结点。指向头结点。 Thrt=(BiThrTree)malloc(sizeof(BiThrNode);Thrt=(B

13、iThrTree)malloc(sizeof(BiThrNode); if (!Thrt) exit(OVERFLOW); if (!Thrt) exit(OVERFLOW); Thrt-ltag=Link; Thrt-ltag=Link;Thrt-rtag=Thread; /Thrt-rtag=Thread; /建立头结点建立头结点 Thrt-rchild=Thrt;Thrt-rchild=Thrt; if (!T) Thrt-lchild=Thrt; / if (!T) Thrt-lchild=Thrt; /空树，左指针回指自身空树，左指针回指自身 else /else /二叉树不为空树，

14、进行线索化二叉树不为空树，进行线索化 Thrt-lchild=T; /Thrt-lchild=T; /头结点的头结点的lchildlchild指向二叉链表根指向二叉链表根 pre=Thrt; /prepre=Thrt; /pre指向前驱结点指向前驱结点 InThreading(T);InThreading(T);/中序线索化二叉链表中序线索化二叉链表T T pre-rchild=Thrt; pre-rchild=Thrt;pre-rtag=Thread; pre-rtag=Thread; / /最后一个结点线索化最后一个结点线索化 Thrt-rchild=pre; Thrt-rchild=pr

15、e; return OK; return OK; Status InOrderThreading(BiThrTree &Thrt,BiThrTree T)Status InOrderThreading(BiThrTree &Thrt,BiThrTree T) Thrt=(BiThrTree)malloc(sizeof(BiThrNode); Thrt=(BiThrTree)malloc(sizeof(BiThrNode); if (!Thrt) exit(OVERFLOW);if (!Thrt) exit(OVERFLOW); Thrt-ltag=Link; Thrt-rtag

16、=Thread; Thrt-ltag=Link; Thrt-rtag=Thread; Thrt-rchild=Thrt; Thrt-rchild=Thrt; if (!T) Thrt-lchild=Thrt; / if (!T) Thrt-lchild=Thrt; /空树，空树，ThrtThrt回指自身回指自身 ThrtLinkThread1elseelse Thrt-lchild=T;/ Thrt-lchild=T;/头结点的头结点的lchildlchild指向二叉链表根指向二叉链表根 pre=Thrt; /prepre=Thrt; /pre指向前驱结点指向前驱结点 InThreading(

17、T);InThreading(T);/中序线索化二叉链表中序线索化二叉链表T T pre-rchild=Thrt; pre-rchild=Thrt;pre-rtag=Thread; pre-rtag=Thread; / /最后一个结点线索化最后一个结点线索化 Thrt-rchild=pre;Thrt-rchild=pre; return OK;return OK; Thrt A B D C Epre输出：输出：B C A E D1 10111110000preP=nullTABDECFG例：对下图的树按先序、后序、中序线索化例：对下图的树按先序、后序、中序线索化第第6 6章章 树和二叉树树和二

18、叉树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 树的存储结构树的存储结构三种常用的链表结构：三种常用的链表结构：双亲表示法双亲表示法孩子表示法孩子表示法孩子兄弟表示法孩子兄弟表示法1. 1. 双亲表示法双亲表示法即以一组连续空间存储树

19、的结点，即以一组连续空间存储树的结点，同时在每个结点中附设一个指示器同时在每个结点中附设一个指示器指示其双亲结点在链表中的位置。指示其双亲结点在链表中的位置。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 typedef struct PTN

20、ode /typedef struct PTNode /结点结构结点结构 Elem data;Elem data; int parent; / int parent; / 双亲位置域双亲位置域 PTNode; PTNode;typedef struct /typedef struct /树结构树结构 PTNode nodesMAX_TREE_SIZE;PTNode nodesMAX_TREE_SIZE; int r, n; / int r, n; / 根结点的位置和结点个根结点的位置和结点个数数 PTree; PTree;分析：分析： 这种存储结构利用每个结点除根结点这种存储结构利用每个结点除

21、根结点只有唯一双亲的性质，只有唯一双亲的性质，Parent(T,xParent(T,x操作可在操作可在常量时间内实现。反复调用常量时间内实现。反复调用ParentParent操作，直到操作，直到遇见无双亲的结点时，便找到了树的根。但在遇见无双亲的结点时，便找到了树的根。但在这种表示方式中，求结点的孩子时需遍历整个这种表示方式中，求结点的孩子时需遍历整个结构。结构。2. 2. 孩子表示法孩子表示法 由于树中每个结点可能有多棵子树，由于树中每个结点可能有多棵子树，则考虑用多重链表，即结点有多个指针则考虑用多重链表，即结点有多个指针域，其中每个指针指向一棵子树的根结域，其中每个指针指向一棵子树的根结

22、点，此时链表中的结点可以有如下两种点，此时链表中的结点可以有如下两种结点格式：结点格式：datadatadegreedegreechild1child1child2child2childchildd dy ydatadatachild1child1child2child2childchildd dx x采用第一种格式采用第一种格式 多重链表中的结点是同构的，其中多重链表中的结点是同构的，其中 dx dx 为树为树的度。由于树中很多结点的度小于的度。由于树中很多结点的度小于 dx dx ，所以链，所以链表中有很多空链域，造成空间浪费。表中有很多空链域，造成空间浪费。datadatachild1c

23、hild1child2child2childchildd dx x采用第二种格式采用第二种格式 多重链表中的结点是不同构的，其中多重链表中的结点是不同构的，其中 dy dy 为为结点的度，结点的度，drgee drgee 域的值同域的值同 dy dy ，此时可以节省，此时可以节省存储空间，但操作不方便。存储空间，但操作不方便。datadatadegreedegreechild1child1child2child2childchildd dy y有没有既能节省空间有没有既能节省空间又操作方便的办法呢？又操作方便的办法呢？另一种方式另一种方式 把每个结点的孩子结点排列起来，看成是一把每个结点的孩子

24、结点排列起来，看成是一个线性表，且以单链表作存储结构，那么个线性表，且以单链表作存储结构，那么 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树的孩子链表存储表示树的孩子链表存储表示typ

25、edef struct CTNode /typedef struct CTNode /孩子结点孩子结点 int child;int child; struct CTNode struct CTNode * *next; next; * *ChildPtr;ChildPtr;typedef struct typedef struct /双亲结点结构双亲结点结构 Elem data; Elem data; ChildPtr firstchild; / ChildPtr firstchild; / 孩子链的头指孩子链的头指针针 CTBox; CTBox;typedef struct /typedef

26、 struct /树结构树结构: : CTBox nodesMAX_TREE_SIZE; CTBox nodesMAX_TREE_SIZE; int n, r; / int n, r; / 结点数和根结点的位置结点数和根结点的位置 CTree; CTree;分析：分析： 与双亲表示法相反，孩子表示法便于涉及与双亲表示法相反，孩子表示法便于涉及孩子的操作实现，却不适用于孩子的操作实现，却不适用于Parent(TParent(T，x)x)操操作。可根据某种需要，将二者结合起来，即带作。可根据某种需要，将二者结合起来，即带双亲的孩子链表。双亲的孩子链表。3. 3. 孩子兄弟表示法孩子兄弟表示法 或称

27、二叉树表示法，或称二叉链表表或称二叉树表示法，或称二叉链表表示法。即以二叉链表作树的存储结构。链示法。即以二叉链表作树的存储结构。链表中结点的两个链域分别指向该结点的第表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。一个孩子结点和下一个兄弟结点。REKCFABGHDD DA AC CR RE EB BF FH HG GK K3. 3. 孩子兄弟表示法孩子兄弟表示法例：例：树的二叉链表孩子树的二叉链表孩子 - - 兄弟存储表示兄弟存储表示typedef struct CSNode typedef struct CSNode Elem data; Elem data; struc

28、t CSNode struct CSNode * *firstchild ,firstchild , * *nextsibling;nextsibling; CSNode, CSNode, * *CSTree;CSTree;分析：分析： 这种存储结构便于实现各种树的操作。首这种存储结构便于实现各种树的操作。首先易于实现找结点孩子等的操作。如果为每个先易于实现找结点孩子等的操作。如果为每个结点增设一个结点增设一个(parent)(parent)域，则同样能方便地实域，则同样能方便地实现现Parent(T,x)Parent(T,x)操作。操作。6.4.2 6.4.2 森林和二叉树的转换森林和二叉树

29、的转换1. 1. 树和二叉树的对应关系树和二叉树的对应关系 由于二叉树和树都可用二叉链表作为由于二叉树和树都可用二叉链表作为存储结构，则以二叉链表作为媒介可导出存储结构，则以二叉链表作为媒介可导出树与二叉树之间的一个对应关系。树与二叉树之间的一个对应关系。树转换为二叉树方法：树转换为二叉树方法：1 1对每个孩子进行从左到右的排序；对每个孩子进行从左到右的排序；2 2在兄弟之间加一条连线；在兄弟之间加一条连线；3 3对每个结点，除了左孩子外，去除其与其余对每个结点，除了左孩子外，去除其与其余孩子之间的联系；孩子之间的联系； 4 4以根结点为轴心，将整个树顺时针转以根结点为轴心，将整个树顺时针转4

30、545。ABCDEGHFIa aABCDEGHFIb bABCDEGHFIc cABCDEGHFId d2. 2. 森林和二叉树的对应关系森林和二叉树的对应关系 从树的二叉链表表示的定义可知，任从树的二叉链表表示的定义可知，任何一棵和树对应的二叉树，其右子树必空。何一棵和树对应的二叉树，其右子树必空。 若把森林中第二棵树的根结点看成是若把森林中第二棵树的根结点看成是第一棵树的根结点的兄弟，则同样可导出第一棵树的根结点的兄弟，则同样可导出森林和二叉树的对应关系。森林和二叉树的对应关系。BCDEGHFIa aBCDEGHFIb bBCDEGHFIc cBCDEGHFId d已知条件：森林和二叉树的

31、对应关系设已知条件：森林和二叉树的对应关系设 森森 林林 F = ( T1, T2, , Tn ); F = ( T1, T2, , Tn ); T1 = (root T1 = (root，t11, t12, , t1m); t11, t12, , t1m); 二叉树二叉树 B =( LBT, Node(root), RBT );B =( LBT, Node(root), RBT );由森林转换成二叉树的转换规则为由森林转换成二叉树的转换规则为: :假设假设 F = F = ，那么，那么 B = ;B = ;否则，由否则，由 Root( T1 ) Root( T1 ) 对应得到对应得到 Nod

32、e(root);Node(root); 由由 (t11, t12, , t1m ) (t11, t12, , t1m ) 对应得到对应得到 LBT;LBT; 由由 (T2, T3, Tn ) (T2, T3, Tn ) 对应得到对应得到 RBTRBT。由二叉树转换为森林的转换规则为由二叉树转换为森林的转换规则为: :假设假设 B = , B = , 那么那么 F = ;F = ;否则，由否则，由 Node(root) Node(root) 对应得到对应得到 Root( T1 );Root( T1 ); 由由LBT LBT 对应得到对应得到 ( t11, t12, ( t11, t12, ，t1

33、m);T1t1m);T1除根以外除根以外所所 构成的森林构成的森林 由由RBT RBT 对应得到对应得到 (T2, T3, , Tn)(T2, T3, , Tn)；除；除T1T1之外的森之外的森林林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.森林的遍历森林的遍历先序遍历先序遍历( (对森林中的每