Java实现数据结构之二叉树|极客教程

Java实现数据结构之二叉树

什么是二叉树

二叉树是数据结构中的一种基础类型，它由节点组成，每个节点最多有两个子节点，分别称为左子节点和右子节点。二叉树可以为空，如果非空的二叉树中的每个节点都有一个左子节点和一个右子节点，那么这个二叉树称为满二叉树。二叉树还有一种特殊的形式，即完全二叉树，它是由若干层节点组成，除了最后一层外，每一层的节点数都是最大可能的。

二叉树节点的定义与实现

在Java中，我们可以通过类来实现二叉树节点的定义。每个节点包含一个值和指向左子节点和右子节点的指针。下面是一个简单的二叉树节点的实现代码：

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }
}

二叉树的遍历方法

1. 前序遍历

前序遍历是指先访问根节点，然后递归地遍历左子树和右子树。在Java中，可以通过递归的方式实现前序遍历：

public void preOrder(TreeNode root) {
    if (root != null) {
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }
}

2. 中序遍历

中序遍历是指先递归地遍历左子树，然后访问根节点，最后递归地遍历右子树。在Java中，可以通过递归的方式实现中序遍历：

public void inOrder(TreeNode root) {
    if (root != null) {
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }
}

3. 后序遍历

后序遍历是指先递归地遍历左子树和右子树，最后访问根节点。在Java中，可以通过递归的方式实现后序遍历：

public void postOrder(TreeNode root) {
    if (root != null) {
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val + " ");
    }
}

二叉树的层次遍历

层次遍历是按层次逐级访问树中的所有节点，通常使用队列来实现。在Java中，可以通过队列实现二叉树的层次遍历：

public void levelOrder(TreeNode root) {
    if (root == null) {
        return;
    }

    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);

    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        System.out.print(node.val + " ");

        if (node.left != null) {
            queue.add(node.left);
        }

        if (node.right != null) {
            queue.add(node.right);
        }
    }
}

二叉树的构建与测试

下面我们可以通过一个简单的示例来构建一棵二叉树，并对其进行遍历测试：

public class BinaryTreeTest {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        BinaryTreeTest test = new BinaryTreeTest();

        System.out.println("前序遍历：");
        test.preOrder(root);

        System.out.println("\n中序遍历：");
        test.inOrder(root);

        System.out.println("\n后序遍历：");
        test.postOrder(root);

        System.out.println("\n层次遍历：");
        test.levelOrder(root);
    }

    public void preOrder(TreeNode root) {
        if (root != null) {
            System.out.print(root.val + " ");
            preOrder(root.left);
            preOrder(root.right);
        }
    }

    public void inOrder(TreeNode root) {
        if (root != null) {
            inOrder(root.left);
            System.out.print(root.val + " ");
            inOrder(root.right);
        }
    }

    public void postOrder(TreeNode root) {
        if (root != null) {
            postOrder(root.left);
            postOrder(root.right);
            System.out.print(root.val + " ");
        }
    }

    public void levelOrder(TreeNode root) {
        if (root == null) {
            return;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            System.out.print(node.val + " ");

            if (node.left != null) {
                queue.add(node.left);
            }

            if (node.right != null) {
                queue.add(node.right);
            }
        }
    }
}

以上代码实现了二叉树的构建和四种遍历方式的测试。我们可以看到，通过递归的方式可以方便地实现二叉树的各种遍历方法。层次遍历则需要借助队列来实现，确保按照每一层的顺序进行访问。通过对二叉树的各种遍历方式的熟练掌握，可以更好地理解和应用二叉树这一重要的数据结构。