数据结构_2013new讲解.pptVIP

* * * * * * * * * * * * * * * * 二叉树遍历的应用 应用三：由遍历序列恢复二叉树 思考： 已知二叉树，可以确定其先序序列、中序序列和后序序列，所以遍历序列中包含了二叉树的逻辑信息。 那么，如果已知二叉树的某种遍历序列，是否能够确定这颗二叉树呢？如果能，应该如何做呢？ 举例：如果已知某个二叉树的先序遍历结果是{1，2，3}，那么它的二叉树应该是什么结构？画画看！！ 大纲 算法复杂度 查找与排序 抽象数据类型 – 表、堆栈、队列 二叉树 二叉查找树 哈夫曼编码 哈夫曼编码 性质1：序列中，没有任何一个元素是另外一个元素的前缀 利用扩充二叉树，同时满足性质1，即为哈夫曼编码 哈夫曼树 对于一棵具有外部节点1,……,n的扩充二叉树，对应的编码串长度为 L(i)为从根到外部节点的长度，即路径数。 F(i)为字符i的频率。 对于给定频率，WEP最小，即为哈夫曼树。 哈夫曼编码 获得不同字符的频率 建立哈夫曼树，外部节点用字符串中的字符表示，外部节点的权重为该字符的频率。 遍历从根到外部节点的路径，得到每个字符的编码。 用字符的编码来代替字符串中的字符。 例子 //重点 ababaafffaacdcdcdefefefefff a:6 b:2 c:3 d:3 e:4 f:9 5 a b c f d e 6 2 4 3 3 9 7 11 16 27 0 0 0 0 0 1 1 1 1 1 a表示为 00 b表示为010 c表示为011 d表示为100 e表示为101 f表示为11 Exercise 给出dataanddataanddata的哈夫曼编码结果 谢谢！ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 二叉树 遍历算法 前序（前根）遍历 中序（中根）遍历 后序（后根）遍历 二叉树的遍历（递归实现） 二叉树遍历的定义 二叉树的遍历是二叉树中经常要用到的一种操作。因为在实际应用问题中，常常需要按一定顺序对二叉树中的每个结点逐个进行访问，查找具有某一特点的结点，然后对这些满足条件的结点进行处理。 二叉树的遍历是指按照某种顺序访问二叉树中的每个结点，使每个结点被访问一次且仅被访问一次。 通过一次完整的遍历，可使二叉树中结点信息由非线性排列变为某种意义上的线性序列。也就是说，遍历操作使非线性结构线性化 二叉树的遍历（递归实现） 二叉树遍历的分类 二叉树由根结点、根结点的左子树和根结点的右子树三部分组成。因此，只要依次遍历这三部分，就可以遍历整个二叉树。 若以D、L、R分别表示访问根结点、遍历根结点的左子树、遍历根结点的右子树，则二叉树的遍历方式有六种：DLR、LDR、LRD、DRL、RDL和RLD。 如果限定先左后右，则只有前三种方式 DLR（称为先序遍历） LDR（称为中序遍历） LRD（称为后序遍历）。 下面的内容如果没有特别说明 都采用二叉链表作为二叉树的存储结构 二叉树的遍历（递归实现） 先序遍历（DLR） 先序遍历的递归过程为： 若二叉树为空，遍历结束。否则： 1：访问根结点； 2：先序遍历根结点的左子树； 3：先序遍历根结点的右子树。 先序遍历二叉树的递归算法如下： void PreOrder（BiTree bt） {/*先序遍历二叉树bt*/ if (bt==NULL) return; /*递归调用的结束条件*/ Visite（bt-data）; /*访问结点的数据域*/ PreOrder（bt-lchild）; /*先序递归遍历bt的左子树*/ PreOrder（bt-rchild）; /*先序递归遍历bt的右子树*/ } A D B C D L R A D L R D L R B D C D L R 先序遍历序列：A B D C 先序遍历: 二叉树的遍历（递归实现） 中序遍历（LDR） 中序遍历的递归过程为： 若二叉树为空，遍历结束。否则， （1）中序遍历根结点的左子树； （2）访问根结点； （3）中序遍历根结点的右子树。 中序遍历二叉树的递归算法如下： void InOrder（BiTree bt） {/*中序遍历二叉树bt*/ if (bt==NULL) return; /*递归调用的结束条件*/ InOrder（bt-lchild）; /*中序递归遍历bt的左子树*/ Visite（bt-data）; /*访问结点的数据域*/ InOrder（bt-rchild）;