《chap6树和二叉树_2》由会员分享，可在线阅读，更多相关《chap6树和二叉树_2（73页珍藏版）》请在金锄头文库上搜索。
1、第六章 树和二叉树,四类基本结构：,1.线性结构,2.树形结构,3.图状结构,4.集 合,本章主要内容,6.1 树的定义与基本术语6.2 二叉树6.3 二叉树的遍历与线索化6.4 树、森林和二叉树的关系6.5 哈夫曼树及其应用,6.3 二叉树的遍历与线索化,6.3.3 基于栈的递归消除 6.3.5 线索二叉树 何谓线索二叉树？ 线索链表的遍历算法 如何建立线索链表？,算法基本思想:DLR,在访问了根结点后，先序遍历左子树前,可以使用堆栈先将根结点保存在堆栈里，以便遍历完根和左子树后，可以从堆栈中弹出根结点，进而可以再先序遍历右子树。 在先序遍历左（右）子树时，可以使用相同的策略。,1.先序遍历
2、算法的非递归描述,基于栈的递归消除,1.先序遍历算法的非递归描述,基于栈的递归消除,void PreOrder(BiTree root)SqStack S;InitStack(S);BiNode *p;p=root;while(p | !StackEmpty(S)Push(S,p);p=p-lchild;elsep=p-rchild;,visit(p-data);,if(p),Pop(S,p);,/*访问根结点*/*保存根结点*/*遍历左子树*/*弹出根结点*/ /*遍历右子树*/,算法基本思想:LDR,在中序遍历左子树前，可以使用堆栈先将根结点保存在堆栈里，以便遍历完左子树后，可以从堆栈中弹
3、出根结点进行访问，进而可以再中序遍历右子树。 在中序遍历左（右）子树时，可以使用相同的策略。,2.中序遍历算法的非递归描述,基于栈的递归消除,2.中序遍历算法的非递归描述,基于栈的递归消除,void InOrder(BiTree root)SqStack S;InitStack(S);BiNode *p;p=root;while(p | !StackEmpty(S)p=p-lchild;elsep=p-rchild;,visit(p-data);,if(p),Push(S,p);,Pop(S,p);,/*保存根结点*/*遍历左子树*/*弹出根结点*/ /*访问根结点*/*遍历右子树*/,算法基
4、本思想:LRD,在后序遍历时，要求左、右子树都访问完后，最后访问根结点。如何判断当前栈顶结点的左右子树都已访问过？,3.后序遍历算法的非递归描述,基于栈的递归消除,判断刚访问过的结点q是不是当前栈顶结点p的右孩子。,？,3.后序遍历算法的非递归描述,基于栈的递归消除,判断刚访问过的结点q是不是当前栈顶结点p的右孩子。,访问根结点两个情况：p无右孩子，此时应该访问根结点；p的右孩子是刚被访问过的结点q(表明p的右子树已遍历过), 此时也应该访问根结点;除此之外，均不应该访问根结点，而是要继续进入右子树中。,3.后序遍历算法的非递归描述,基于栈的递归消除,void PostOrder(BiTree
5、 root)SqStack S;InitStack(S);BiNode *p,*q;while(p | !StackEmpty(S)p=p-lchild;elsep=p-rchild;if(p=NULL | p=q) q=p;p=NULL;,if(p),GetTop(S,p);,Push(S,p);,Pop(S,p);,p=root;q=NULL;,visit(p-data);,/*保存根结点*/*遍历左子树*/*遍历右子树*/*弹出根结点*/ /*访问根结点*/,遍历二叉树的结果是，求得结点的一个线性序列。,先序序列:中序序列:后序序列:,A B C D E F G H KB D C A H
6、 G K F ED C B H K G F E A,对线索链表中结点的约定：,若该结点的左子树不空， 则lchild域的指针指向其左子树， 且左标志域的值为“指针 Link”； 否则，lchild域的指针指向其“前驱”， 且左标志的值为“线索 Thread” 。,在二叉链表的结点中增加两个标志域, 并规定,对线索链表中结点的约定：,在二叉链表的结点中增加两个标志域, 并规定,若该结点的右子树不空， 则rchild域的指针指向其左子树， 且右标志域的值为“指针 Link”； 否则，rchild域的指针指向其“后继”， 且右标志的值为“线索 Thread” 。,如此定义的二叉树的存储结构称作“线索
7、链表”。,左孩子 左标志 数据域 右标志 右孩子,ltag(左标志域),rtag(右标志域),在二叉链表的结点中增加两个标志域, 并规定,二叉链表类型表述如下：,typedef char DataType; typedef struct Node DataType data; int ltag; int rtag; struct Node *lchild; struct Node *rchild; BiTNode, *BiTree;,结点结构:,线索: 在这种存储结构中，指向前驱和后继 结点的指针叫做线索。,线索链表: 以这种结构组成的二叉链表作为 二叉树的存储结构，叫做。,线索化: 对二叉树
8、以某种次序进行遍历并且 加上线索的过程叫做。,线索二叉树: 线索化了的二叉树称为 。,线索化实质上是将二叉链表中的空指针域填上相应结点的遍历前驱或后继结点的地址，而前驱和后继的地址只能在动态的遍历过程中才能得到。,二叉树的线索化,因此线索化的过程是在遍历过程中修改空指针域的过程。,对二叉树按照不同的遍历次序进行线索化，可以得到不同的线索二叉树 先序线索二叉树、 中序线索二叉树 后序线索二叉树,举例：,先序序列：,ABDGCEHF,NULL,中序序列：,DGBAEHCF,NULL,NULL,后序序列：,GDBHEFCA,NULL,在中序遍历过程中修改结点的左、右指针域，以保存当前访问结点的“前驱
9、”和“后继”信息。遍历过程中，附设指针pre, 并始终保持指针pre指向当前访问的、指针p所指结点的前驱。,建立线索链表,中序线索化算法,void Inthread(BiTree root) if (root-lchild=NULL) root-ltag=1; root-lchild=pre; if (pre!=NULL ,Inthread(root-lchild);,if(root!=NULL),6.4树、森林和二叉树的关系,6.4.1 树的存储结构6.4.2 树、森林与二叉树的相互转换6.4.3 树与森林的遍历,6.4.1 树的三种存储结构,一、双亲表示法,二、孩子链表表示法,三、树的二叉
10、链表(孩子-兄弟）存储表示法,以一组连续的空间存放树的结点，同时在每个结点上附设一个指示器指示其双亲结点的位置。,一、双亲表示法:,2,G,1,F,1,E,1,D,0,C,0,B,-1,A,结点序号,结点信息,双亲位置,双亲表示法类型表述如下：,#define MAX 100typedef struct TNode DataType data; int parent; TNode;typedef struct TNode treeMAX; int nodenum; /*结点数*/ParentTree;ParentTree bt;,结点结构:,结点信息,双亲位置,将每个结点的孩子结点链接构成一个
11、单链表，称为孩子链表。将孩子链表的头指针又组成了一个顺序表。,二、孩子表示法:,data,头指针,G,F,E,D,C,B,A,位置,下一个孩子,孩子链表头指针,孩子表示法类型表述如下：,typedef struct ChildNode /*孩子链表结点*/ int Child; struct ChildNode *next;ChildNode;typedef struct DataType data; ChildNode *FirstChild; DataNode;typedef struct /*树的类型定义*/ /*顺序表*/ int root; int num;ChildTree;,位置
12、,下一个孩子,结点信息,孩子链表头指针,DataNode nodesMAX;,每个结点设有两个指针域，分别指向该结点的第一个孩子和下一个兄弟（右兄弟），又称为树的二叉链表表示法。,三、孩子兄弟表示法:,第一个孩子,结点信息,下一个兄弟,孩子兄弟表示法类型表述如下：,typedef struct CSNode DataType data; struct CSNode *FirstChild; struct CSNode *NextSibling;CSNode, *CSTree;,结点结构:,第一个孩子,结点信息,下一个兄弟,每个结点设有两个指针域，分别指向该结点的第一个孩子和下一个兄弟（右兄弟）
13、，又称为树的二叉链表表示法。,三、孩子兄弟表示法:,第一个孩子,结点信息,下一个兄弟,A,B,D,E,F,C,G,树与二叉树均可用二叉链表作为存储结构，则以二叉链表为媒介可导出树与二叉树之间的一个对应关系即给定一棵树，可以找到唯一一棵二叉树与之对应。,【注意】：和树对应的二叉树，其左、右子树的概念已改变为： 左是孩子，右是兄弟。,6.4.2 树与二叉树的转换,第一个孩子,下一个兄弟,左孩子,右孩子,1、加线：在各亲兄弟之间加一虚线。2、抹线：抹掉（除第一个孩子外）该结点到其余孩子之间的连线。3、旋转：新加上去的虚线改实线且均向右斜（rchild），原有的连线均向左斜（lchild)，使之结构层
14、次分明。,一、树 二叉树,树二叉树举例：,A,B,E,D,H,C,F,G,1、加线：在各亲兄弟之间加一虚线。,2、抹线：抹掉（除第一个孩子外）该结点到其余孩子之间的连线。,3、旋转：新加上去的虚线改实线且均向右斜（rchild），原有的连线均向左斜（lchild)，使之结构层次分明。,1、将各棵树分别转换为二叉树。2、按给出森林中树的次序，依次将后一棵二叉树作为前一棵二叉树根结点的右子树，则第一棵树的根结点是转换后二叉树的根。,二、森林 二叉树,森林二叉树举例：,1、将各棵树分别转换为二叉树,2、按给出森林中树的次序，依次将后一棵二叉树作为前一棵二叉树根结点的右子树，则第一棵树的根结点是转换后二叉树的根。,A,B,D,C,F,E,G,H,I,J,前提：二叉树的根结点无右孩子1、加线：若某结点i是双亲结点的左孩子，则将该结点的右孩子以及当且仅当连续地沿着此右孩子的右链不断搜索到的所有右孩子都分别与结点i的双亲用虚线连起来。2、抹线：抹掉原二叉树中所有双亲结点 与右孩子的连线。3、归整化：将图形归整化，使各结点按层次排列且将加上去的虚线变成实线。,
