叉搜索树 1小时 堆与优先队列 0.5小时 Huffman树及其应用 1小时 排序算法的时间代价 0.5小时 叉树知识点总结 0.5小时 4、重点难点 (1)二叉树的各种存储方法及效率分析。 (2)二叉树的周游策略。 (3)堆的建立与 Huffman编码树的基本思想。 (4)二叉树的非递归周游算法 5、授课提示 采用灵活的教学方式,通过提出问题、分析问题、解决问题这样的基本流程,加深学生 对重难点知识的理解,并培养其创新意识和创新能力 下面是二叉树的重点和难点内容的讲授注意事项 (1)二叉树的性质 性质7.对于具有n个结点的完全二叉树,结点按层次由左到右编号,则对任一 结点i(0≤i≤n-1)有 (1)如果i=0,则结点i是二叉树的根结点;若1>0,则其父结点编号是(i-1)2」。 (2)当2i+1≤n-1时,结点i的左子结点是2i+1,否则结点i没有左子结点。 当2i+2≤n-1时,结点i的右子结点是2i+2,否则结点i没有右子结点。 (3)当i为偶数且0<i<n时,结点i的左兄弟是结点i-1,否则结点i没有左兄弟。 当i为奇数且计1<n时,结点i的右兄弟是结点i+1,否则结点i没有右兄弟。 这个性质的证明,只需证明(2),(1)和(3)即可由结论(2推得。 (2)二叉树的前序、中序、后序周游的递归算法和使用栈的非递归算法 基于二叉树的递归定义,这三种深度优先周游的递归定义是 (1)前序法其递归定义是:访问根结点;按前序周游左子树:按前序周游右子树 (2)中序法其递归定义是:按中序周游左子树;访问根结点;按中序周游右子树 (3)后序法其递归定义是:按后序周游左子树;按后序周游右子树;访问根结点。2 二叉搜索树 1 小时 堆与优先队列 0.5 小时 Huffman 树及其应用 1 小时 排序算法的时间代价 0.5 小时 二叉树知识点总结 0.5 小时 4、重点难点 （1） 二叉树的各种存储方法及效率分析。 （2） 二叉树的周游策略。 （3） 堆的建立与 Huffman 编码树的基本思想。 （4） 二叉树的非递归周游算法。 5、授课提示 采用灵活的教学方式，通过提出问题、分析问题、解决问题这样的基本流程，加深学生 对重难点知识的理解，并培养其创新意识和创新能力。 下面是二叉树的重点和难点内容的讲授注意事项 （1）二叉树的性质 性质 7. 对于具有 n 个结点的完全二叉树，结点按层次由左到右编号，则对任一 结点 i（0 ≤ i ≤ n - 1）有 （1）如果 i = 0，则结点 i 是二叉树的根结点；若 i＞0，则其父结点编号是(i - 1)/2。 （2）当 2i + 1 ≤ n - 1 时，结点 i 的左子结点是 2i + 1，否则结点 i 没有左子结点。 当 2i + 2 ≤ n - 1 时，结点 i 的右子结点是 2i + 2，否则结点 i 没有右子结点。 （3）当 i 为偶数且 0 < i < n 时，结点 i 的左兄弟是结点 i - 1，否则结点 i 没有左兄弟。 当 i 为奇数且 i+1 < n 时，结点 i 的右兄弟是结点 i + 1，否则结点 i 没有右兄弟。 这个性质的证明，只需证明(2)，(1) 和(3)即可由结论(2)推得。 （2）二叉树的前序、中序、后序周游的递归算法和使用栈的非递归算法 基于二叉树的递归定义，这三种深度优先周游的递归定义是： (1) 前序法其递归定义是：访问根结点；按前序周游左子树；按前序周游右子树。 (2) 中序法其递归定义是：按中序周游左子树；访问根结点；按中序周游右子树。 (3) 后序法其递归定义是：按后序周游左子树；按后序周游右子树；访问根结点