数据结构(C++版)第5章树和二叉树1018.ppt

二叉树的逻辑结构二叉树的存储结构及实现,第5章二叉树,本章的主要内容是,二叉树的定义,二叉树是n（n0）个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。,5.1二叉树的逻辑结构,结构简单，适合于计算机处理问题转化：将树转换为二叉树，从而利用二叉树解决树的有关问题。,研究二叉树的意义？,二叉树的特点：,每个结点最多有两棵子树；二叉树是有序的，其次序不能任意颠倒。,5.1二叉树的逻辑结构,二叉树的基本形态,5.1二叉树的逻辑结构,满二叉树在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上。,满二叉树的特点：,叶子只能出现在最下一层；只有度为0和度为2的结点。,5.1二叉树的逻辑结构,特殊的二叉树,满二叉树,5.1二叉树的逻辑结构,不是满二叉树，虽然所有分支结点都有左右子树，但叶子不在同一层上。,满二叉树在同样深度的二叉树中结点个数最多满二叉树在同样深度的二叉树中叶子结点个数最多,特殊的二叉树,完全二叉树对一棵具有n个结点的二叉树按层序编号，如果编号为i（1in）的结点与同样深度的满二叉树中编号为i的结点在二叉树中的位置完全相同。,5.1二叉树的逻辑结构,特殊的二叉树,在满二叉树中，从最后一个结点开始，连续去掉任意个结点，即是一棵完全二叉树。,5.1二叉树的逻辑结构,A,1,5,2,3,4,6,7,9,10,B,C,D,E,F,G,H,I,J,不是完全二叉树，结点10与满二叉树中的结点10不是同一个结点,特殊的二叉树,1.叶子结点只能出现在最下两层，且最下层的叶子结点都集中在二叉树的左部；2.完全二叉树中如果有度为1的结点，只可能有一个，且该结点只有左孩子。3.深度为k的完全二叉树在k-1层上一定是满二叉树。,完全二叉树的特点,5.1二叉树的逻辑结构,特殊的二叉树,二叉树的遍历操作,二叉树的遍历是指从根结点出发，按照某种次序访问二叉树中的所有结点，使得每个结点被访问一次且仅被访问一次。,二叉树遍历操作的目的？,5.1二叉树的逻辑结构,二叉树的遍历方式：DLR、LDR、LRD、DRL、RDL、RLD,如果限定先左后右，则二叉树遍历方式有三种：前序：DLR中序：LDR后序：LRD,层序遍历：按二叉树的层序编号的次序访问各结点。,5.1二叉树的逻辑结构,考虑二叉树的组成：,前序（根）遍历若二叉树为空，则空操作返回；否则：访问根结点；前序遍历根结点的左子树；前序遍历根结点的右子树。,5.1二叉树的逻辑结构,前序遍历序列：ABDGCEF,二叉树的遍历操作,中序（根）遍历若二叉树为空，则空操作返回；否则：中序遍历根结点的左子树；访问根结点；中序遍历根结点的右子树。,5.1二叉树的逻辑结构,中序遍历序列：DGBAECF,二叉树的遍历操作,后序（根）遍历若二叉树为空，则空操作返回；否则：后序遍历根结点的左子树；后序遍历根结点的右子树。访问根结点；,5.1二叉树的逻辑结构,后序遍历序列：GDBEFCA,二叉树的遍历操作,层序遍历二叉树的层次遍历是指从二叉树的第一层（即根结点）开始，从上至下逐层遍历，在同一层中，则按从左到右的顺序对结点逐个访问。,5.1二叉树的逻辑结构,层序遍历序列：ABCDEFG,二叉树的遍历操作,5.1二叉树的逻辑结构,-,-,/,+,*,a,b,c,d,e,f,二叉树遍历操作练习,前序遍历结果：-+a*b-cd/ef中序遍历结果：a+b*c-d-e/f后序遍历结果：abcd-*+ef/-,二叉链表,基本思想：令二叉树的每个结点对应一个链表结点，链表结点除了存放与二叉树结点有关的数据信息外，还要设置指示左右孩子的指针。,结点结构：,其中，data：数据域，存放该结点的数据信息；lchild：左指针域，存放指向左孩子的指针；rchild：右指针域，存放指向右孩子的指针。,5.2二叉树的存储结构及实现,templatestructBiNodeTdata;BiNode*lchild,*rchild;,5.2二叉树的存储结构及实现,二叉链表,二叉链表,5.2二叉树的存储结构及实现,具有n个结点的二叉链表中，有多少个空指针？,二叉链表,5.2二叉树的存储结构及实现,具有n个结点的二叉链表中，有n+1个空指针。,二叉链表存储结构的类声明,templateclassBiTreepublic:BiTree();BiTree(BiNode*root);BiNode*Root()returnroot;BiTree();voidPreOrder(BiNode*root);voidInOrder(BiNode*root);voidPostOrder(BiNode*root);voidLeverOrder(BiNode*root);private:BiNode*root;BiNode*creat();voidRelease(BiNode*root);,5.2二叉树的存储结构及实现,前序遍历递归算法,templatevoidBiTree:PreOrder(BiNode*root)if(root=NULL)return;elsecoutdatalchild);PreOrder(root-rchild);,5.2二叉树的存储结构及实现,前序遍历算法的执行轨迹,templatevoidBiTree:PreOrder(BiNode*root)if(root=NULL)return;else1coutdatalchild);3PreOrder(root-rchild);4,二叉树前序遍历的非递归算法的关键：在前序遍历过某结点的整个左子树后，如何找到该结点的右子树的根指针。解决办法：在访问完该结点后，将该结点的指针保存在栈中，以便以后能通过它找到该结点的右子树。,5.2二叉树的存储结构及实现,前序遍历非递归算法,非递归前序遍历二叉树,栈是实现递归的最常用的结构思想：遇到一个结点，就访问该结点，并把此结点推入栈中，然后遍历它的左子树；遍历完它的左子树后，从栈顶托出这个结点，并按照它的右链接指示的地址再去遍历该结点的右子树结构。,访问结点序列:,A,栈S内容:,B,D,A,B,前序遍历的非递归实现,5.2二叉树的存储结构及实现,A,D,B,C,访问结点序列:,A,栈S内容:,B,D,A,前序遍历的非递归实现,5.2二叉树的存储结构及实现,A,D,B,C,D,访问结点序列:,A,栈S内容:,B,D,C,前序遍历的非递归实现,5.2二叉树的存储结构及实现,A,D,B,C,C,1.栈s初始化；2.循环直到root为空且栈s为空2.1当root不空时循环2.1.1输出root-data;2.1.2将指针root的值保存到栈中；2.1.3继续遍历root的左子树2.2如果栈s不空，则2.2.1将栈顶元素弹出至root；2.2.2准备遍历root的右子树；,前序遍历非递归算法（伪代码）,5.2二叉树的存储结构及实现,前序遍历非递归算法（伪代码）,templatevoidBiTree:PreOrder(BiNode*root)LinkStack*s;while(root!=NULL|!s.Empty()while(root!=NULL)coutdatalchild;if(!s.Empty()root=s.Pop();root=root-rchild;,1.栈s初始化；2.循环直到root为空且栈s为空2.1当root不空时循环2.1.1输出root-data;2.1.2将指针root的值保存到栈中；2.1.3继续遍历root的左子树2.2如果栈s不空，则2.2.1将栈顶元素弹出至root；2.2.2准备遍历root的右子树；,二叉树的建立,为了建立一棵二叉树，将二叉树中每个结点的空指针引出一个虚结点，其值为一特定值如“#”，以标识其为空，把这样处理后的二叉树称为原二叉树的扩展二叉树。,5.2二叉树的存储结构及实现,如何由一种遍历序列生成该二叉树？,遍历是二叉树各种操作的基础，可以在遍历的过程中进行各种操作，例如建立一棵二叉树。,扩展二叉树的前序遍历序列:AB#D#C#,5.2二叉树的存储结构及实现,二叉树的建立,设二叉树中的结点均为一个字符。假设扩展二叉树的前序遍历序列由键盘输入，root为指向根结点的指针，二叉链表的建立过程是：,5.2二叉树的存储结构及实现,二叉树的建立,按前序扩展遍历序列输入结点的值如果输入结点值为“#”,则建立一棵空的子树否则，根结点申请空间，将输入值写入数据域中，以相同方法的创建根结点的左子树以相同的方法创建根结点的右子树递归方法,templateBiTree:BiTree()root=creat();templateBiNode*BiTree:creat()BiNode*root;Tch;cinch;if(ch=#)root=NULL;elseroot=newBiNode;root-data=ch;root-lchild=creat();root-rchild=creat();returnroot;,5.2二叉树的存储结构及实现,按前序扩展遍历序列输入输入节点的值如果输入节点之为“#”,则建立一棵空的子树否则，根结点申请空间，将输入值写入数据域中，以相同方法的创建根节点的左子树以相同的方法创建根节点的右子树递归方法,templatevoidBiTree:Release(BiNode*root)if(root!=NULL)Release(root-lchild);Release(root-rchild);deleteroot;templateBiTree:BiTree(void)Release(root);,析构函数,中序遍历递归算法,templatevoidBiTree:InOrder(BiNode*root)if(root=NULL)return;elseInOrder(root-lchild);coutdatarchild);,5.2二叉树的存储结构及实现,非递归中序遍历二叉树,思想：遇到一个结点，就把它推入栈中，并去遍历它的左子树遍历完左子树后，从栈顶托出这个结点并访问之，然后按照它的右链接指示的地址再去遍历该结点的右子树。,非递归中序周游二叉树,templatevoidBiTree:InOrder(BiNode*root)LinkStack*aStack;BiNode*pointer=root;,while(!aStack.Empty()|pointer)if(pointer)aStack.Push(pointer);pointer=pointer-lchild;elsepointer=aStack.Top()-data;BiNode*q=aStack.Pop();coutdatarchild;,定义一个栈；从根节点出发开始遍历，p=root，如果栈不空，或者P！=NULL，进行下面的工作如果，p!=NULL,将P入栈；p=p-lchild;如果P=NULL，则栈顶出栈P，访问P，p=P-rchild;重复2,后序遍历递归算法,templatevoidBiTree:PostOrder(BiNode*root)if(root=NULL)return;elsePostOrder(root-lchild);PostOrder(root-rchild);coutdata;,5.2二叉树的存储结构及实现,非递归后序遍历二叉树,思想:遇到一个结点，把它推入栈中，遍历它的左子树左子树遍历结束后，还不能马上访问处于栈顶的该结点，而是要再按照它的右链接结构指示的地址去遍历该结点的右子树遍历遍右子树后才能从栈顶托出该结点并访问之,解决方案：需要给栈中的每个元素加上一个特征位，以便当从栈顶弹出一个结点时区别是从栈顶元素左边回来的(则要继续周游右子树)，还是从右边回来的(该结点的左、右子树均已周游)特征为Left表示已进入该结点的左子树，将从左边回来；特征为Right表示已进入该结点的右子树，将从右边回来,a,b,c,d,e,非递归后序周游二叉树,d,b,e,c,a,二叉树的非递归遍历总结,都是沿着左分支访问，直到左分支为空时，在依次对栈中节点的右分支进行处理。（遵循从左至右的遍历原则，体现深度优先搜索的思想）前序遍历：每个节点只进栈一次，在进栈前访问节点中序遍历：每个节点进栈一次，在出栈时访问节点后序遍历：每个节点进栈两次，在第二次出栈时访问节点,层序遍历,5.2二叉树的存储结构及实现,遍历序列：,A,A,B,C,B,D,C,E,F,G,D,E,F,G,层序遍历,队列Q初始化；2.如果二叉树非空，将根指针入队；3.循环直到队列Q为空3.1q=队列Q的队头元素出队；3.2访问结点q的数据域；3.3若结点q存在左孩子，则将左孩子指针入队；3.4若结点q存在右孩子，则将右孩子指针入队；,5.2二叉树的存储结构及实现,广度优先周游二叉树,templatevoidBiTree:LeverOrder(BiNode*root)LinkQueue*aQueue;BiNode*pointer=root;if(pointer)aQueue.EnQueue(pointer);,首先创建一个空队列；判断根节点是否为空，如果不空，根节点入队,while(!aQueue.Empty()pointer=aQueue.Front()-next-data;/取队列首结点BiNode*q=aQueue.DeQueue();coutdatavalue();/访问当前结点if(pointer-lchild)/左子树进队列aQueue.EnQueue(pointer-lchild);if(pointer-rchild)/右子树进队列aQueue.EnQueue(pointer-rchild);/endwhile,队首出队（P），输出队首的值，将P的所有孩子（非0）入队重复第二步的工作，直到队空,二叉树算法设计练习,遍历二叉树是二叉树各种操作的基础，遍历算法中对每个结点的访问操作可以是多种形式及多个操作，根据遍历算法的框架，适当修改访问操作的内容，可以派生出很多关于二叉树的应用算法。,voidInOrder(BiNode*root)if(root=NULL)return;elseInOrder(root-lchild);coutdata;InOrder(root-rchild);,二叉树算法设计练习,设计算法求二叉树的结点