树

树的详细讲解

1. 什么是树？

树是一种分层数据结构，由一个根节点及其子节点组成。与现实中的树不同，计算机中的树是“倒置”的，根节点在上，叶子节点在下。

树的基本特点：

1. 树中的任意两个节点之间有且仅有一条路径连通。
2. 一棵树如果有 ( n ) 个节点，则一定有 ( n - 1 ) 条边。
3. 树中不包含回路。

---

2. 树的基本概念

2.1 常见术语

• 节点：树中的每个元素。
• 根节点：没有父节点的节点，树的起点。
• 子节点：某节点的直接下属。
• 父节点：某节点的直接上级。
• 兄弟节点：同一父节点的子节点。
• 叶子节点：没有子节点的节点。
• 节点的高度：从节点到叶子节点的最长路径所包含的边数。
• 节点的深度：从根节点到该节点的路径所包含的边数。
• 节点的层数：节点的深度 + 1。
• 树的高度：根节点的高度。

2.2 树的分类

1. 普通树：每个节点可以有任意多个子节点。
2. 二叉树：每个节点最多有两个子节点（左子节点和右子节点）。
3. 满二叉树：每层的节点数都达到最大值。
4. 完全二叉树：除了最后一层，其他层的节点数都达到最大值，且最后一层的节点从左到右依次排列。
5. 平衡二叉树：每个节点的左右子树高度差的绝对值不超过 1。
6. 二叉搜索树（BST）：每个节点的值大于左子树中所有节点的值，小于右子树中所有节点的值。
7. 红黑树、B 树、Trie 树：特殊用途的树。

---

3. 二叉树的存储

3.1 链式存储

• 使用节点对象表示树，包含数据域和指向左右子节点的指针。
• 每个节点通常有 3 个字段：
  • 数据字段 data。
  • 左子节点指针 left。
  • 右子节点指针 right。

Java 示例：

class TreeNode {
    int data;
    TreeNode left, right;

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

3.2 顺序存储

• 使用数组存储二叉树：
  • 根节点存储在索引 1（或 0）处。
  • 左子节点存储在索引 ( 2i ) 处，右子节点存储在索引 ( 2i + 1 ) 处。
• 适合完全二叉树，非完全二叉树可能浪费存储空间。

---

4. 二叉树的遍历

二叉树的遍历方式分为深度优先遍历和广度优先遍历。

4.1 深度优先遍历

1. 前序遍历：

   • 访问顺序：根节点 → 左子树 → 右子树。
   • 递归实现：

     public void preOrder(TreeNode root) {
         if (root == null) return;
         System.out.println(root.data);
         preOrder(root.left);
         preOrder(root.right);
     }

   • 非递归实现（栈）：

     public void preOrder(TreeNode root) {
         if (root == null) return;
         Stack<TreeNode> stack = new Stack<>();
         stack.push(root);
         while (!stack.isEmpty()) {
             TreeNode node = stack.pop();
             System.out.println(node.data);
             if (node.right != null) stack.push(node.right);
             if (node.left != null) stack.push(node.left);
         }
     }

2. 中序遍历：

   • 访问顺序：左子树 → 根节点 → 右子树。
   • 递归实现：

     public void inOrder(TreeNode root) {
         if (root == null) return;
         inOrder(root.left);
         System.out.println(root.data);
         inOrder(root.right);
     }

   • 非递归实现（栈）：

     public void inOrder(TreeNode root) {
         if (root == null) return;
         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.println(current.data);
             current = current.right;
         }
     }

3. 后序遍历：

   • 访问顺序：左子树 → 右子树 → 根节点。
   • 递归实现：

     public void postOrder(TreeNode root) {
         if (root == null) return;
         postOrder(root.left);
         postOrder(root.right);
         System.out.println(root.data);
     }

4.2 广度优先遍历（层次遍历）

• 访问顺序：按层从上到下，从左到右。
• 使用队列实现：

  public void levelOrder(TreeNode root) {
      if (root == null) return;
      Queue<TreeNode> queue = new LinkedList<>();
      queue.add(root);
      while (!queue.isEmpty()) {
          TreeNode node = queue.poll();
          System.out.println(node.data);
          if (node.left != null) queue.add(node.left);
          if (node.right != null) queue.add(node.right);
      }
  }

---

5. 二叉树的应用场景

1. 表达式树：用来解析数学表达式。
2. 二叉搜索树（BST）：支持高效插入、查找、删除操作。
3. 红黑树/B 树：用于数据库索引、集合类的实现（如 TreeMap、TreeSet）。
4. Huffman 树：用于数据压缩算法。
5. Trie 树：高效存储和查找字符串集合。

树是一个功能强大的数据结构，它的多种变体在实际开发中都有广泛的应用。