软件技术基础数据结构.pptVIP

第二章 常用数据结构及其运算 进栈与出栈 栈的应用 ? 实现数制转换 ? 实现函数的递归 ? 实现表达式求值：根据输入的表达式 计算运算结果。 4.3.2 栈的基本操作 ? ?初始化 inistack(S): 构造一个空栈S，准备存放数据 ? 入栈操作 push(S,x)： 将数据元素x插入栈S，使x成为S的栈顶元素 ? 出栈操作 pop(S)： 当栈不空时返回栈顶元素为该函数的值，然后移除栈顶元素 ? 判栈空 emptystack(S)： 若S为空栈则该函数值为1，否则为0。 1. 栈的顺序存储结构及栈的运算 两种基本策略： ? 广度遍历 ? 深度遍历 ? 广度遍历策略（层次遍历） 广度遍历方法：从上到下、从左到右访问各结点 适用于顺序存储结构 ?深度遍历策略 二叉树由根、左子树、右子树三部分组成 二叉树的遍历可以分解为： 1）访问根（D） 2）遍历左子树（L） 3）遍历右子树（R） 有六种遍历方法： D L R，L D R，L R D， D R L，R D L，R L D 二、各种遍历的思想 1 . 先序遍历（DLR） 2 . 中序遍历（LDR） 3. 后序遍历（RLD） 1 . 先序遍历（DLR） ? 先序遍历（DLR）思想 若二叉树非空，则依次进行以下操作 （1）访问根结点； （2）先序遍历左子树； （3）先序遍历右子树； 2. 中序遍历（LDR） ? 中序遍历（LDR）思想 若二叉树非空，则依次进行以下操作 （1）中序遍历左子树； （2）访问根结点； （3）中序遍历右子树； 3. 后序遍历（LRD） ? 后序遍历（LRD）思想 若二叉树非空，则依次进行以下操作 （1）后序遍历左子树； （2）后序遍历右子树； （3）访问根结点； 三、遍历的递归算法 ? 前序遍历（DLR） ? 中序遍历（DLR） ? 后序遍历（LRD） 4.5.4 二叉树的应用 4.5 树与二叉树 1 6 4 5 3 2 PL=0+1×2+2×2+3=9 例： 4 3 6 2 5 1 PL=0+1+2×2+3＋4=12 ? 树的带权路径长度：树中所有叶子结点的 带权路径长度之和。 wk ---叶子结点的权值， lk ---叶子结点到根结点的路径长度。 4.5 树与二叉树 4.5.4 二叉树的应用 ? 结点的带权路径长度：从该结点到树根之间的路径长度与该结点上权值的乘积。 (a) WPL=7*2+5*2+2*2+4*2=36 (b) WPL=7*3+5*3+2*1+4*2=46 (c) WPL=7*1+5*2+2*3+4*3=35 (哈夫曼树) a b c d 7 5 2 4 d a c b 7 5 4 2 a b c d 7 5 2 4 4.5 树与二叉树 4.5.4 二叉树的应用 例： (a) (b) (c) 4.5 树与二叉树 4.5.4 二叉树的应用 ? 哈夫曼树：WPL最小的二叉树称最优二叉树 或哈夫曼（huffman）树。 ① 由给定的n个权值{w1,w2,…,wn}构成n棵二叉树的集合F={T1,T2,…,Tn}，每棵树只有一个权值为Wi的根结点； ② 在F中选取两棵根结点权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和； ③ 将新二叉树加入F中，并去除原两棵树； ④ 重复②、③，直到F中只含一棵树，即huffman树 4.5.4 二叉树的应用 4.5 树与二叉树 （2）哈夫曼树的构造 a b c d a b 7 5 c 2 d 4 b 5 c 2 d 4 a c 2 d 4 a b 7 5 2 4 7 5 6 7 11 18 (a) (b) (c) (d) ? 哈夫曼编码(可用于信息的二进制编码) 1) 不等长即时可译码（前缀码） A B C D 电文“ABACCDA”码长 00 01 10 11 14 bit(自然码) 0 00 1 01 9 bit(非即时可译) 01 001 0001 00001 21 bit(即时可译) 4.5 树与二叉树 4.5.4 二叉树的应用