第十讲 遍历算与优先队列.ppt

二叉树的应用 2009/03/31 本讲主要内容： 二叉树的非递归周游算法及应用 二叉树的存储结构与实现 堆与优先队列 深度优先周游算法 先根次序： 头节点入栈 弹出栈顶，访问 右子树入栈 左子树入栈 递归周游树、计算表达式 求叶子数 递归求树的高度 智坚 非递归深度优先周游算法 先根次序： 头节点入栈 弹出栈顶，访问 右子树入栈 左子树入栈 求树的叶子数？求树的高度？ visite() ？ 中根次序（对称序）深度优先周游算法 非空头节点入栈; c = leftChild(c); until (c==NULL) 弹出栈顶，访问 c = rightChild(c); 直到栈空且c==NULL; 后根次序周游算法 非空子树头节点入栈！; c = top(s); if (左子树为空) if ( 右子树也为空) c = pop(s); visit(c); else push( rightChild(c)); else push( leftChild(c)); 直到栈空; 后根次序周游算法 后根次序周游算法与迷宫问题 广度优先进行树的周游 算法步骤： 访问节点 访问儿子节点 （依次从左到右） 重复 2 二叉树的存储实现 —— 顺序表示 将完全二叉树上序号为i (广度优先顺序)的结点存储在数组 下标为i - 1的元素中（如下图）。  完全二叉树： 对于具有n个结点的完全二叉树，如果按照从上（根结点）到下（叶结点）和从左到右的顺序对二叉树中的所有结点从0开始到n-1进行编号，则对于任意的下标为i的结点，有：(1) 如果 i = 0，是根结点。如果i＞0，则其父结点的下标为 ?(i-1)/2? ；(2) 如果2i＋1≤n－1，则下标为i的结点的左子结点的下标为2i＋1；否则，i结点没有左子结点：(3) 如果2i+2≤n－1，则下标为i的结点的右子结点的下标为2i+2。否则，i的结点没有右子结点。 顺序存储二叉树的操作 H-elements[(i-1)/2] 找父节点 H-elements[i*2+1] 找左子节点 H-elements[i*2+2] 找右子节点 H-elements[0] 将二叉树改造成完全二叉树，再按顺序存储表示。  二叉树顺序存储的特点 建立、插入、删除、访问等操作很简便。 最大占用空间与二叉树的高度相关。在某些情况下空间冗余较大。 二叉树的应用  —— 堆与 优先队列 (Priority queue) priority queue is a data structure that allows at least the following two operations: insert, which does the obvious thing. delete_min, which finds, returns and removes the minimum element in the heap. ADT of PriorityQueue Operations PriorityQueue createEmptyPriQueue( void) 创建一个空优先队列。 int isEmpty(PriorityQueue S) 若S为空，则返回1，否则返回0。 void add(PriorityQueue S, DataType e) 向S中添加元素e。 DataType min(PriorityQueue S) 返回S中的最小元素。 void removeMin(PriorityQueue S) 删除S中的最小元素。 end ADT PriorityQueue 作业： 上机布置 通过后缀表达式生成树 算法： 每个数字生成为一个叶结点，入栈。 算符生成为一个结点，弹出两个叶结点，先右后左，链接生成一棵子树，入栈。 直到表达式尾，弹出最后一个元素作为树根。 * * + 6 / 2 8 + 6 / 2 8 先根深度优先周游算法 + 6 / 2 8 中根次序深度优先周游算法 + 6 / 2 8 右顾左探 到头了 继续退栈 + 6 / 2 8 从(0,1)开始顺时针序列依次探查 N (i-1,j) w (i,j-1) ? (i, j) E (i,j+1) S (i+1,j) drection[4][2] 令k取0,1,2,3之一，