14数据结构之三.pptVIP

数据结构之二 树型结构 四 二叉树的遍历 二叉树遍历的定义按照一定的规律不重复地访问 或取出结点中的信息 或对结点作其它的处理 二叉树中的每一个结点 2 二叉树遍历的顺序如果用L D R分别表示遍历左子树 访问根结点 遍历右子树 则对二叉树的遍历可以有下列六种 3 6 组合 LDR LRD DLR DRL RDL RLD 若再限定先左后右的次序 则只剩下三种组合 LDR 中序遍历 LRD 后序遍历 DLR 前序遍历 以下遍历以该树为例 前序遍历 规则如下 若二叉树为空 则退出 否则 访问处理根结点 前序遍历左子树 前序遍历右子树 如上图的前序遍历结果为abdehicfg 中序遍历 规则如下 若二叉树为空 则退出 否则 中序遍历左子树 访问处理根结点 中序遍历右子树 如上图的中序遍历结果为dbheiafcg 后序遍历 规则如下 若二叉树为空 则退出 否则 后序遍历左子树 后序遍历右子树 访问处理根结点 如上图的后序遍历结果为dhiebfgca 普通树的遍历 先根次序遍历树规则 若树为空 则退出 否则先根访问树的根结点 然后先根遍历根的每棵子树 后根次序遍历树规则 若树为空 则退出 否则先依次后根遍历每棵子树 然后访问根结点 后根遍历次序为whdexafbsmonijtucr 先根遍历次序为rawxdhebfcstimonju 五 根据两种遍历顺序确定树结构 由两种顺序确定树结构遍历二叉树有三种规则 前序遍历 根 左子树 右子树 中序遍历 左子树 根 右子树 后序遍历 左子树 右子树 根 由于前序遍历的第一个字符和后序遍历的最后一个字符为根 中序遍历中位于根左方的子串和位于根右方的子串分别反映了左子树和右子树的结构 因此二叉树的形态可以由其中序与后序或者前序与中序唯一确定 但无法反映左子树和右子树结构的前序遍历与后序遍历却不能做到这一点 因此这两个遍历顺序可对应多种二叉树的形态 试题 1 二叉树T 已知其先根遍历是1243576 数字为结点的编号 以下同 后根遍历是4275631 则该二叉树的可能的中根遍历是 A 4217536B 2417536C 4217563D 24157362 已知一棵二叉树的结点名为大写英文字母 其中序与后序遍历的顺序分别为 CBGEAFHDIJ与CGEBHFJIDA 则该二叉树的先序遍历的顺序为什么 六 二叉排序树 所谓二叉排序树是指具有下列性质的非空二叉树 若根结点的左子树不空 则左子树的所有结点值均小于根结点值 若根结点的右子树不空 则右子树的所有结点值均不小于根结点值 根结的左右树也分别为二叉排序树 显然 对二叉排序树进行中序遍历 可得出结点值递增的排序序列 例 638192457 6 3 1 4 2 5 8 7 9 七 最优二叉树 哈夫曼树 概念在具有n个带权叶结点的二叉树中 使所有叶结点的带权路径长度之和 即二叉树的带权路径长度 为最小的二叉树 称为最优二叉树 又称最优搜索树或哈夫曼树 即最优二叉树使 Wk 第k个叶结点的权值 Pk 第k个叶结点的带权路径长度 达到最小 哈夫曼树的应用 哈夫曼编码发明Huffman于1952年提出一种编码方法 该方法完全依据字符出现概率来构造异字头的平均长度最短的码字 有时称之为最佳编码 一般就叫作Huffman编码 编码过程例 编码字符组成abcdef频度 单位 次 4513121695 e f e f c e f c b e f c b d e f c b d a e f c b d a 0 1 1 1 1 1 0 0 0 0 每个编码都不是另一个的前缀 试题 最优前缀编码 也称Huffman编码 这种编码组合的特点是对于较频繁使用的元素给与较短的唯一编码 以提高通讯的效率 下面编码组合哪一组不是合法的前缀编码 A 00 01 10 11 B 0 1 00 11 C 0 10 110 111 D 1 01 000 001 用二叉树来表示表达式 对于表达式a b c d e f g有如下二叉树 如果按照中序遍历此二叉树 得到的中序序列就是a b c d e f g如果改用先序序列遍历 就将得到 a bc de fg而后序遍历将得到abc de fg 从表达式