9 数据结构第五章知识点2.doc

二叉树是数据结构中的重要概念，它是一种特殊的树形数据结构，由n（n>=0）个节点组成。在二叉树中，n=0表示空二叉树，n>0则为非空二叉树，每个节点最多有两个子节点，即左子树和右子树。 1. 二叉树的五种形态： - 空二叉树：没有任何节点。 - 只有一个根节点的二叉树。 - 只有左子树的二叉树。 - 只有右子树的二叉树。 - 既有左子树又有右子树的二叉树。 2. 二叉树的特点： - 每个节点最多有两个子节点，不存在度大于2的节点。 - 左子树和右子树的顺序不可颠倒，单子树的左右属性需明确。 3. 单支树（左斜树和右斜树）： - 所有节点都只有左子树或只有右子树。 - 特性包括：同层只有一个节点，结点数等于其深度，高度最高时结点数最少，且只有一个度为0的结点，其余结点度为1。 4. 满二叉树： - 每个分支节点都有左右子树，叶子节点都在最底层。 - 特性包括：叶子只能出现在最底层，只有度为0和度为2的节点，结点数最多，高度固定时结点数最多。 5. 完全二叉树： - 是满二叉树的一种推广，满足特定条件的二叉树。 - 特性包括：满二叉树是完全二叉树的特殊情况，深度为k的完全二叉树，k-1层以上是满二叉树，叶子结点集中在最下层两侧，度为1的结点至多一个且只有左子树，高度最小。 6. 二叉树的性质： - 性质1：叶子结点数等于度为2的结点数加1。 - 性质2：第i层最多有2i-1个结点。 - 性质3：深度为k的二叉树最多有2k-1个结点。 - 性质4：n个结点的完全二叉树深度为log2n向上取整+1。 - 性质5：完全二叉树的层序编号规则。 7. 二叉树的遍历： - 前序遍历：根-左-右，如：ABCDFE。 - 中序遍历：左-根-右，如：BADFCE。 - 后序遍历：左-右-根，如：BFDECA。 - 层序遍历：从上到下，从左到右，如：ABCDEF。 8. 构造二叉树： - 通过前序、中序或后序遍历序列可以唯一确定二叉树结构。 9. 二叉树的存储结构： - 顺序存储结构：通常用数组实现，但不利于插入和删除操作。 - 二叉链表：每个节点包含数据域和两个指向子节点的指针。 10. 二叉树遍历算法（递归实现）： - 前序遍历：先访问根，然后递归遍历左子树和右子树。 - 中序遍历：先递归遍历左子树，然后访问根，最后遍历右子树。 - 后序遍历：先递归遍历左子树和右子树，最后访问根。 二叉树的概念和特性在实际应用中非常广泛，例如在文件系统、编译器设计、图形界面布局等领域。理解和掌握这些知识点对于进行有效的数据处理和算法设计至关重要。