05数据结构---树2

本章主要讲述树,其中包括树的基本概念;二叉树;二叉树的存储表示;二叉树的遍历及其应用;二叉树遍历的非递归算法;二叉树的计数;树与二叉树的转换;堆:将一组用数组存放的任意数据调整成堆,堆的插入操作,堆的删除操作;Huffman树及其应用:路径,路径长度,带权路径长度,等
展开查看详情

1. 第五章 树 东南大学计算机学院 方效林 方效林 本课件借鉴了清华大学殷人昆老师 和哈尔滨工业大学张岩老师的课件

2. 本章主要内容  树的基本概念  二叉树  二叉树的存储表示  二叉树的遍历及其应用  二叉树遍历的非递归算法  二叉树的计数  树与二叉树的转换  堆  Huffman 树及其应用 2

3. 堆 (Heap)Heap))  关键字按完全二叉树顺序存储在一维数组中  若 Ki  K2i+1 && Ki  K2i+2(Heap) 小于孩子 ) ,称为最小称为最小 堆  若 Ki  K2i+1 && Ki  K2i+2(Heap) 大于孩子 ) ,称为最小称为最大 不失一般性,称为最小只介绍最小堆 09 87 堆 17 65 78 53 23 45 78 87 45 65 09 31 53 31 17 23 完全二叉树顺序表示 完全二叉树顺序表示 Ki  K2i+1 && Ki  K2i+2 Ki  K2i+1 && Ki  3

4. 堆 (Heap)Heap))  将一组用数组存放的任意数据调整成堆  自下向上扫描 (Heap) 从 (Heap)n-2)/2)/2)/2 位置开始 ) ,称为最小向下调整 53 向下调整过程: 每次与更小的孩子交换,称为最小 17 78 直到没有孩子,称为最小或比两个孩子都小,称为最小则停止 i=3 09 45 65 87 2)/23 从 i = 3 开始扫描,称为最小这是由于共有 n=8 个 数,称为最小 从 i = (Heap)n-2)/2)/2)/2=3 开始扫描 (Heap) 即最后一个 叶子结点的父结点开始 ) ,称为最小 4 09 小于孩子,称为最小不用调整

5. 堆 (Heap)Heap))  将一组用数组存放的任意数据调整成堆  自下向上扫描 (Heap) 从 (Heap)n-2)/2)/2)/2 位置开始 ) ,称为最小向下调整 53 i=2)/2 向下调整过程: 每次与更小的孩子交换,称为最小 17 78 直到没有孩子,称为最小或比两个孩子都小,称为最小则停止 09 45 65 87 2)/23 扫描到 i = 2)/2 78 大于其中一孩子,称为最小向下调整 78 与孩子中更小的 69 交换 5

6. 堆 (Heap)Heap))  将一组用数组存放的任意数据调整成堆  自下向上扫描 (Heap) 从 (Heap)n-2)/2)/2)/2 位置开始 ) ,称为最小向下调整 53 向下调整过程: 每次与更小的孩子交换,称为最小 17 65 直到没有孩子,称为最小或比两个孩子都小,称为最小则停止 09 45 78 87 2)/23 78 与 69 已交换 6

7. 堆 (Heap)Heap))  将一组用数组存放的任意数据调整成堆  自下向上扫描 (Heap) 从 (Heap)n-2)/2)/2)/2 位置开始 ) ,称为最小向下调整 i=1 53 向下调整过程: 每次与更小的孩子交换,称为最小 17 65 直到没有孩子,称为最小或比两个孩子都小,称为最小则停止 09 45 78 87 2)/23 扫描到 i = 1 17 大于其中一孩子,称为最小向下调 整 17 与孩子中更小的 09 交换 7

8. 堆 (Heap)Heap))  将一组用数组存放的任意数据调整成堆  自下向上扫描 (Heap) 从 (Heap)n-2)/2)/2)/2 位置开始 ) ,称为最小向下调整 53 向下调整过程: 每次与更小的孩子交换,称为最小 09 65 直到没有孩子,称为最小或比两个孩子都小,称为最小则停止 17 45 78 87 2)/23 17 与 09 已交换 8

9. 堆 (Heap)Heap))  将一组用数组存放的任意数据调整成堆  自下向上扫描 (Heap) 从 (Heap)n-2)/2)/2)/2 位置开始 ) ,称为最小向下调整 53 向下调整过程: 每次与更小的孩子交换,称为最小 09 65 直到没有孩子,称为最小或比两个孩子都小,称为最小则停止 17 45 78 87 2)/23 继续向下进行判断 17 小于孩子,称为最小不用向下调整 9

10. 堆 (Heap)Heap))  将一组用数组存放的任意数据调整成堆  自下向上扫描 (Heap) 从 (Heap)n-2)/2)/2)/2 位置开始 ) ,称为最小向下调整 i=0 53 向下调整过程: 每次与更小的孩子交换,称为最小 09 65 直到没有孩子,称为最小或比两个孩子都小,称为最小则停止 17 45 78 87 2)/23 扫描到 i = 0 53 大于其中一孩子,称为最小 向下调整,称为最小 53 与更小的 09 交换 10

11. 堆 (Heap)Heap))  将一组用数组存放的任意数据调整成堆  自下向上扫描 (Heap) 从 (Heap)n-2)/2)/2)/2 位置开始 ) ,称为最小向下调整 09 向下调整过程: 每次与更小的孩子交换,称为最小 53 65 直到没有孩子,称为最小或比两个孩子都小,称为最小则停止 17 45 78 87 2)/23 53 与 09 已交换 11

12. 堆 (Heap)Heap))  将一组用数组存放的任意数据调整成堆  自下向上扫描 (Heap) 从 (Heap)n-2)/2)/2)/2 位置开始 ) ,称为最小向下调整 09 向下调整过程: 每次与更小的孩子交换,称为最小 53 65 直到没有孩子,称为最小或比两个孩子都小,称为最小则停止 17 45 78 87 2)/23 继续向下进行判断 53 大于其中一孩子,称为最小 53 与更小的 17 交换 12

13. 堆 (Heap)Heap))  将一组用数组存放的任意数据调整成堆  自下向上扫描 (Heap) 从 (Heap)n-2)/2)/2)/2 位置开始 ) ,称为最小向下调整 09 向下调整过程: 每次与更小的孩子交换,称为最小 17 65 直到没有孩子,称为最小或比两个孩子都小,称为最小则停止 53 45 78 87 2)/23 53 与 17 已交换 13

14. 堆 (Heap)Heap))  将一组用数组存放的任意数据调整成堆  自下向上扫描 (Heap) 从 (Heap)n-2)/2)/2)/2 位置开始 ) ,称为最小向下调整 09 向下调整过程: 每次与更小的孩子交换,称为最小 17 65 直到没有孩子,称为最小或比两个孩子都小,称为最小则停止 53 45 78 87 2)/23 继续向下进行判断,称为最小 53 大于孩子,称为最小 53 与更小的 2)/23 交换 14

15. 堆 (Heap)Heap))  将一组用数组存放的任意数据调整成堆  自下向上扫描 (Heap) 从 (Heap)n-2)/2)/2)/2 位置开始 ) ,称为最小向下调整 09 向下调整过程: 每次与更小的孩子交换,称为最小 17 65 直到没有孩子,称为最小或比两个孩子都小,称为最小则停止 2)/23 45 78 87 53 53 与 2)/23 已交换,称为最小 最终结果 15

16. 堆 (Heap)Heap))  堆的插入操作  先在堆 (Heap) 完全二叉树 ) 的最后增加一个叶子结点  从新增的叶子开始,称为最小逐步向上调整 09 17 65 在堆中插入 11 2)/23 45 78 87 53 初始 16

17. 堆 (Heap)Heap))  堆的插入操作  先在堆 (Heap) 完全二叉树 ) 的最后增加一个叶子结点  从新增的叶子开始,称为最小逐步向上调整 09 17 65 在堆中插入 11 2)/23 45 78 87 53 11 在完全二叉树的最后增加新结点 11 11 比父结点 2)/23 小,称为最小交换 17

18. 堆 (Heap)Heap))  堆的插入操作  先在堆 (Heap) 完全二叉树 ) 的最后增加一个叶子结点  从新增的叶子开始,称为最小逐步向上调整 09 17 65 在堆中插入 11 11 45 78 87 53 2)/23 交换后,称为最小 11 比父结点 17 小,称为最小交换 18

19. 堆 (Heap)Heap))  堆的插入操作  先在堆 (Heap) 完全二叉树 ) 的最后增加一个叶子结点  从新增的叶子开始,称为最小逐步向上调整 09 11 65 在堆中插入 11 17 45 78 87 53 2)/23 交换后,称为最小 11 比父结点 09 大,称为最小不交换 即为最终结果 19

20. 堆 (Heap)Heap))  堆的删除操作 (Heap) 只删除堆顶元素 )  将堆最后的元素覆盖堆顶,称为最小堆大小减 1  从堆顶开始逐步向下调整 (Heap) 与更小的孩子交换 ) 09 删除堆顶元素 17 65 2)/23 45 78 87 53 初始 20

21. 堆 (Heap)Heap))  堆的删除操作 (Heap) 只删除堆顶元素 )  将堆最后的元素覆盖堆顶,称为最小堆大小减 1  从堆顶开始逐步向下调整 (Heap) 与更小的孩子交换 ) 53 删除堆顶元素 17 65 2)/23 45 78 87 53 覆盖堆顶 09 ,称为最小堆大小减 1 53 比孩子 17 大,称为最小交换 21

22. 堆 (Heap)Heap))  堆的删除操作 (Heap) 只删除堆顶元素 )  将堆最后的元素覆盖堆顶,称为最小堆大小减 1  从堆顶开始逐步向下调整 (Heap) 与更小的孩子交换 ) 17 删除堆顶元素 53 65 2)/23 45 78 87 53 比孩子 2)/23 大,称为最小交换 22

23. 堆 (Heap)Heap))  堆的删除操作 (Heap) 只删除堆顶元素 )  将堆最后的元素覆盖堆顶,称为最小堆大小减 1  从堆顶开始逐步向下调整 (Heap) 与更小的孩子交换 ) 17 删除堆顶元素 2)/23 65 53 45 78 87 最终结果 23

24. Huffman 树  路径  树中一结点到另一结点之间的边构成两结点间路径  路径长度  路径上的边数  树的根到达树中每一结点有且仅有一条路径 1 2 3 4 5 6 7 24

25. Huffman 树  树根到结点的路径长度等于结点所处层次 k-1  左图树根到各结点路径长度 0,1,1,2)/2,2)/2,2)/2,2)/2,3  右图树根到各结点路径长度 0,1,1,2)/2,2)/2,2)/2,3,3  树的路径长度  各结点到根路径长度总和,称为最小 PL1=13 ,称为最小 PL2)/2=14 1 1 2 3 2 3 4 5 6 7 4 5 6 8 7 8 25

26. Huffman 树  带权路径长度  假设二叉树中每个叶结点有一个权值 wi ,称为最小到根的 路径长度为 li ,称为最小其他结点权值为 0 ,称为最小则有 n 个叶子 n -1 结点的树的带权路径长度为 WPL   w i  l i i 0 2)/2 7 4 5 2)/2 4 5 7 4 2)/2 5 7 WPL=2)/2*(Heap)2)/2+4+5+7)=36 WPL=2)/2+2)/2*4+3*(Heap)5+7)=46 WPL=7+2)/2*5+3*(Heap)4+2)/2)=35 带权路径长度达到最小的二叉树即为 Huffman 树 。 26 在 Huffman 树中,称为最小权值越大的结点离根越近。

27. Huffman 树  构造权值为 {ww1,w2)/2, …, wn} 的 Huffman 树  构造 n 棵二叉树的森林 F={wT1,T2)/2, …, Tn} ,称为最小每棵二 叉树 Ti 只有一个带权值为 wi 的根结点  重复以下步骤,称为最小直到只剩一棵树为止:  1. 在 F 中选两棵根结点权值最小的二叉树,称为最小作为左、 右子树构造一棵新的二叉树,称为最小新树的根结点权值等于 其左、右子树根结点权值之和  2)/2. 在 F 中删除这两棵二叉树  3. 把新构造的二叉树加入 F 27

28. Huffman 树 F: {w7} {w5} {w2)/2} {w4} F: {w7} {w5} {w6} F: {w7} {w11} F: {w18} 7 5 2)/2 4 7 5 6 7 11 18 2)/2 4 5 6 7 11 2)/2 4 5 6 2)/2 4 (Heap)a) 初始 (Heap)b) 合并 {w2)/2}{w4} (Heap)b) 合并 {w2)/2}{w4} (Heap)b) 合并 {w7}{w11} 28

29. Huffman 树  应用 1 :最佳判定树  判定树是二叉树,称为最小叶子结点是比较结果,称为最小其他结点 是比较过程  用 Huffman 树让平均判定次数最小 29