Java 数据结构：从树形结构到二叉树详解

一、树形结构

1. 树形结构的概念

树是一种非线性的数据结构，它模拟了自然界中树的结构。树形结构由若干个节点 (node) 组成，这些节点之间存在明确的层次关系。

树是递归定义的。

结点的度：一个结点含有子树的个数称为该结点的度。

树的度：一棵树中，所有结点度的最大值称为树的度。

叶子结点或终端结点：度为 0 的结点称为叶结点。

双亲结点或父结点：指向其他节点的节点。

孩子结点或子结点：被其他节点指向的节点。

根结点：每个树形结构有一个根节点 (root)，它是树的起点。

非终端结点或分支结点：度不为 0 的结点。

兄弟结点：具有相同父结点的结点互称为兄弟结点。

堂兄弟结点：双亲在同一层的结点互为堂兄弟。

树结构示意图

2. 树的表示形式

常见的表示法包括：双亲表示法、孩子表示法、孩子双亲表示法、孩子兄弟表示法等。

class Node {
    int value; // 数据域
    Node firstChild; // 第一个孩子
    Node nextBrother; // 下一个兄弟
}

孩子兄弟表示法示意图

二、二叉树

1. 概念

二叉树是一种非线性数据结构，其中每个节点最多有两棵树，分别称为左子树和右子树。

二叉树示意图

2. 二叉树类型

二叉树主要分为满二叉树和完全二叉树。

2.1 满二叉树

定义：每个节点都有 0 个或 2 个子节点。

特点：没有只有 1 个子节点的节点。

满二叉树示意图

2.2 完全二叉树

定义：除最后一层外，所有层都完全填满，且最后一层节点尽可能靠左。

应用：常用于堆的实现。

完全二叉树示意图

3. 二叉树的性质

若规定根结点的层数为 1，则一棵非空二叉树的第 i 层上最多有 2^(i-1) 个结点 (i>0)。
若规定只有根结点的二叉树的深度为 1，则深度为 K 的二叉树的最大结点数是 (2^k)-1 (k>=0)。
对任何一棵二叉树，如果其叶结点个数为 n0，度为 2 的非叶结点个数为 n2，则有 n0＝n2＋1。
具有 n 个结点的完全二叉树的深度 k 为 log(n+1) 上取整。
对于具有 n 个结点的完全二叉树，如果按照从上至下从左至右的顺序对所有节点从 0 开始编号，则对于序号为 i 的结点有：

若 i>0，双亲序号：(i-1)/2；i=0，i 为根结点编号，无双亲结点若 2i+1<n，左孩子序号：2i+1，否则无左孩子若 2i+2<n，右孩子序号：2i+2，否则无右孩子

4. 二叉树的存储

二叉树的存储结构分为：顺序存储和类似于链表的链式存储。二叉树的链式存储是通过一个一个的节点引用起来的，常见的表示方式有二叉和三叉表示方式。

// 孩子表示法
class Node {
    int val; // 数据域
    Node left; // 左孩子的引用
    Node right; // 右孩子的引用
}

// 孩子双亲表示法
class Node1 {
    int val; // 数据域
    Node left; // 左孩子的引用
    Node right; // 右孩子的引用
    Node parent; // 当前节点的根节点
}

5. 二叉树的基本操作

5.1 手动创建二叉树

public static class Node {
    public char val;
    public Node left;
    public Node right;

    public Node(char val) {
        this.val = val;
    }
}

// 根节点
public Node createTree() {
    Node A = new Node('A');
    Node B = new Node('B');
    Node C = new Node('C');
    Node D = new Node('D');
    Node E = new Node('E');
    Node F = new Node('F');
    Node G = new Node('G');
    Node H = new Node('H');
    A.left = B;
    A.right = C;
    B.left = D;
    B.right = E;
    E.right = H;
    C.left = F;
    C.right = G;
    return A;
}

5.2 二叉树的遍历

1. 前序遍历

访问顺序：根节点 → 左子树 → 右子树

// 前序遍历
public void preOrder(Node root) {
    if (root == null) {
        return;
    }
    System.out.println(root.val);
    preOrder(root.left);
    preOrder(root.right);
}

2. 中序遍历

访问顺序：左子树 → 根节点 → 右子树

// 中序遍历
public void inOrder(Node root) {
    if (root == null) {
        return;
    }
    inOrder(root.left); // 修正：原代码误写为 preOrder
    System.out.println(root.val);
    inOrder(root.right); // 修正：原代码误写为 preOrder
}

3. 后序遍历

访问顺序：左子树 → 右子树 → 根节点

// 后序遍历
public void postOrder(Node root) {
    if (root == null) {
        return;
    }
    postOrder(root.left); // 修正：原代码误写为 preOrder
    postOrder(root.right); // 修正：原代码误写为 preOrder
    System.out.println(root.val);
}

5.3 二叉树操作方法实现

// 获取节点个数
public int size(Node root) {
    if (root == null) {
        return 0;
    }
    return size(root.left) + size(root.right) + 1;
}

// 获取叶子节点个数
public int getLeafNodeCount(Node root) {
    if (root == null) {
        return 0;
    }
    if (root.left == null && root.right == null) {
        return 1;
    }
    return getLeafNodeCount(root.left) + getLeafNodeCount(root.right);
}

// 获取第 k 层节点个数
public int getLevelNodeCount(Node root, int k) {
    if (root == null) {
        return 0;
    }
    if (k == 1) {
        return 1;
    }
    return getLevelNodeCount(root.left, k - 1) + getLevelNodeCount(root.right, k - 1);
}

// 获取二叉树高度
public int getHeight(Node root) {
    if (root == null) {
        return 0;
    }
    int leftH = getHeight(root.left);
    int rightH = getHeight(root.right);
    return Math.max(leftH, rightH) + 1;
}

// 找 val 元素是否存在
public Node find(Node root, char val) {
    if (root == null) {
        return null;
    }
    if (root.val == val) {
        return root;
    }
    Node ret = find(root.left, val);
    if (ret != null) {
        return ret;
    }
    return find(root.right, val);
}

三、总结

树形结构是一种'一对多'的层级数据组织方式，而二叉树作为它的特殊形式（每个节点最多俩孩子），凭借满二叉树、完全二叉树等细分类型，以及明确的性质（比如节点数和层数的关系），成了实际开发中常用的结构。我们可以用不同方式存储二叉树，也能通过前/中/后序遍历'逛遍'树里的每个节点——掌握这些内容，不仅能理解数据的组织逻辑，也能为后续学更复杂的树结构（比如红黑树）打牢基础。