第6章二叉树答案.doc

"第6章二叉树答案" 本资源是关于二叉树的知识点总结，涵盖了二叉树的基本概念、性质、存储结构、遍历算法等方面的知识点。 一、基本概念 * 二叉树的定义：二叉树是一种特殊的树结构，即每个结点最多有两个孩子结点（左孩子和右孩子）。 * 二叉树的性质：二叉树的每个结点的关键字值大于其左子树所有结点的关键字值，小于其右子树所有结点的关键字值。 二、存储结构 * 二叉链表法（link-rlink）：用链表法存储二叉树，每个结点有三个指针域：左孩子指针、右孩子指针和父结点指针。 * 二叉树的存储结构：二叉树可以用链表法或数组法存储，每个结点占用三个指针域的空间。 三、遍历算法 * 前序遍历（Pre-order Traversal）：先访问根结点，然后访问左子树和右子树。 * 中序遍历（In-order Traversal）：先访问左子树，然后访问根结点，最后访问右子树。 * 后序遍历（Post-order Traversal）：先访问左子树和右子树，然后访问根结点。 四、性质和应用 * 二叉树的高度：二叉树的高度是从根结点到最远叶子结点的路径长度。 * 二叉树的结点数：二叉树的结点数是从根结点到所有叶子结点的路径长度之和。 * 二叉树的应用：二叉树广泛应用于计算机科学和信息技术领域，如数据库索引、文件系统、编译器等。 五、常见题型 * 判断二叉树的正确性：判断二叉树的性质是否正确，如高度、结点数、左右子树的关系等。 * 二叉树的遍历：实现二叉树的前序、中序、后序遍历算法。 * 二叉树的构建：根据给定的结点集合构建二叉树。 六、重要结论 * 二叉树的高度最多为n-1，其中n是结点数。 * 二叉树的结点数最多为2^n-1，其中n是高度。 * 二叉树的遍历次序有六种：前序、中序、后序、层序、对称序和逆序。 本资源涵盖了二叉树的基本概念、存储结构、遍历算法、性质和应用，希望能够帮助读者更好地理解和掌握二叉树的知识点。