1.前言

我们来学习下二叉树。二叉树是树结构中最常见的一种。我们在学习算法和数据结构的过程中。在了解了基础的数组和链表等线性结构后，一般会继续学习树和图这种非线性结构。树是一种特殊的图，是只有一个连通的无环图。树的细分下面有很多种，比如二叉树，二叉搜索树，平衡二叉树，红黑树，B树，B+树等等。我们这里先学习二叉树。

2.二叉树介绍

二叉树是一种树形数据结构，其中每个节点最多有两个子节点。它是数据结构中非常基础且广泛应用的一种结构，特别是在计
算机科学中处理排序、查找等操作时经常使用。

3.二叉树的基本定义

二叉树是一种树形结构，其中每个节点有以下特点：

• 根节点：二叉树的第一个节点，没有父节点。
• 节点：树中的每个元素，包含一个数据元素。
• 子节点：每个节点最多有两个子节点，通常分别被称为“左子节点”和“右子节点”。
• 叶节点：没有任何子节点的节点，位于树的最底层。
• 边：连接节点的线条，表示父子关系。

二叉树通常可以通过以下几种方式表示：

• 链式表示法：每个节点是一个对象，包含节点的数据以及指向左右子节点的指针（引用）。
• 数组表示法：如果节点编号从 1 开始，则对于节点 i，其左子节点的位置是 2*i，右子节点的位置是 2*i + 1，父节点的位置是 i/2（取整）。

4.二叉树的分类

二叉树有很多变种，以下是常见的几种：

• 普通二叉树：每个节点最多有两个子节点，没有任何额外的要求或限制。
• 满二叉树（Full Binary Tree）：每个节点要么是叶子节点，要么有两个子节点。
• 完全二叉树（Complete Binary Tree）：除了最后一层外，每一层都是满的，且最后一层的节点都集中在最左边。
• 平衡二叉树（Balanced Binary Tree）：左右子树的高度差的绝对值不超过1（例如 AVL 树）。
• 二叉搜索树（Binary Search Tree，BST）：对每个节点，左子树的值都小于该节点的值，右子树的值都大于该节点的值。二叉搜索树有助于高效地执行查找、插入和删除操作。
• 红黑树（Red-Black Tree）：是一种自平衡的二叉搜索树，具有额外的颜色约束（红色或黑色），用于保证树的平衡性，避免退化成链表。

ps：

1. 在做题目和工作中对于满二叉树和完全二叉树，我们要了解他们的特性
2. 满二叉树：我们知道他每个节点要么是叶子节点，要么有两个子节点。所以通过高度，我们可以直接获取道到节点的数量。高度为h的满二叉树有 2^(h+1) - 1 个节点。比如高度为2的满二叉树，有2^(2+1) - 1 = 7个节点。

    1
   / \
  2   3
 / \ / \
4  5 6  7 // 高度0是根节点有1个，高度为1的节点有2个，高度为2的节点有4个。

1. 完全二叉树：除了最后一层外，每一层都是满的，最后一层的节点都集中在最左边。可以根据这个特性，搜索的时候减少比较的次数。

5.二叉树的基本操作

二叉树支持以下基本操作：

• 遍历：访问树的每一个节点。常见的遍历方式包括：
• 前序遍历（Pre-order）：根节点 -> 左子树 -> 右子树。
• 中序遍历（In-order）：左子树 -> 根节点 -> 右子树。对于二叉搜索树，中序遍历会按照升序顺序输出所有节点。
• 后序遍历（Post-order）：左子树 -> 右子树 -> 根节点。
• 层序遍历（Level-order）：按层次从上到下、从左到右访问每一个节点。
  ps：

1. 怎么记忆前，中，后序遍历的顺序呢？前中后是根据访问根节点的顺序来记忆。比如前序遍历，根节点在前面，所以是前序遍历。中序遍历，根节点在中间，所以是中序遍历。后序遍历，根节点在后面，所以是后序遍历。所谓访问当前节点（根节点），就是去实现对当前节点的逻辑。
2. 层序遍历，我们可以使用队列来实现。按照标准模版来写就可以了。

5.1 前序遍历

递归实现：

public void preorderTraversal(TreeNode root) {
    if (root != null) {
        System.out.print(root.value + " ");  // 访问当前节点
        preorderTraversal(root.left);        // 遍历左子树
        preorderTraversal(root.right);       // 遍历右子树
    }
}

非递归实现（使用栈）：

public void preorderTraversal(TreeNode root) {
    if (root == null) return;
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        System.out.print(node.value + " ");
        if (node.right != null) stack.push(node.right);  // 右子树先入栈
        if (node.left != null) stack.push(node.left);    // 左子树后入栈
    }
}

5.2 中序遍历

中序遍历的顺序是：左子树，当前节点，右子树。

递归实现：

public void inorderTraversal(TreeNode root) {
    if (root != null) {
        inorderTraversal(root.left);  // 遍历左子树
        System.out.print(root.value + " ");  // 访问当前节点
        inorderTraversal(root.right); // 遍历右子树
    }
}

非递归实现（使用栈）：

public void inorderTraversal(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode current = root;
    while (current != null || !stack.isEmpty()) {
        // 向左走到底
        while (current != null) {
            stack.push(current);
            current = current.left;
        }
        current = stack.pop();  // 当前节点
        System.out.print(current.value + " ");
        current = current.right; // 转向右子树
    }
}

5.3 后序遍历

后序遍历的顺序是： 左子树，右子树，当前节点。

递归实现：

public void postorderTraversal(TreeNode root) {
    if (root != null) {
        postorderTraversal(root.left);  // 遍历左子树
        postorderTraversal(root.right); // 遍历右子树
        System.out.print(root.value + " ");  // 访问当前节点
    }
}

非递归实现（使用栈）：

public void postorderTraversal(TreeNode root) {
    if (root == null) return;
    Stack<TreeNode> stack = new Stack<>();
    TreeNode prev = null;
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode current = stack.peek();
        // 如果是叶节点或当前节点的子节点已经访问过了，访问当前节点
        if (current.left == null && current.right == null || 
            prev != null && (prev == current.left || prev == current.right)) {
            System.out.print(current.value + " "); // 访问当前节点
            stack.pop();
            prev = current;
        } else {
            if (current.right != null) stack.push(current.right);  // 右子树先入栈
            if (current.left != null) stack.push(current.left);    // 左子树后入栈
        }
    }
}

5.4 层序遍历

层序遍历是按照树的层次，从上到下、从左到右逐层访问节点，通常使用队列实现。

实现方法（使用队列）：

public void levelOrderTraversal(TreeNode root) {
    if (root == null) return;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        TreeNode current = queue.poll();
        System.out.print(current.value + " "); // 访问当前节点
        if (current.left != null) queue.offer(current.left);  // 左子树
        if (current.right != null) queue.offer(current.right); // 右子树
    }
}

ps：递归实现能让我们对三种遍历方式，有一个直观的认识。但是非递归实现才能让我们在脑海中认清楚，在遍历过程中的顺序是什么样子的，对解决问题有一个更好的认识。

5.5 总结：遍历方式对比

5.6 插入操作：

根据树的类型不同，插入操作的复杂度和方法有所不同。对于二叉搜索树，通常需要遵循左小右大的规则，依次查找合适位置插入新节点。

5. 7 删除操作：

删除节点时，根据被删除节点的子节点情况进行不同的处理：

如果节点是叶子节点，直接删除。

如果节点有一个子节点，将该节点的父节点直接连接到该子节点。

如果节点有两个子节点，找到该节点的中序后继或前驱节点，替代删除节点。

查找操作：对于二叉搜索树，查找某个元素时，从根节点开始，若目标值小于当前节点值，则查找左子树；若目标值大于当前节点值，则查找右子树，直到找到目标或到达叶节点。

高度计算：树的高度是从根节点到叶节点的最长路径上的节点数。对于一个节点，左右子树的高度差可以用来判断该树是否平衡。

6. 二叉树的时间复杂度

在二叉树中，常见操作的时间复杂度如下（假设树的高度为 h）：

• 查找：O(h)
• 插入：O(h)
• 删除：O(h)
• 遍历：O(n)，其中 n 是节点的总数

对于平衡二叉树（如 AVL 树、红黑树），高度 h 保持在 O(log n) 的水平，因此这些操作的时间复杂度是 O(log n)。

7. 二叉树的应用

二叉树广泛应用于许多领域，以下是一些典型应用：

• 二叉搜索树：在数据库系统中用于存储有序数据，支持高效的查找、插入、删除操作。
• 表达式树：在计算机编译器中，二叉树用于表示数学表达式的结构，叶节点代表操作数，非叶节点代表操作符。
• 堆（Heap）：堆是完全二叉树的一种变种，常用于实现优先队列，支持高效的插入和删除最小/最大元素操作。
• 哈夫曼编码树：在数据压缩算法中，哈夫曼编码树使用二叉树来表示字符的编码。
• 决策树：在机器学习中，决策树用于分类和回归问题，通过二叉树的结构进行判断。

8. 示例代码：二叉树的基本实现

// 二叉树节点定义
class TreeNode {
    int value;
    TreeNode left, right;

    TreeNode(int value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

// 二叉树类
class BinaryTree {
    TreeNode root;

    // 插入一个新的节点
    public TreeNode insert(TreeNode root, int value) {
        if (root == null) {
            return new TreeNode(value);
        }

        if (value < root.value) {
            root.left = insert(root.left, value);
        } else if (value > root.value) {
            root.right = insert(root.right, value);
        }

        return root;
    }

    // 中序遍历
    public void inorderTraversal(TreeNode root) {
        if (root != null) {
            inorderTraversal(root.left);
            System.out.print(root.value + " ");
            inorderTraversal(root.right);
        }
    }

    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();
        tree.root = tree.insert(tree.root, 50);
        tree.root = tree.insert(tree.root, 30);
        tree.root = tree.insert(tree.root, 20);
        tree.root = tree.insert(tree.root, 40);
        tree.root = tree.insert(tree.root, 70);
        tree.root = tree.insert(tree.root, 60);
        tree.root = tree.insert(tree.root, 80);

        System.out.println("中序遍历结果：");
        tree.inorderTraversal(tree.root);
    }
}

输出：

中序遍历结果：
20 30 40 50 60 70 80

9.总结

二叉树是一种非常基础的数据结构，在计算机科学中有广泛的应用。根据不同的应用需求，二叉树可以被改进为多种变种，如二叉搜索树、平衡二叉树、堆等。通过不同的遍历方式和操作，二叉树为许多计算机算法提供了高效的支持。

通过基础二叉树，我们了解了树的基本定义和相关的遍历和构建操作。刷题和工作中，我们经常使用的是特殊的二叉树。比如二叉搜索树，平衡二叉树，红黑树，堆等来解决实际的问题。

随后我们还会学习多叉树，比如b树，b+树，线段树等去解决特定场景下的问题。