第四章_树的知识点.doc

第四章 树的知识点1. 基本概念和术语，必须掌握2. 二叉树的性质,几个引理。掌握引理的证明方法，并透彻掌握二叉树的性质，针对二叉树的性质，做一些习题，加深理解和记忆3 二叉树的顺序存储。要求掌握该存储方法，能够画出存储二叉树的数组图示，如图4.8（c），并掌握从一个节点访问其子节点、父节点之方法。4二叉树的链接存储。要求掌握节点结构，能够画出存储结构图，如图4.9（b）。链接存储结构上的相关操作，包括递归和非递归的，通过上机实现可达到完全掌握的程度。5线索二叉树。要求掌握概念，最终的线索二叉树为图4.19。线索二叉树的基本算法可通过上机掌握。6树和森林。树、森林和二叉树之间的转换必须掌握。树的顺序存储，掌握定理4.2，它是顺序存储的依据。已知先根（后根）遍历序列和次数序列，能画出相应的树结构，如图4.32。Father数组存储，非常简单，一看就会。7树的链接存储。Father链接结构，非常简单，一看就会。孩子链表链接结构，与图的邻接表存储原理相同，现在不看也可，等讲完图再看，会容易些。要求是，能够画出图4.38 孩子链表表示和图4.39父亲孩子链表表示，知其原理。左儿子右兄弟链接结构，是重点。要求掌握节点结构，能画出如图4.40 的左儿子右兄弟链接结构。并通过上机实现掌握其上的操作。8树和森林的遍历。掌握先根、后根、层次遍历的概念。已知一棵树或森林，能写出相应的遍历序列。9压缩与哈夫曼树。重点掌握哈夫曼树的构造过程，及哈夫曼编码的编码方法。要求能够画出图4.44的哈夫曼树，并给出编码。同时掌握相关概念，如前缀码，扩充二叉树、最优二叉查找树、内外通路长度等。学习指导：1 首先掌握概念和基本知识点。本文中列出的所有图示知识点最简单，可最先掌握。2 书上给出了很多算法。这些算法对应树结构上的一些操作。我们可以将这些算法看成是一些例题。书上给出这么多算法的主要目的是培养学生读算法、写算法的能力。有些算法非常经典，如利用栈实现的非递归算法和利用队列实现的层次遍历算法。经典的算法有助于我们学习别人的算法设计技巧，我们可以利用同样的技巧去解决其他类似的问题。我们看的算法多了，设计算法的思路就广。通过反复接触非递归的遍历算法，我们就知道凡是基于非递归遍历的问题，都可以用这个框架去解决。最重要的是同学们在头脑中要形成一种方法，解决问题的方法。把这些算法的学习看成是解决问题之方法的学习。学习最重要的是把前人的方法变成自己的方法。不要把这么多算法看成是一种压力，看成是一种开阔视野的东西，你会感谢这本书的作者，收集了这么多有思想的算法。书中的算法有些可能存在错误，在学习过程中注意发现。3 学习知识是为了应用。要选一本比较好的习题集，多做些题，有助于基本知识和求解问题之方法的掌握。4 学习是个循序渐进的过程，不是一蹴而就的事，要慢慢来。如果把会的知识看成是一个集合，那么学习的过程就是将这个集合逐渐扩大的过程。每个领域的知识都是一片海洋，谁都不可能掌握全部，但只要掌握了基本原理，融会贯通就等于是拥有了一片海洋。附录：1 先根遍历的非递归实现Public void iterativePreorder()IntBSTNode p=root;Stack travStack = new Stack();If (p!=null)travStack.push(p);while (!travStack.isEmpty()p=(IntBSTNode)travStack.pop();p.visit();if (p.right!=null)travStack.push(p.right);if (p.left!=null)travStack.push(p.left);2 后根遍历的非递归实现Public void iterativePostorder()BSTNode p=root, q=root;Stack travStack=new Stack();While (p!=null)for (;p.left!=null;p=p.left) travStack.push(p);while (p!=null &(p.right=null | p.right=q)p.visit();q=p;if (travStack.isEmpty() return;p= (BSTNode) travStack.pop();travStack.push(p);p=p.right;3 中根遍历的非递归实现Public void iterativeInorder()IntBSTNode p=root;Stack travStack =new Stack();While (p!=null) While (p!=null)If (p.right!=null)travStack.push(p.right);travStack.push(p);p=p.left;p=(IntBSTNode)travStack.pop();while (!travStack.isEmpty()&p.right=null)p.visi