Java实现二叉树的示例代码(递归&迭代)

下面是针对“Java实现二叉树的示例代码(递归&迭代)”的完整攻略：

什么是二叉树？

二叉树（binary tree）是一种非常常用的数据结构，在计算机科学的领域中被广泛使用。它采用了树形结构，每个结点最多有两个子节点：一个左子节点和一个右子节点。以根节点为起点，不断递归地对子节点进行处理，可以有效地管理数据和信息。

递归实现二叉树

递归是一种非常常用的编程思想，在二叉树的设计中，也有其独特的应用。下面我们就来看看一个经典的例子，如何使用递归实现二叉树的设计：

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class BinaryTree {
    public TreeNode construct(int[] preorder, int[] inorder) {
        if (preorder == null || preorder.length == 0) {
            return null;
        }
        return helper(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
    }

    private TreeNode helper(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) {
        if (preStart > preEnd || inStart > inEnd) {
            return null;
        }
        int rootVal = preorder[preStart];
        TreeNode root = new TreeNode(rootVal);
        int inorderIndex = 0;
        for (int i = inStart; i <= inEnd; i++) {
            if (inorder[i] == rootVal) {
                inorderIndex = i;
                break;
            }
        }
        int leftSubtreeSize = inorderIndex - inStart;
        root.left = helper(preorder, preStart + 1, preStart + leftSubtreeSize, inorder, inStart, inorderIndex - 1);
        root.right = helper(preorder, preStart + leftSubtreeSize + 1, preEnd, inorder, inorderIndex + 1, inEnd);
        return root;
    }
}

我们可以看到，在递归实现函数中，首先判断前序遍历序列中是否有值。如果没有值，则直接返回null。接着，需要对当前的根节点进行初始化。

然后，根据前序遍历序列的特点，可以找到该根节点对应的中序遍历序列中的位置。这样我们就可以确定所有的左子树节点和右子树节点，从而进行递归地处理整个二叉树。

迭代实现二叉树

迭代是另一种常用的编程思想，在二叉树的设计中，它同样有非常的应用。下面我们来看看一个经典的例子，如何使用迭代实现二叉树的设计：

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class BinaryTree {
    public TreeNode construct(int[] preorder, int[] inorder) {
        if (preorder == null || preorder.length == 0) {
            return null;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode root = new TreeNode(preorder[0]);
        stack.push(root);
        for (int i = 1, j = 0; i < preorder.length; i++) {
            TreeNode node = new TreeNode(preorder[i]);
            TreeNode cur = stack.peek();
            if (cur.val != inorder[j]) {
                cur.left = node;
            } else {
                while (!stack.isEmpty() && stack.peek().val == inorder[j]) {
                    cur = stack.pop();
                    j++;
                }
                cur.right = node;
            }
            stack.push(node);
        }
        return root;
    }
}

我们可以看到，在迭代实现函数中，首先判断前序遍历序列中是否有值。如果没有值，则直接返回null。接着使用stack作为辅助容器，来存储整个二叉树的结点。首先，我们需要初始化根节点，然后对所有的结点进行循环，依次判断当前节点是否是左子节点或者右子节点。

如果是左子节点，则需要将此节点与前面的节点挂接上，同时将此节点入栈。如果是右子节点，则需要对所有的前面的节点进行出栈，直到找到一个节点，左子树被处理完毕，右子树尚未处理。此时，将此节点与当前节点挂接上，并将散入的所有右子节点入栈。

通过这样的方式，我们就可以使用迭代实现二叉树的相关功能了。

示例说明

1. 递归示例

假设有如下二叉树：

           1
        /    \
       2      4
     /   \   /  \
    3    5  7   9

则先序遍历序列为：1 2 3 5 4 7 9

中序遍历序列为：3 2 5 1 7 4 9

使用递归方式，可以将此二叉树表示为以下结构：

         1
       /   \
      2     4
     / \   / \
    3   5 7   9

1. 迭代示例

假设有如下二叉树：

           1
        /    \
       2      4
     /   \   /  \
    3    5  7   9

则先序遍历序列为：1 2 3 5 4 7 9

中序遍历序列为：3 2 5 1 7 4 9

使用迭代方式，可以将此二叉树表示为以下结构：

         1
       /   \
      2     4
     / \   / \
    3   5 7   9

通过以上两个示例，我们可以看到，在递归和迭代的方式下，无论是数据量还是性能，都没有明显的差异。使用递归和迭代方式，开发者可以根据项目的需求来决定使用何种编程思想。