树和二叉树下部梁.ppt

第7章 树和二叉树,主讲：梁宝兰,2,教学要求： 1、理解和掌握：树的定义、术语；树的各种表示方式和存储结构；二叉树的定义、性质及其存储方法；二叉树的二叉链表存储方式、结点结构和类型定义；二叉树的三种遍历算法，能够灵活运用二叉树的遍历方法解决相关的应用问题；哈夫曼树的概念及哈夫曼编码。 2、了解：二叉树的分步遍历；二叉树的线索化方法；树与二叉树的转换；树的遍历。,第7章 树和二叉树,3,内容提要,树的逻辑结构 树的存储结构 二叉树的逻辑结构 二叉树的存储结构及实现 哈夫曼树 树、森林与二叉树的转换,本章的主要内容是,4,7.3 以结点类为基础的二叉树设计,二叉树类定义： 首先设计二叉树结点类 然后在二叉树结点类的基础上，再设计二叉树类,5,class Node friend class BTree; private: ElemType data; /数据元素值 Node *lChild; /左子树指针 Node *rChild; /右子树指针 public: Node() lChild = NULL; rChild = NULL; Node( ElemType item, Node *left = NULL,Node *right = NULL ) data = item; lChild = left; rChild = right; Node() ;,/二叉树的结点类的定义,6,class BTree private: Node* root; public: BTree(); /构造函数 void Create(int No,char data,int n); /创建二叉树 void PreOrder(Node* r, void Visit(Node*); /先序遍历 void InOrder(Node* r, void Visit(Node*); /中序遍历 void PostOrder( Node* r, void Visit(Node*); /后序遍历 void BTree:LevelOrder(Node* r, void Visit(Node*) Node* getRoot(); /获取根结点指针 ;,/ 二叉树类的定义,7,构造函数：创建一个空二叉树 获取二叉树根结点指针,BTree:BTree() root = NULL; ,Node* BTree:getRoot() return root; ,8,为了后面遍历二叉树方便，先介绍建立二叉链表的算法。,方法1：利用二叉树中结点对应与满二叉树中的层序编号进行构造：,二叉链表的建立,9,10,void BTree:Create(int No,char data,int n) Node* sMaxSize; /二叉树结点指针数组 Node *q; int i, j; for( i=0; ilChild = q; else sj-rChild = q; ,二叉树类(基本),11,方法2：利用二叉树的合并，从叶子结点开始构建二叉树,二叉链表的建立,12,/二叉树的合并 void MakeTree(const T ,13,二叉树的遍历方式： DLR、DRL、LDR、 LRD、RDL、RLD,如果限定先左后右，则二叉树遍历方式有四种： 前序：DLR 中序：LDR 后序：LRD,层序遍历：按二叉树的层序编号的次序访问各结点。,考虑二叉树的组成：,7.3.2 二叉树的遍历,14,7.3.2 二叉树的遍历,二叉树的遍历是指从根结点出发，按照某种次序访问二叉树中的所有结点，使得每个结点被访问一次且仅被访问一次。,二叉树遍历操作的结果？,15,前序（根）遍历 若二叉树为空，则空操作返回；否则： 访问根结点； 前序遍历根结点的左子树； 前序遍历根结点的右子树。,前序遍历序列：A B D G C E F,A,B,C,D,E,F,G,7.3.2 二叉树的遍历,16,前序（根）遍历过程：,A,B,C,D,E,F,G,7.3.2 二叉树的遍历,A,B,F,根,左子树,右子树,D,G,C,E,17,若二叉树为空，则空操作返回；否则： 中序遍历根结点的左子树； 访问根结点； 中序遍历根结点的右子树。,中序遍历序列：D G B A E C F,中序（根）遍历,7.3.2 二叉树的遍历,18,若二叉树为空，则空操作返回；否则： 后序遍历根结点的左子树； 后序遍历根结点的右子树。 访问根结点；,后序遍历序列：G D B E F C A,后序（根）遍历,7.3.2 二叉树的遍历,A,B,C,D,E,F,G,19,二叉树的层次遍历是指从二叉树的第0层（即根结点）开始，从上至下逐层遍历，在同一层中，则按从左到右的顺序对结点逐个访问。,层序遍历序列：A B C D E F G,7.3.2 二叉树的遍历,A,B,C,D,E,F,G,层序遍历,20,-,-,/,+,*,a,b,c,d,e,f,二叉树遍历操作练习,前序遍历结果：- + a * b - c d / e f 中序遍历结果：a + b * c - d - e / f 后序遍历结果：a b c d - * + e f / - 层序遍历结果：-+/a*efb-cd,7.3.2 二叉树的遍历,21,若已知一棵二叉树的前序（或中序，或后序，或层序）序列，能否唯一确定这棵二叉树呢？,例：已知前序序列为ABC，则与之对应的二叉树为：,7.3.2 二叉树的遍历,22,例：已知前序遍历序列为ABC，后序遍历序列为CBA，则下列二叉树都满足条件。,A,B,C,A,B,C,若已知一棵二叉树的前序序列和后序序列，能否唯一确定这棵二叉树呢？,7.3.2 二叉树的遍历,23,若已知一棵二叉树的前序序列和中序序列，能否唯一确定这棵二叉树呢？,例：已知一棵二叉树的前序遍历序列和中序遍历序列分别为ABCDEFGHI 和BCAEDGHFI，如何构造该二叉树呢?,7.3.2 二叉树的遍历,怎样确定？,24,前序：A B C D E F G H I中序：B C A E D G H F I,前序：B C 中序：B C,前序： D E F G H I 中序： E D G H F I,7.3.2 二叉树的遍历,25,前序：F G H I 中序：G H F I,前序： D E F G H I 中序： E D G H F I,7.3.2 二叉树的遍历,26,练习,1、现有一棵二叉树的仿真指针表如下所示，请写出该二叉树的先序，中序，后序,层序遍历的序列。,27,练习,2、现有一棵二叉树的先序遍历和中序遍历的序列分别为： 先序：A,B,C,D,F,E,G,H 中序：B,D,F,C,G,E,H,A 请以图示表示方式画出该二叉树。,28,/二叉树先序遍历递归算法 void PreOrder(Node* r ) if(r!=NULL) coutdata lChild); /遍历左子树 PreOrder ( r-rChild); /遍历右子树 ,7.3.2 二叉树的遍历,29,/二叉树先序遍历 递归算法 void BTree:PreOrder(Node* r,void Visit(Node*) if(r!=NULL) Visit(r); PreOrder(r-lChild,Visit); PreOrder(r-rChild,Visit); ,7.3.2 二叉树的遍历,怎样消去递归？,30,B,A,C,E,D,G,F,root,前序遍历序列：,A的左右子树均不空，访问A后应该访问左子树的所有节点，然后再访问右子树的所有节点。,访问完A的左子树后，怎样知道A的右子树在哪里？,7.3.2 二叉树的遍历,/二叉树先序遍历的非递归过程,31,B,A,C,E,D,G,F,root,前序遍历序列：,A,root: C,32,B,A,C,E,D,G,F,root: B,前序遍历序列：,A,B,root: E,root: C,33,B,A,C,E,D,G,F,root,root: E,root: C,前序遍历序列：,A,B,D,D的右子树为空，不需要进栈，左子树为空，弹栈访问下一个元素,34,E,E,B,A,C,D,G,F,root,root: C,前序遍历序列：,A,B,D,E,E的右子树为空，不需要进栈,35,C,B,A,C,E,D,G,F,root,root: C,前序遍历序列：,A,B,D,E,G,G的右子树为空，不需要进栈，左子树为空，弹栈访问下一个元素,36,C,B,A,C,E,D,G,F,root,root: F,前序遍历序列：,A,B,D,E,G,C,C的右子树不空，进栈；,37,F,B,A,C,E,D,G,F,root,前序遍历序列：,A,B,D,E,G,C,F,C的左子树空，弹栈访问下一个元素,38,F,B,A,C,E,D,G,F,root,前序遍历序列：,A,B,D,E,G,C,F,F的左子树为空，且栈为空，遍历完毕！,39,B,A,C,E,D,G,F,root,前序遍历序列：,A,B,D,E,G,C,F,40,7.3.2 二叉树的遍历,/二叉树先序遍历的非递归算法 算法思想： 指针指向树的根结点 指针不为空，访问指针指向的结点，转3；否则转5； 若有右孩子，则把右孩子结点压栈； 若有左孩子，则指针指向左孩子，转2；否则，若栈非空，则指针指向弹栈结点；栈空则指针指向空； 结束,41,/二叉树先序遍历的非递归算法 stack mystack; while(r!=NULL) Visit(r); if(r-rChild !=NULL) mystack.push(r-rChild ); if(r-lChild !=NULL) r=r-lChild; else if(mystack.empty() =0) r=mystack.top(); mystack.pop (); else r=NULL; ,42,中序遍历（LDR）递归算法为： 若二叉树为空则算法结束；否则： （1）中序遍历根结点的左子树； （2）访问根结点； （3）中序遍历根结点的右子树。,7.3.2 二叉树的遍历,43,/二叉树中序遍历 递归算法 void BTree:InOrder(Node* r) if(r!=NULL) InOrder(r-lChild); coutdatarChild); ,44,/二叉树中序遍历 递归算法 void BTree:InOrder(Node* r,void Visit(Node*) if(r!=NULL) InOrder(r-lChild,Visit); Visit(r); InOrder(r-rChild,Visit); ,45,中序遍历非递归算法 算法思想为： 从二叉树根结点开始，沿左子树一直走到末端（左孩子为空）为止，在走的过程中，把依次遇到的结点进栈，待左子树为空时，从栈中退出结点并访问，然后再转向它的右子树。如此重复，直到栈空或指针为空止。,7.3.2 二叉树的遍历,46,/中序遍历非递归算法 void BTree:InOrder1(Node* r,vod Visit(Node*) Node *p,*s100; /s为一个栈，top为栈顶指针 int top=0; p=r; while(p!=NULL)|(top0) while(p!=NULL) s+top=p; p=p-lchild; p=stop-; Visit(p); p=p-rchild; ,47,后序遍历（LRD）递归算法为： 若二叉树为空则算法结束；否则： （1）后序遍历根结点的左子树； （2）后序遍历根结点的右子树； （3）访问根结点。,7.3.2 二叉树的遍历,48,/二叉树后序遍历递归算法 void BTree:PostOrder(Node* r) if(r!=NULL) PostOrder(r-lChild); PostOrder(r-rChild); coutdataendl; ,49,/二叉树后序遍历递归算法 void BTree:PostOrder(Node* r,void Visit(Node*) if(r!=NULL) PostOrder(r-lChild,Visit); PostOrder(rt-rChild,Visit); Visit(r); ,50,后序遍历非递归算法 算法思想为： 搜索指针指向某一个结点时，先要遍历左子树，此结点应先进栈保存，遍历完它的左子树后，再次回到该结点，该结点再次进栈（遍历其右子树），右子树遍历完后，再次退栈时，访问该结点。 为了区分同一结点的两次进栈，引入一个栈次数的标志，一个元素第一次进栈标志为0，第二次进标志为1，并将标志存入另一个栈中，当从标志栈中退出的元素为1时，访问结点。,7.3.2 二叉树的遍历,51,void BTree:PostOrder1(Node* r,void Visit(Node*) Node *p,*s1100; /s1栈存放树中结点 int s2100,top=0,b; /s2栈存放进栈标志 p=r; do while(p!=NULL) s1top=p;s2top+=0; /第一次进栈标志为0 p=p-lchild; if(top0) b=s2-top; p=s1top; if(b=0) s1top=p;s2top+=1; /第二次进栈标志为0 p=p-rchild; else Visit(p); p=NULL; while(top0); ,52,层序遍历算法 层序遍历算法思想：在所有未被访问结点的集合中，排列在已访问结点集合中最前面结点的左子树的根结点将最先被访问，然后是该结点的右子树的根结点。这样，如果把已访问的结点放在一个队列中，那么，所有未被访问结点的访问次序就可以由存放在队列中的已访问结点的出队列次序决定。因此可以借助队列实现二叉树的层序遍历。,7.3.2 二叉树的遍历,53,层序遍历算法 （1）初始化设置一个队列（结点指针类型）； （2）把根结点指针入队列； （3）当队列非空时，循环执行步骤（3.a）到步骤（3.c）； （3.a）出队列取得一个结点指针，访问该结点； （3.b）若该结点的左子树非空，则将该结点的左子树指针入队列； （3.c）若该结点的右子树非空，则将该结点的右子树指针入队列； （4）结束。,7.3.2 二叉树的遍历,54,/层序遍历 void BTree:LevelOrder(void Visit(Node*) Node* qMaxSize; Node* t; int front=0,rear=0; if(root!=NULL) q+rear = root; while (front!=rear) front+; t = qfront; Visit(t); if(t-lChild!=NULL) q+rear = t-lChild; if(t-rChild!=NULL) q+rear = t-rChild; ,55,二叉树遍历的应用 (1)二叉树的撤消操作 在释放某个结点的存储空间前必须先释放该结点左孩子结点的存储空间和右孩子结点的存储空间，因此，二叉树撤消操作必须是后序遍历的具体应用。撤消操作函数实现如下：,7.3.2 二叉树的遍历,56,void BTree:Destroy(Node *r) if(r =NULL) return; else if(r-lChild != NULL) Destroy(r-lChild); if(r-rChild != NULL) Destroy(r-rChild); cout data “ “; /此语句只为方便测试 delete r; ,57,二叉树遍历的应用 (2) 打印二叉树 把二叉树逆时针旋转90度，按照二叉树的凹入表示法打印二叉树。可把此函数设计成递归函数。由于把二叉树逆时针旋转90度后，在屏幕上方的首先是右子树，然后是根结点，最后是左子树，所以打印二叉树算法是一种特殊的中序遍历算法。,实验预告,58,void BTree:Print(Node* r, int level) /二叉树r第level层结点数据域值的横向显示 if(r != NULL) /二叉树r-rChild第level+1层结点数据域值的横向显示 Print(r-rChild , level+1); if(level != 0) /走过6*(level-1)个空格 for(int i = 0; i data lChild第level+1层结点数据域值的横向显示 Print(r-lChild, level+1); ,59,应用举例 例7-1 编写一个程序，首先建立如图7-10(a)所示的不带头结点的二叉链存储结构的二叉树，然后打印该二叉树并分别输出按照前序遍历二叉树次序、中序遍历二叉树次序和后序遍历二叉树次序访问各结点的序列信息，最后再测试查找函数和撤消函数的正确性。,二叉树类(提高),60,*7.6 线索二叉树,对二叉链存储结构的二叉树分析可知，在有n个结点的二叉树中必定存在n+1个空链域。 二叉树本身是非线性结构，但通过某种遍历方法遍历得到的结点序列却是线性的。 当按某种规则遍历二叉树时，保存遍历时得到的结点的后继结点信息和前驱结点信息的最常用的方法是建立线索二叉树。 下面讨论建立线索二叉树的方法：,61,当某结点的左指针为空时，令该指针指向按某种方法遍历二叉树时得到的该结点的前驱结点；当某结点的右指针为空时，令该指针指向按某种方法遍历二叉树时得到的该结点的后继结点。 问题：如何区分左指针指向的结点到底是左孩子结点还是前驱结点，右指针指向的结点到底是右孩子结点还是后继结点。 解决方法：在结点中增加两个线索标志位来区分这两种情况。线索标志位定义如下：,62,每个结点的结构就如下所示：,结点中指向前驱结点和后继结点的指针称为线索。在二叉树的结点上加上线索的二叉树称作线索二叉树。对二叉树以某种方法（如前序、中序或后序方法）遍历使其变为线索二叉树的过程称作按该方法对二叉树进行的线索化。,63,A,D,G,E,C,F,B,64,65,中序线索化,66,中序线索二叉树中 查找结点的后继和前驱:,如何在中序线索二叉树中找结点的后继： RThread = 1时，Rchild所指的结点即为后继； RThread = 0时，其后继为遍历其右子树时的第一个结点（最左下结点）。 如何在中序线索二叉树中找结点的前驱： LThread = 1时，Lchild所指的结点即为前驱； LThread = 0时，其前驱为遍历其左子树时的最后一个结点（最右下结点）。,67,7.7 哈夫曼(Huffman)树,一、哈夫曼树的基本概念 从A结点到B结点所经过的分支序列叫做从A结点到B结点的路径； 从A结点到B结点所经过的分支个数叫做从A结点到B结点的路径长度； 从二叉树的根结点到二叉树中所有叶结点的路径长度之和称作该二叉树的路径长度。,68,设二叉树有n个带权值的叶结点，定义从二叉树的根结点到二叉树中所有叶结点的路径长度与相应叶结点权值的乘积之和称作该二叉树的带权路径长度（WPL），即：,其中，wi为第i个叶结点的权值，li为从根结点到第i个叶结点的路径长度。,7.7 哈夫曼(Huffman)树,69,哈夫曼树：给定一组具有确定权值的叶子结点，带权路径长度最小的二叉树。,例：给定4个叶子结点，其权值分别为2，3，4，7，可以构造出形状不同的多个二叉树。,WPL=32 WPL=41 WPL=30,2,3,4,7,2,3,4,7,7,4,2,3,7.7 哈夫曼(Huffman)树,70,WPL=32 WPL=41 WPL=30,2,3,4,7,2,3,4,7,7,4,2,3,7.7 哈夫曼(Huffman)树,哈夫曼树的特点： 1. 权值越大的叶子结点越靠近根结点，而权值越小的叶子结点越远离根结点。 2. 只有度为0（叶子结点）和度为2（分支结点）的结点，不存在度为1的结点。（反证法）,71,7.7 哈夫曼(Huffman)树,哈夫曼算法基本思想： 初始化：由给定的n个权值w1，w2，wn构造n棵只有一个根结点的二叉树，从而得到一个二叉树集合FT1，T2，Tn； 选取与合并：在F中选取根结点的权值最小的两棵二叉树分别作为左、右子树构造一棵新的二叉树，这棵新二叉树的根结点的权值为其左、右子树根结点的权值之和； 删除与加入：在F中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到F中； 重复、两步，当集合F中只剩下一棵二叉树时，这棵二叉树便是哈夫曼树。,讲解图7-15,72,第1步：初始化,W2，3，4，5 哈夫曼树的构造过程,第2步：选取与合并,第3步：删除与加入,7.7 哈夫曼(Huffman)树,73,W2，3，4，5 哈夫曼树的构造过程,重复第2步,重复第3步,7.7 哈夫曼(Huffman)树,74,W2，3，4，5 哈夫曼树的构造过程,重复第2步,重复第3步,7.7 哈夫曼(Huffman)树,75,课堂练习,现有权值集合W=3, 5, 6, 7, 9, 12, 18，请构造相应的哈夫曼树。,76,7.7 哈夫曼(Huffman)树,怎样的编码方式，使得电文最短？,哈夫曼树应用哈夫曼编码,编码：将传送的文字转换为二进制字符0和1组成的二进制串的过程为编码。 前缀编码：一组编码中任一编码都不是其它任何一个编码的前缀 ；保证了在解码时不会有多种可能。,77,7.7 哈夫曼(Huffman)树,哈夫曼树应用哈夫曼编码,假设要传送的电文为ABACCDA，电文中只有A,B,C,D四种字符，则有以下编码方案：,编码1，则电文为：00 01 00 10 10 11 00，总长度为14。 编码2，则电文为：0 110 0 10 10 111 0，总长度为13。,78,7.7 哈夫曼(Huffman)树,哈夫曼编码：设需要编码的字符集合为d1,d2,dn ，各个字符在电文中出现的次数集合为w1,w2,wn，以d1,d2,dn作为叶结点，以w1,w2,wn作为各叶结点的权值构造一棵哈夫曼树，规定哈夫曼树中的左分支为0，右分支为1，则从根结点到每个叶结点所经过的分支对应的0和1组成的序列便为该结点对应字符的编码。 代码总长度最短的不等长编码称之为哈夫曼编码。,哈夫曼树应用哈夫曼编码,79,例：一组字符A, B, C, D, E, F, G出现的频率分别是9, 11, 5, 7, 8, 2, 3，设计最经济的编码方案。,0,0,0,0,0,0,1,1,1,1,1,1,编码方案： A：00 B：10 C：010 D：110 E：111 F：0110 G：0111,怎样对电文进行编码和译码？,80,利用二叉树仿真指针顺序表构造哈夫曼树进行哈夫曼编码原理,N个叶子叶子结点的哈夫曼树会有2N-1个结点，初始化方仿真指针顺序表,81,利用二叉树仿真指针顺序表构造哈夫曼树进行哈夫曼编码原理,挑选出权值最小的两个flag为0的结点合并,82,利用二叉树仿真指针顺序表构造哈夫曼树进行哈夫曼编码原理,挑选出权值最小的两个flag为0的结点合并,83,利用二叉树仿真指针顺序表构造哈夫曼树进行哈夫曼编码原理,挑选出权值最小的两个flag为0的结点合并,84,利用二叉树仿真指针顺序表构造哈夫曼树进行哈夫曼编码原理,挑选出权值最小的两个flag为0的结点合并,85,利用二叉树仿真指针顺序表构造哈夫曼树进行哈夫曼编码原理,挑选出权值最小的两个flag为0的结点合并,86,利用二叉树仿真指针顺序表构造哈夫曼树进行哈夫曼编码原理,挑选出权值最小的两个flag为0的结点合并,87,利用二叉树仿真指针顺序表构造哈夫曼树进行哈夫曼编码原理,哈夫曼编码，对每个叶子结点进行向上溯源，编码在数组中右对齐。,88,实验预告,利用教材哈夫曼编码的实现程序，实现对给定的电文进行编码和译码。 【进阶】对英文文档文件进行编码和译码。,89,* 树与二叉树