一篇文章彻底弄懂 Java 中二叉树

简介

二叉树是计算机科学中最基础的数据结构之一，它的设计是为了解决组织和搜索排列在内存连续空间上的数据的问题，使得在处理数据时可以更方便地遍历和查找。本文将针对 Java 中的二叉树进行详细地介绍，包括定义、构造、遍历、查找等操作，希望可以为读者提供全面的知识点和实例操作，以便更好地理解和应用二叉树。

定义

二叉树是由一组节点组成的层次结构，每个节点包含一个元素，最多有两个子节点。一个节点有右子节点和左子节点，如果一个节点没有子节点，那么这个节点就是叶子节点。我们也可以定义二叉树是一个满足以下条件的树：每个节点最多有两个子节点，并且所有的子节点都可以被视为一颗二叉树。

构造

二叉树的构造可以通过节点对象和其中的指针进行操作。具体地，我们可以定义一个节点类 Node，包含节点的元素 value 和指针 left、right，它们分别指向左子节点和右子节点。我们还可以定义一个二叉树类 BinaryTree，包含一个 root 节点，它指向整棵树的根节点。代码示例如下：

class Node {
    int value;
    Node left;
    Node right;

    public Node(int value) {
        value = value;
        left = null;
        right = null;
    }
}

class BinaryTree {
    Node root;

    public BinaryTree() {
        root = null;
    }
}

对于二叉树的构造，我们可以通过节点的指针进行链接，例如下面创建一棵树：

BinaryTree tree = new BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);

这棵树的结构如下：

           1
         /   \
        2     3
      /   \
     4     5

遍历

二叉树的遍历有三种基本方式：前序遍历、中序遍历和后序遍历。它们的实现都基于递归思想，递归函数会先递归访问左子树或右子树，然后回溯到根节点继续递归到下一个子树，直到结束。以下是三种遍历方式的代码示例：

前序遍历

前序遍历即按照“根-左-右”的顺序进行遍历，可以用递归实现：

void preorderTraversal(Node node) {
    if (node != null) {
        System.out.println(node.value);
        preorderTraversal(node.left);
        preorderTraversal(node.right);
    }
}

这个函数会先输出当前节点的值，然后递归调用自身访问左子树和右子树，直到整棵树被遍历完成。

中序遍历

中序遍历即按照“左-根-右”的顺序进行遍历，可以用递归实现：

void inorderTraversal(Node node) {
    if (node != null) {
        inorderTraversal(node.left);
        System.out.println(node.value);
        inorderTraversal(node.right);
    }
}

这个函数会先访问左子树，然后输出当前节点的值，再递归调用自身访问右子树。

后序遍历

后序遍历即按照“左-右-根”的顺序进行遍历，可以用递归实现：

void postorderTraversal(Node node) {
    if (node != null) {
        postorderTraversal(node.left);
        postorderTraversal(node.right);
        System.out.println(node.value);
    }
}

这个函数会先递归访问左子树和右子树，然后输出当前节点的值。

查找

二叉树的查找是指在二叉树中查找某个特定节点的操作。通常情况下，我们可以采用二叉查找的方法，即先遍历左子树或右子树，再向下寻找目标节点，直到找到或找不到。以下是在 Java 中实现查找的代码示例：

boolean contains(Node node, int value) {
    if (node == null) {
        return false;
    }

    if (value == node.value) {
        return true;
    } else if (value < node.value) {
        return contains(node.left, value);
    } else {
        return contains(node.right, value);
    }
}

这个函数接收一个节点和一个值作为参数，如果这个节点为空，则返回 false；如果节点的值等于目标值，则返回 true；如果目标值小于节点的值，则在左子树中递归查找；如果目标值大于节点的值，则在右子树中递归查找。

示例

示例一

我们使用上面的代码构造一棵二叉树，然后对这棵树进行遍历。代码如下：

public static void main(String[] args) {
    BinaryTree tree = new BinaryTree();
    tree.root = new Node(1);
    tree.root.left = new Node(2);
    tree.root.right = new Node(3);
    tree.root.left.left = new Node(4);
    tree.root.left.right = new Node(5);

    System.out.println("前序遍历:");
    tree.preorderTraversal(tree.root);

    System.out.println("中序遍历:");
    tree.inorderTraversal(tree.root);

    System.out.println("后序遍历:");
    tree.postorderTraversal(tree.root);
}

输出结果如下：

前序遍历:
1
2
4
5
3
中序遍历:
4
2
5
1
3
后序遍历:
4
5
2
3
1

说明前、中、后序遍历依次输出了二叉树的每一个节点。

示例二

我们使用上面的代码查找二叉树中的某个节点是否存在。代码如下：

public static void main(String[] args) {
    BinaryTree tree = new BinaryTree();
    tree.root = new Node(1);
    tree.root.left = new Node(2);
    tree.root.right = new Node(3);
    tree.root.left.left = new Node(4);
    tree.root.left.right = new Node(5);

    int target = 3;
    if (tree.contains(tree.root, target)) {
        System.out.println("节点 " + target + " 存在于二叉树中");
    } else {
        System.out.println("节点 " + target + " 不存在于二叉树中");
    }
}

输出结果如下：

节点 3 存在于二叉树中

说明 3 这个节点存在于二叉树中。

结论

本文对 Java 中的二叉树进行了全面的讲解，包括定义、构造、遍历、查找等方面。二叉树的应用非常广泛，如数据搜索、排序、图形绘制等等。了解和掌握二叉树是计算机科学和编程的基本功之一，希望读者可以通过本文深入了解和掌握它的操作，以便在工作和生活中灵活运用。