二叉树基础及常见类型

二叉树基础及常见类型

二叉树是计算机科学中最重要的基础数据结构之一。本文将从基本概念出发，详细介绍二叉树的各种类型及其特点，并探讨二叉树的实现方式。通过本文的学习，你将对二叉树有一个全面而深入的理解。

二叉树基础及常见类型

二叉树是一种常见的数据结构，它由节点和连接节点的边组成。每个节点最多有两个子节点，分别称为左子节点和右子节点。二叉树的基本概念包括：

• 父节点：每个节点上方直接相连的节点。
• 子节点：每个节点下方直接相连的节点。
• 子树：以子节点为根的树。
• 根节点：最上方没有父节点的节点。
• 叶子节点：最下层没有子节点的节点。
• 深度/高度：从根节点到最下方叶子节点经过的节点个数。

几种常见的二叉树

满二叉树

满二叉树的特点是每一层的节点都是满的，整棵树像一个正三角形。如果满二叉树的深度为 (h)，那么总节点数就是 (2^h - 1)。

完全二叉树

完全二叉树的特点是每一层的节点都紧凑靠左排列，除了最后一层外，其他每层都必须是满的。完全二叉树的一个重要特点是，如果从左到右从上到下对它的每个节点编号，那么父子节点的索引存在明显的规律。

二叉搜索树

二叉搜索树（BST）是一种特殊的二叉树，其定义是：对于树中的每个节点，其左子树的所有节点的值都要小于这个节点的值，右子树的所有节点的值都要大于这个节点的值。这种特性使得二叉搜索树在查找、插入和删除操作中具有很高的效率。

平衡二叉树

平衡二叉树是一种特殊的二叉树，它的每个节点的左右子树的高度差不超过 1。这种结构保证了树的高度为 (O(\log N))，从而提高了增删查改的效率。

自平衡二叉树

自平衡二叉树是在增删节点时能够自动保持平衡的二叉树，最经典的例子是红黑树。保持树的平衡性，最关键的就是“旋转”操作。

二叉树的实现方式

二叉树最常见的实现方式是链式存储结构，每个节点包含指向左右子节点的指针。此外，还可以使用数组存储或哈希表表示等方法。

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { this.val = x; }
}

在某些场景下，还可以使用哈希表来表示二叉树，其中键是父节点ID，值是子节点ID的列表。

HashMap<Integer, List<Integer>> tree = new HashMap<>();
tree.put(1, Arrays.asList(2, 3));
tree.put(2, Collections.singletonList(4));
tree.put(3, Arrays.asList(5, 6));