树的深度结点F.ppt

* * currentPos = i = 1 53 17 78 09 23 45 65 87 i 53 17 78 09 23 45 65 87 i * * currentPos = i = 0 53 17 78 09 23 45 65 87 i 17 78 09 23 45 65 87 i 09 53 * * 17 78 09 23 45 65 87 i 53 17 78 09 23 45 65 87 i 17 53 09 17 65 23 45 78 87 53 data * 下滑调整的算法设计思路： ①设置调整的初始位置（从start开始），把其值赋给临时变量temp（用于交换） ②若没有调整完，temp与其子女的小者比较 ③若比小者小，则中断这次比较，否则，进行交换 ④设置新的调整位置 重复②～④，直到调整完 * * * 每次插入都加在堆的最后，再自下向上执行调整，使之重新形成堆。 最小堆的插入 * * 在堆中插入新元素11 17 78 09 23 45 65 87 i 11 53 j 53 17 78 09 23 45 65 87 j 11 23 i 最小堆的向上调整 * * 17 78 09 45 65 87 j 11 53 i 23 17 53 11 78 09 17 45 65 87 23 j i * * 最小堆的删除 把第一个元素删除，把最后一个元素移到第一个元素的位置，再自上向下滑动，使之重新形成堆。 53 11 78 09 17 45 65 87 23 i * * 最小堆的删除 练习与讨论： 1. 将下列用数组存放的关键字调整成最小堆。 {09，53，46，78，87，92，11，65} 2. 插入关键字23，形成新的最小堆。 3. 删除最小的关键字重新调整成最小堆 4. 分析插入和删除一个元素后重新调整为最小堆算法的时间复杂度。 5月5日，周一 * 5月7日 * * A B C E D G F 树的先根次序遍历 当树非空时 访问根结点 依次先根遍历根的各棵 子树 树先根遍历 ： 对应二叉树前序遍历： 树的先根遍历结果与其对应二叉树 表示的前序遍历结果相同 结论：树的先根遍历可以借助对应二叉树的前序遍历算法实现 A B C D E F G ABEFCDG ABEFCDG * A B C E D G F 树的后根次序遍历 当树非空时 依次后根遍历根的各棵子树 访问根结点 树后根遍历 ： 对应二叉树中序遍历： 树的后根遍历结果与其对应二叉树 表示的中序遍历结果相同 结论：树的后根遍历可以借助对应二叉树的中序遍历算法实现 A B C D E F G EFBCGDA EFBCGDA * 将一般树转换为二叉树表示就是用树的子女-兄弟表示来存储树的结构。 森林与二叉树表示的转换可以借助树的二叉树表示来实现。 6.6.3 森林与二叉树的转换 * T1 T2 T3 A T1 T2 T3 A F H B C D G I J E K F B C D E G H I K J A B C E D H I K J F G 3 棵树的森林 各棵树的二叉树表示 森林的二叉树表示 1. 森林转换为二叉树 * 2. 二叉树转换为森林 T1 A B C D E A B C E D H I K J F G F G T2 H I J K T3 练习与讨论： 1.给出下图所示森林的先序、后序遍历序列； 把森林转换为二叉树； 给出二叉树的前序、中序遍历序列。 * A B C D E F G H I J K 2.把下图所示的二叉树转换为森林。 * B C E D G F A H I K J L M 两棵树，你砍哪一棵？ 老道长给弟子们讲道，弟子们希望老道长给些开示，老道长给弟子们出了一道题，让他们回答。 老道长：“如果你去山上砍树，正好面前有两棵树，一棵粗，另一棵细，你会砍哪一棵?” 问题一出，大家都说：“当然砍那棵粗的了。 * 老道长一笑，说：“那棵粗的不过是一棵普通的杨树，而那棵细的却是红松，现在你们会砍哪一棵?” 两棵树，你砍哪一棵？ 弟子们一想，红松比较珍贵，就说：“当然砍红松了，杨树又不值钱!” 老道长带着不变的微笑看着弟子们，问：“那如果杨树是笔直的，而红松却七歪八扭，你们会砍哪一棵?” 弟子们觉得有些疑惑，就说:“如果这样的