Java实现二叉树的基本操作详解

二叉树是一种非常常见的树形结构，由于它的具有良好的数据存储和查询性能，在实际开发中也经常使用到。本文将介绍如何使用Java语言实现二叉树的基本操作，包括构建二叉树、插入节点、删除节点、查找节点等功能。

二叉树节点的定义

首先，我们需要定义一个二叉树节点类，它包含三个属性，分别是节点值、左子节点和右子节点，定义如下：

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

构建二叉树

我们可以通过先序遍历的方式来构建二叉树。具体实现如下：

public TreeNode buildTree(int[] preorder, int[] inorder) {
    return buildTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
}

private TreeNode buildTree(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) {
    if (preStart > preEnd || inStart > inEnd) {
        return null;
    }

    int rootVal = preorder[preStart];
    int rootIndex = 0;
    for (int i = inStart; i <= inEnd; i++) {
        if (inorder[i] == rootVal) {
            rootIndex = i;
            break;
        }
    }

    int leftSize = rootIndex - inStart;
    TreeNode root = new TreeNode(rootVal);
    root.left = buildTree(preorder, preStart + 1, preStart + leftSize, inorder, inStart, rootIndex - 1);
    root.right = buildTree(preorder, preStart + leftSize + 1, preEnd, inorder, rootIndex + 1, inEnd);
    return root;
}

例如，我们有如下先序遍历和中序遍历序列：

先序遍历序列：[3,9,20,15,7]

中序遍历序列：[9,3,15,20,7]

我们可以通过下面的代码来构建二叉树：

int[] preorder = new int[] {3,9,20,15,7};
int[] inorder = new int[] {9,3,15,20,7};
TreeNode root = buildTree(preorder, inorder);

插入节点

如果我们需要在已有二叉树中插入一个节点，可以按照以下步骤进行：

• 从根节点开始搜索，直到找到一个叶子节点空位，将新节点插入到这个位置上。

具体实现如下：

public void insertIntoBST(TreeNode root, int val) {
    if (root == null) {
        return new TreeNode(val);
    }

    if (val < root.val) {
        root.left = insertIntoBST(root.left, val);
    } else {
        root.right = insertIntoBST(root.right, val);
    }

    return root;
}

例如，我们有如下二叉树：

      4
    /  \
   2    7
  / \
 1   3

我们可以按照以下方式插入一个节点值为 5 的节点：

TreeNode root = insertIntoBST(root, 5);

插入后，二叉树变为：

      4
    /  \
   2    7
  / \   
 1   3    
      \
       5

删除节点

如果我们需要删除已有二叉树中的一个节点，可以按照以下步骤进行：

• 如果要删除的节点是叶子节点，直接删除即可。
• 如果要删除的节点只有一个子节点，直接删除该节点，并将其子节点替换成其父节点的子节点。
• 如果要删除的节点有两个子节点，需要找到其右子树的最小节点，将其值替换到当前节点，然后递归的删除右子树的最小节点。

具体实现如下：

public TreeNode deleteNode(TreeNode root, int key) {
    if (root == null) {
        return null;
    }

    if (key < root.val) {
        root.left = deleteNode(root.left, key);
    } else if (key > root.val) {
        root.right = deleteNode(root.right, key);
    } else {
        if (root.left == null && root.right == null) {
            return null;
        } else if (root.left == null) {
            return root.right;
        } else if (root.right == null) {
            return root.left;
        } else {
            TreeNode minNode = findMin(root.right);
            root.val = minNode.val;
            root.right = deleteNode(root.right, minNode.val);
        }
    }

    return root;
}

private TreeNode findMin(TreeNode node) {
    while (node.left != null) {
        node = node.left;
    }
    return node;
}

例如，我们有如下二叉树：

      4
    /  \
   2    7
  / \
 1   3

我们可以按照以下方式删除节点值为 2 的节点：

TreeNode root = deleteNode(root, 2);

删除后，二叉树变为：

      4
    /  \
   1    7
    \   
     3

查找节点

如果我们需要在已有二叉树中查找一个节点，可以按照以下步骤进行：

• 从根节点开始查找。
• 如果节点值等于要查找的节点值，返回该节点。
• 如果要查找的节点值小于当前节点值，则递归的在左子树中查找。
• 如果要查找的节点值大于当前节点值，则递归的在右子树中查找。

具体实现如下：

public TreeNode searchBST(TreeNode root, int val) {
    if (root == null) {
        return null;
    }

    if (root.val == val) {
        return root;
    } else if (val < root.val) {
        return searchBST(root.left, val);
    } else {
        return searchBST(root.right, val);
    }
}

例如，我们有如下二叉树：

      4
    /  \
   2    7
  / \
 1   3

我们可以按照以下方式查找节点值为 3 的节点：

TreeNode node = searchBST(root, 3);

查找到的节点为：

3

/ \
1 3