树简介 | 小菜鸟

树（Tree）：层次结构的数据结构基础

树是一种非线性数据结构，由节点（Node）和边（Edge）组成，呈现层次化的分支关系。它广泛应用于文件系统、数据库索引、决策分析等场景，是理解更复杂数据结构（如二叉树、B 树）的基础。

树的核心概念与特性

基本定义

树是由n（n ≥ 0）个节点组成的有限集合：

当n = 0时，称为空树。
当n > 0时，有且仅有一个根节点（Root），其余节点分为若干个互不相交的子集，每个子集本身也是一棵树（称为子树）。

关键术语

节点的度：一个节点拥有的子节点数量（如叶子节点的度为 0）。
树的度：树中所有节点的最大度数（反映树的 “分支能力”）。
父节点与子节点：若节点A是节点B的直接前驱，则A是B的父节点，B是A的子节点。
叶子节点：度为 0 的节点（无任何子节点）。
深度：从根节点到当前节点的路径长度（根节点深度为 0，子节点深度为父节点深度 + 1）。
高度：从当前节点到最深叶子节点的路径长度（叶子节点高度为 0，父节点高度为子节点高度的最大值 + 1）。

核心特性

唯一性：根节点唯一，非根节点有且仅有一个父节点。
无环性：任意两个节点之间的路径唯一，不存在环路。
层次性：节点按 “根→子树” 的层次关系组织。

树的表示方式

树的存储需体现节点间的父子关系，常见表示方法有以下两种：

1. 父节点表示法（数组存储）

原理

用数组存储所有节点，每个节点记录自身数据和父节点在数组中的索引。
根节点的父索引通常设为-1（无父节点）。

代码结构

// 父节点表示法
class ParentTree<T> {
    private Node<T>[] nodes; // 存储所有节点的数组

    // 节点结构
    static class Node<T> {
        T data;       // 节点数据
        int parent;   // 父节点的数组索引（根节点为-1）

        Node(T data, int parent) {
            this.data = data;
            this.parent = parent;
        }
    }

    // 示例：构建一棵树
    public ParentTree(int size) {
        nodes = new Node[size];
        // 根节点（索引0，父索引-1）
        nodes[0] = new Node<>("根", -1);
        // 子节点（索引1，父索引0）
        nodes[1] = new Node<>("子1", 0);
        // 子节点（索引2，父索引0）
        nodes[2] = new Node<>("子2", 0);
    }
}

优缺点

优点：快速查找父节点（通过索引直接访问），空间开销小。
缺点：查找子节点需遍历整个数组（效率低）。

2. 孩子链表表示法（数组 + 链表）

原理

用数组存储所有节点，每个节点通过链表记录其所有子节点。
数组元素包含节点数据和指向第一个子节点的指针；链表节点记录子节点数据和下一个子节点的指针。

代码结构

// 孩子链表表示法
class ChildTree<T> {
    private Node<T>[] nodes; // 存储所有节点的数组

    // 数组中的节点（非叶子节点）
    static class Node<T> {
        T data;               // 节点数据
        ChildNode<T> firstChild; // 指向第一个子节点的链表

        Node(T data) {
            this.data = data;
            this.firstChild = null;
        }
    }

    // 链表中的子节点
    static class ChildNode<T> {
        T data;                 // 子节点数据
        ChildNode<T> nextSibling; // 指向下一个子节点

        ChildNode(T data, ChildNode<T> next) {
            this.data = data;
            this.nextSibling = next;
        }
    }

    // 示例：构建一棵树
    public ChildTree(int size) {
        nodes = new Node[size];
        // 根节点（数组索引0）
        nodes[0] = new Node<>("根");
        // 根节点的第一个子节点
        nodes[0].firstChild = new ChildNode<>("子1", 
            new ChildNode<>("子2", null)); // 子1的下一个兄弟是子2
    }
}

优缺点

优点：快速查找所有子节点（通过链表遍历），适合频繁访问子树的场景。
缺点：查找父节点需遍历整个数组（效率低），空间开销略大（需存储链表指针）。

树的分类

按不同维度，树可分为以下类别：

1. 按有序性划分

无序树：节点的子节点无顺序关系（如家族树中 “子女” 无先后之分）。
有序树：节点的子节点按固定顺序排列（如二叉树的 “左子树” 和 “右子树” 有明确顺序）。

2. 按节点的子树数量划分

二叉树：每个节点最多有 2 棵子树（左子树和右子树），是应用最广的树结构（如二叉查找树、平衡二叉树）。
B 树 / B + 树：多路平衡查找树，每个节点可拥有多个子树（如 B 树的度通常大于 2），常用于数据库索引。
其他：如三叉树（每个节点最多 3 棵子树）、n 叉树等。

树的应用场景

文件系统：目录与文件的层次关系（根目录→子目录→文件）。
数据库索引：B + 树用于加速数据查询（如 MySQL 的 InnoDB 引擎）。
决策树：机器学习中用于分类与回归（如 ID3、C4.5 算法）。
XML/HTML 解析：标签的嵌套结构可用树表示（DOM 树）