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

二、二叉树

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 creatTree() {
    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);
}

三、总结

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