第3章堆栈、队列、二叉树.ppt

《第3章堆栈、队列、二叉树.ppt》由会员分享，可在线阅读，更多相关《第3章堆栈、队列、二叉树.ppt（82页珍藏版）》请在三一办公上搜索。

1、堆栈、队列、二叉树,线性表堆栈队列二叉树,栈的逻辑结构,空栈：不含任何数据元素的栈。,（a1,a2,an）,栈：限定仅在表尾进行插入和删除操作的线性表。,允许插入和删除的一端称为栈顶，另一端称为栈底。,栈,栈,a1,a2,a3,入栈,出栈,插入：入栈、进栈、压栈删除：出栈、弹栈,栈的示意图,栈,栈的操作特性：后进先出,a1,a2,a3,入栈,出栈,插入：入栈、进栈、压栈删除：出栈、弹栈,栈的示意图,栈操作函数包括：栈的初始化、栈的释放、弹栈压栈。,存储方式：连续存储(基于数组)：顺序栈动态存储(基于链表)：链栈,/stack.h#ifndef STACK_T_H#define SATCK_T_

2、H#include/结构定义struct Stack int*data;/栈数据存储 int memNum;/栈元素个数 int size;/栈大小;int InitStack(Stack/函数原型#endif STACK_T_H,顺序栈的定义(1),/stack.cpp#include“stack.h”/初始化栈int InitStack(Stack,顺序栈栈的定义(2),/弹栈，无数据时返回0，否则返回1int PopStack(Stack,顺序栈的定义(3),/test.cpp#include#include“stack.h”int main()int i,num;Stack newSt

3、ack;InitStack(newStack,10);coutPush integers to stack:endl;for(i=0;i10;+i)couti;PushStack(newStack,i);coutendl;coutFrom function popStack:endl;for(i=0;i10;+i)if(PopStack(newStack,num)coutnum;,顺序栈的测试(1),coutendlendl;for(i=10;i20;+i)newStack.datanewStack.memNum+=i;coutReading from struct newStack:endl

4、;for(i=0;i10;+i)coutnewStack.datai;coutendl;for(i=10;i20;+i)coutnewStack.datai;coutendl;DelStack(newStack);return 0;,顺序栈的测试(2),顺序栈的测试输出(3),使用结构时的一些缺陷通过专门的函数使用时没有问题直接操作时可能会出错，任何函数都可以直接操作可能会被赋予不恰当的值，或破坏默认的操作流程，如栈的先进后出数据和函数的相关性也没有体现，所有函数都是平等的根本原因对数据的访问权限问题封装和隐藏机制可以克服该问题,队列,队列的逻辑结构,空队列：不含任何数据元素的队列。,队列：只

5、允许在一端进行插入操作，而另一端进行删除操作的线性表。,允许插入（也称入队、进队）的一端称为队尾，允许删除（也称出队）的一端称为队头。,（a1,a2,an）,队列,队列的操作特性：先进先出,a1,a2,a3,入队,队尾,队头,出队,队头,队列的逻辑结构,队列操作函数包括：(1)队列的初始化(2)队列的释放、(3)插入一个新的队尾元素，称为进队；(4)删除队头元素，称为出队；(5)读取队头元素；,队列,队列的顺序存储结构及实现,顺序队列：队列的顺序存储结构,如何改造数组实现队列的顺序存储？,例：a1a2a3a4依次入队,a1,a2,a3,a4,入队操作时间性能为O(1),队列,如何改造数组实现队

6、列的顺序存储？,例：a1a2依次出队,队列的顺序存储结构及实现,a1,a2,a3,a4,队列,如何改造数组实现队列的顺序存储？,例：a1a2依次出队,队列的顺序存储结构及实现,a2,a3,a4,队列,如何改造数组实现队列的顺序存储？,例：a1a2依次出队,队列的顺序存储结构及实现,a3,a4,出队操作时间性能为O(n),队列,队列的顺序存储结构及实现,如何改进出队的时间性能？,队列,队列的顺序存储结构及实现,例：a1a2a3a4依次入队,a1,a2,a3,a4,入队操作时间性能仍为O(1),队列,例：a1a2依次出队,队列的顺序存储结构及实现,a1,a2,a3,a4,出队操作时间性能提高为O(

7、1),队列,例：a1a2依次出队,队列的顺序存储结构及实现,a3,a4,队列的移动有什么特点？,队列,例：a1a2依次出队,队列的顺序存储结构及实现,a3,a4,队列,假溢出：当元素被插入到数组中下标最大的位置上之后，队列的空间就用尽了，尽管此时数组的低端还有空闲空间，这种现象叫做假溢出。,队列的顺序存储结构及实现,继续入队会出现什么情况？,a3,a4,a5,队列,循环队列：将存储队列的数组头尾相接。,队列的顺序存储结构及实现,如何解决假溢出？,0 1 2 3 4,入队,出队,a3,a4,a5,a6,逻辑上的循环队列,队列,不存在物理的循环结构，用软件方法实现。求模：（41）mod 50,队列

8、的顺序存储结构及实现,如何实现循环队列？,0 1 2 3 4,入队,出队,a3,a4,a6,队列,如何判断循环队列队空？,队空的临界状态,队列的顺序存储结构及实现,0 1 2 3 4,入队,出队,a3,队列,如何判断循环队列队空？,执行出队操作,队空：front=rear,队列的顺序存储结构及实现,0 1 2 3 4,入队,出队,a3,队列,如何判断循环队列队满？,队满的临界状态,队列的顺序存储结构及实现,0 1 2 3 4,入队,出队,a3,a4,a5,a6,队列,如何判断循环队列队满？,执行入队操作,队满：front=rear,队列的顺序存储结构及实现,0 1 2 3 4,入队,出队,a3

9、,a4,a5,a6,a7,队列,方法一：附设一个存储队列中元素个数的变量num，当num=0时队空，当num=QueueSize时为队满；方法二：修改队满条件，浪费一个元素空间，队满时数组中只有一个空闲单元；方法三：,如何确定不同的队空、队满的判定条件？为什么要将队空和队满的判定条件分开？,队列的顺序存储结构及实现,队列,循环队列类的声明,const int QueueSize=100;template class CirQueue public:CirQueue()；CirQueue()；void EnQueue(T x);T DeQueue();T GetQueue();bool Empt

10、y()；private:T dataQueueSize;int front,rear;,队列,template void CirQueue:EnQueue(T x)if(rear+1)%QueueSize=front)throw 上溢;rear=(rear+1)%QueueSize;datarear=x;,循环队列的实现入队,a3,a4,a5,队列,0 1 2 3 4,入队,a4,a5,a6,出队,template T CirQueue:DeQueue()if(rear=front)throw 下溢;front=(front+1)%QueueSize;return datafront;,循环队

11、列的实现出队,a3,队列,template T CirQueue:GetQueue()if(rear=front)throw 下溢;i=(front+1)%QueueSize;return datai;,循环队列的实现读队头元素,0 1 2 3 4,入队,a4,a5,a6,出队,a3,树,树的基本概念和术语二叉树的基本概念和性质二叉树的存储结构和各种遍历算法,树的基本概念,什么是树？什么是子树、树根？树的深度？什么是结点、双亲结点、孩子结点、结点的度、兄弟、祖先和子孙？,树的定义,树(Tree)是由一个或多个结点组成的有限集合T。其中：（1）有一个特定的结点，称为该树的根（root）结点；,（

12、2）根结点之外的其余结点可分为m(m0)个互不相交的有限集合T1,T2,Tm，且其中每一个集合本身又是一棵树，称之为根的子树（Sub Tree）。这是递归定义。仅有一个根结点的树是最小树。,树的常用术语,子女：若结点的子树非空，结点子树即为该结点的子女。双亲：若结点有子女，该结点是子女双亲。,树的常用术语,兄弟：同一结点的子女互称为兄弟。度：结点的子女个数即为该结点的度；树中各个结点的度的最大值称为树的度。分支结点：度不为0的结点即为分支结点，亦称为非终端结点。叶结点：度为0的结点即为叶结点，亦称为终端结点。祖先：某结点到根结点的路径上的各个结点都是该结点的祖先。子孙：某结点的所有下属结点，都

13、是该结点的子孙。,树的常用术语,结点的层次：规定根结点在第一层，其子女结点的层次等于它的层次加一。以下类推。深度：结点的深度即为结点的层次；离根最远结点的层次即为树的深度。,树的常用术语,高度：规定叶结点的高度为1，其双亲结点的高度等于它的高度加一。树的高度：等于根结点的高度，即根结点所有子女高度的最大值加一。有序树：树中结点的各棵子树 T0,T1,是有次序的，即为有序树。无序树：树中结点的各棵子树之间的次序是不重要的，可以互相交换位置。森林：森林是m（m0）棵树的集合。,树的表示形式,树形结构法，如前面图(a);集合包含关系文氏图法，如图(b);凹入法，如图(c)。,二叉树,二叉树的定义：二

14、叉树（Binary Tree）是n(n0)个结点的有限集合。它或为空树（n=0）；或为非空树。对于非空树T：（1）有且仅有一个特定的称之为根root的结点；（2）当n1时，除根结点以外的其余结点分为两个互不相交的子集T1和T2，它们称之为T的左子树和右子树，且都是二叉树。这个定义是递归的。由于左、右子树也是二叉树，因此子树也可为空树。,5种基本形态的二叉树,(a)空树(b)仅有一个结点(c)仅有左子树而右子树为空(d)仅有右子树而左子树为空(e)左右子树均为非空的二叉树(a)(b)(c)(d)(e),注意：二叉树的左、右子树必须严格区分。（c）与（d）就是两棵不同的二叉树。,L,L,R,R,二

15、叉树的重要性质,性质1 二叉树第i(i1)层上至多有2i-1个结点。证明：(数学归纳法)根结点在二叉树的第1层上，这层结点数最多为1个，即20个；第2层上最多有2个结点，即21个；假设第i1层的结点最多有2i2个，且每个结点最多有两个孩子；那么第i层上结点最多有 2*2i2=2i1个。,二叉树的重要性质,性质2 深度为k(k1)的二叉树至多有2k1个结点。证明：由性质1可知各层结点最多数之和为：20+21+22+2k1；由二进制换算关系可知：20+21+22+2k1=2k 1；因此，二叉树树中结点的最大数目为2k 1。性质2证明完毕。,二叉树的重要性质,性质3：在任意二叉树中，若叶子结点（即度

16、为零的结点）个数为n0，度为1的结点个数为n1，度为2的结点个数为n2，那么n0=n2+1。证明：设n代表二叉树结点的总数，那么：n=n0+n1+n2(1)有n个结点的二叉树总边数为n1条，得：n1=0*n0+1*n1+2*n2(2)将式(1)代入式(2)得：n0=n2+1。,满二叉树和完全二叉树(二种特殊二叉树),深度为k并且含有2k1个结点的二叉树称为满二叉树，如图（a）。对满二叉树的结点可以从根结点开始自上向下，自左至右顺序编号。深度为k含有n个结点的二叉树，当且仅当每个结点的编号与相应满二叉树的结点顺序编号从1到n 一一对应，则称此二叉树为完全二叉树，如图（b）。图（c）因为其结点编号

17、与满二叉树的结点编号不是一一对应完全相同，不是完全二叉树。,二叉树的重要性质,性质4：具有n个结点的完全二叉树，其树深k为 证明：假设某完全二叉树的结点总数是n，n值应该大于树深为k1的满二叉树结点数2k11，且小于等于树深为k的满二叉树结点数2k1：2k11 n 2k1 由于不等式各项均为整数，当对两端两项各加1时得：2k1n2k 再对其取对数得：k1log2nk 对log2n取整等于k1。所以：k=,二叉树的重要性质,性质5：若对有n个结点的完全二叉树进行顺序编号（1in），那么对于编号为i(i1)的结点：若i=1,则 i 无双亲若i 1,则 i 的双亲为i2若2*i=n,则 i 的左子女

18、为 2*i，若2*i+1=n,则 i 的右子女为2*i+1若 i 为奇数,且i!=1,则其左兄弟为i-1,若若 i 为偶数,且i!=n,则其右兄弟为i+1,二叉树的存储结构,二叉树的存储结构有多种，最常用的是：顺序存储结构链表存储结构。,链表存储结构,用于二叉树存储的链表结构，常见的有二叉链表和三叉链表 二叉链表的每个结点的结构描述如下：struct node int data;/数据域 node*lch;/左指针域 node*rch;/右指针域,链表存储结构,三叉链表的每个结点的结构描述如下：struct node3 int data;/数据域 node3*lch,*par，*rch;/pa

19、r是双亲指针域;,链表存储结构,二叉树 二叉链表 三叉链表,二叉树链表表示的示例,二叉树类,/Binary Tree-#include#include typedef int ElemType;struct node/定义结点结构体 ElemType data;node*lch;node*rch;node()lch=NULL;rch=NULL;node(ElemType x,node*l=NULL,node*r=NULL)data=x;lch=l;rch=r;,二叉树类,class BinTree public:BinTree()root=NULL;/构造函数，空树 BinTree()/析构函

20、数 destroy(root);root=NULL;void create()/建立二叉树 void preorder()/先根遍历调用 preorder(root);void inorder()/中根遍历调用 inorder(root);void postorder()/后根遍历调用 postorder(root);,二叉树类,protected:node*root;/数据成员，树根指针 private:void CreateBinTree(ifstream/BiTree End,遍历二叉树,二叉树最主要、最基本的运算是遍历。遍历二叉树是指以一定的次序访问二叉树中的每个结点，并且每个结点仅被

21、访问一次。访问结点是指对结点进行各种操作的简称。例如，查询结点数据域的内容，或输出它的值，或找出结点位置，或是执行对结点的其他操作。遍历二叉树的过程实质是把二叉树的结点进行线性排列的过程。,遍历的顺序,二叉树的遍历就是按某种次序访问树中的结点，要求每个结点访问一次且仅访问一次。设访问根结点记作 V 遍历根的左子树记作 L 遍历根的右子树记作 R则可能的遍历次序有 前序 VLR 中序 LVR 后序 LRV,前序遍历,前序遍历二叉树算法的框架是：若二叉树为空，则空操作；否则访问根结点(V)；前序遍历左子树(L)；前序遍历右子树(R)。遍历结果-+a*b-c d/e f,前序遍历,void BinT

22、ree:PreOrder(node*p)if(p!=NULL)/访问根结点coutdata;/operate/遍历左子树PreOrder(p-lch);/遍历右子树PreOrder(p-rch);,前序遍历,中序遍历,中序遍历二叉树算法的框架是：若二叉树为空，则空操作；否则中序遍历左子树(L)；访问根结点(V)；中序遍历右子树(R)。遍历结果 a+b*c-d-e/f,中序遍历,void BinTree:InOrder(node*p)if(p!=NULL)/遍历左子树InOrder(p-lch);/访问根结点coutdata;/operate/遍历右子树InOrder(p-rch);,后序遍历,

23、后序遍历二叉树算法的框架是：若二叉树为空，则空操作；否则后序遍历左子树(L)；后序遍历右子树(R)；访问根结点(V)。遍历结果 a b c d-*+e f/-,-,-,/,+,*,a,b,c,d,e,f,后序遍历,void BinTree:PostOrder(node*p)if(p!=NULL)/遍历左子树PostOrder(p-lch);/遍历右子树PostOrder(p-rch);/访问根结点coutdata;/operate;,利用二叉树前序遍历建立二叉树,以递归方式建立二叉树。输入结点值的顺序必须对应二叉树结点前序遍历的顺序。并约定以输入序列中不可能出现的值作为空结点的值以结束递归,此

24、值在RefValue中。例如用“”或用“-1”表示字符序列或正整数序列空结点。,利用二叉树前序遍历建立二叉树,如图所示的二叉树的前序遍历顺序为A B C D E G F,利用二叉树前序遍历建立二叉树,void BinTree:CreateBinTree(ifstream,利用二叉树前序遍历建立二叉树,/递归建立左子树 CreateBinTree(in,p-lch);/递归建立右子树 CreateBinTree(in,p-rch);/关闭指向空子树的指针 else p=NULL;,二叉排序树,二叉排序树的定义：二叉排序树或者是一棵空二叉树，或者是具有以下性质的二叉树若它的左子树非空，则左子树上所

25、有结点的值均小于根结点的值若它的右子树非空，则右子树上所有结点的值均不小于根结点的值左右子树本身右各是一棵二叉排序树,二叉排序树,用中序遍历二叉树就可以得到由小到大的有序树 15 23 26 47 56 89,二叉排序树,插入操作若二叉排序树为空，则新结点为二叉排序树的根结点；否则将新结点的关键字值和根结点的关键字值进行比较，若小于根结点的值，则将新结点插入到左子树中去，否则，插入到右子树中去。此插入过程是递归进行的,二叉排序数,void BinTree:Insert(const int data,node*,二叉排序树,查找某一结点node*BinTree:Find(int data,nod

26、e*b)if(b!=NULL)node*temp=b;while(temp!=NULL)if(temp-data=data)return temp;if(temp-data lchild;else temp=temp-rchild;,二叉排序,删除操作一个结点被删除后，必须保证余下的结点仍然构成一棵二叉排序树。下面分两种情况讨论：情况一：被删除的结点至少有一棵空子树方法：使被删结点的那棵非空子树的根成为其双亲结点的相应子女,二叉排序树,后继结点,前驱结点,将结点50删除,二叉排序树,情况二：被删除的结点有两棵非空的子树方法一：找到被删除结点在中序遍历序列中的直接后继结点（它一定在被删除结点的右子树中），用此后继结点的值取代被删除结点的值，然后删除此后继结点，由于被删除的后继结点的左子树一定是空子树，所以删除后继结点的过程同情况一。方法二：用被删除结点在中序遍历序列中的直接前驱结点（该结点的右子树也一定为空）代替被删除的结点，然后删除这个前驱结点。,二叉排序树,中序遍历：,10,15,30,33,35,37,50,53,55,62,