本文共 1368 字，大约阅读时间需要 4 分钟。

树的概述

树是一种非常重要的数据结构，它与线性结构的主要区别在于树中的节点具有明显的层级关系，并且一个节点可以对应多个节点。树的定义如下：

树是n（n≥0）个节点的有限集。当n=0时，称为空树。在任意一棵非空树中：

树的定义本身体现了递归的思想，根的子树节点同时作为子树的根节点。

在树中，节点的层级关系非常重要。根节点为第一层，其直接子节点为第二层，以此类推。树的深度（Depth）是从根节点到最远叶节点的层数，而树的高度（Height）则是从最远叶节点到根节点的层数。根据本文的定义，根节点的深度为1，最深叶节点的深度即为树的深度。

节点在树中扮演着核心角色：

• 每个节点可以有任意多个子节点，也可以没有子节点，称为树叶节点。
• 具有相同父亲的节点称为兄弟节点。
• 子节点之间没有顺序关系，这种树称为无序树。

森林是由两棵或更多互不相交的树组成的集合。

树的实现

树可以采用顺序存储结构或链式存储结构实现。以下是几种常见的实现方法：

1. 父节点表示法

这种方法使用数组存储节点，通过父节点索引来表示子节点的关系。每个节点包含数据域和父节点索引，根节点的父节点索引为-1。这种方法的优点是简单且直观，但缺点是无法快速查找子节点。

2. 父子节点链表示法

为了方便查找子节点，增加一个子节点链表。每个节点保存子节点链表的头索引和父节点索引。这种方法能够快速找到子节点，但实现相对复杂。

3. 父子兄弟表示法

为了方便查找兄弟节点，增加两个索引：第一个子节点索引和右兄弟索引。这种方法通过两个引用关系来表示树的结构，能够在O(1)时间内查找子节点和兄弟节点。

树节点设计

树节点可以设计为以下形式：

private static class TreeNode {
    // 数据域
    Object data;
    // 父节点索引
    int parent;
    // 第一个子节点引用
    TreeNode firstChild;
    // 右兄弟节点引用
    TreeNode rightBrother;
    public TreeNode(Object data, int parent, TreeNode firstChild, TreeNode rightBrother) {
        this.data = data;
        this.parent = parent;
        this.firstChild = firstChild;
        this.rightBrother = rightBrother;
    }
}

这种设计能够通过两个引用关系（firstChild和rightBrother）直观地表示树的结构，并且查找某个节点的子节点或兄弟节点的时间复杂度为O(1)。

总结

本文作为树数据结构的入门文章，详细讲解了树的定义、节点特性以及树的实现方式。通过父节点表示法、父子节点链表示法和父子兄弟表示法，展示了树的三种常见实现方法。这些方法为后续学习特性化树（如二叉树、AVL树、红黑树）奠定了基础。