数据结构与算法课件：树与二叉树.ppt

层序遍历所谓按层遍历，即是从根结点开始逐层向下遍历，直到最后一层对于同一层的结点，由左到右遍历各结点同一层中的结点相继被访问，同时，它们之间的相对次序也决定着它们孩子结点的相对次序。即同一层中的结点u和结点v，若先遍历u再遍历v，则u的孩子结点的遍历也早于v的孩子结点的遍历按层进行遍历先访问最上面一层即0层中的元素，输出1然后依次访问1的子结点2和3再继续访问2的子结点和3的子结点依此类推，得到的层序遍历结果是：1,2,3,4,5,6,7层序遍历算法二叉树层序遍历的算法遍历的非递归实现仍然将一棵二叉树分为三部分：根、左子树和右子树。从根开始遍历二叉树时，根的左子树和右子树的遍历不能同时进行，只能先遍历一棵子树，同时保存二叉树中尚不能遍历部分的信息，留待一棵子树处理完毕后再处理分析二叉树的遍历过程可知，使用栈来保存相关信息先序遍历算法在进入左子树进行处理之前，需要在栈中保存右子树的相关信息，以便当左子树处理完毕，能够根据保存的线索找到右子树的根。所以，栈中保存右子树的根即可程序中序遍历算法中序遍历时，先进行左子树的遍历，然后遍历根，再遍历右子树。所以栈中保存根的信息，遍历完左子树后，从栈中找到根，访问根，同时也能容易地找到右子树程序后序遍历算法类似于中序遍历过程，在进入左子树遍历之前，需要先保存根的信息。当左子树遍历结束，从栈中找到根，但此时因为右子树尚未遍历，所以根并不能从栈中弹出，仍需要保存在栈中，只有当右子树也遍历结束后，才能访问根栈中保存的结点需要入栈两次出栈两次。为了能有所区别，二叉树结点入栈时，附带一个标记位flag。第一次出栈时，并不访问结点。第二次出栈时才访问它将二叉树结点和标记组合在一起，定义新的栈的类型，专用于非递归实现二叉树的后序遍历过程typedefstruct SNode //进栈带标记结点{ BinTNodebtreeNode; //二叉树结点 intflag; //标记}StackTNode; typedefstruct{ //用于后序遍历的栈 StackTNodeelement[maxSize]; inttop; //栈顶位置}SeqBTreeStackforPostT;程序二叉树的应用可以使用二叉树来表示一个表达式，这样的二叉树称为表达式树2*y*(a+3*y)-b画出表达式树先根据运算符的优先级对表达式加括号去掉最外层括号。中间的运算符为根，前后两部分分别对应于左子树和右子树对左子树递归执行步骤②对右子树递归执行步骤②当遇到空串时，递归结束例5-12已知算术表达式的中缀形式为A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为（）A．-A+B*C/DEB．-A+B*CD/EC．-+*ABC/DED．-+A*BC/DE答案：D?第四节堆及优先队列前一种关系表明，任何一个分支结点的值都不大于它子结点的值，所以树根结点的值是全部结点中的最小值。这样的堆称为最小堆或小根堆后一种关系表明，任何一个分支结点的值都不小于它子结点的值，故树根结点的值是全部结点中的最大值。这样的堆称为最大堆或大根堆树根结点称为堆顶堆的定义中还隐含了递归的含义，当用完全二叉树的形式表示堆时，树中的任意一棵子树都可以构成堆，并且保持与原来同样的性质最大堆中任何结点的子树仍是最大堆最小堆中任何结点的子树仍是最小堆最小堆和最大堆堆的类型定义#defineHeapSize30 //堆的容量typedefintELEMType; //元素类型typedefstructHeap{ ELEMTypeheap[HeapSize]; //存放元素的数组 intn; //堆中当前元素个数};堆的基本操作intcreatHeap(maxHeap*H,ELEMTypearr[],intn); //创建堆intinsertHeap(maxHeap*H,ELEMTypex); //在堆中插入元素xintdeleteHeap(maxHeap*H,ELEMType*x); //删除堆顶元素intisHeapEmpty(maxHeap*H); //如果堆为空，则返回1，否则返回0intisHeapFull(maxHeap*H); //如果堆为满，则返回1，否则返回0最大堆的类型定义#defineHeapSize30 //堆的容量typedefintELEMType; //元素类型typedefstructmaxHeap{ ELEMTypeheap[Heap