Java数据结构之二叉搜索树详解

我为您详细讲解“Java数据结构之二叉搜索树详解”的完整攻略。

什么是二叉搜索树？

二叉搜索树（Binary Search Tree，简称BST）是一种特殊的二叉树，它的每个节点最多有两颗子树，左子树元素均小于当前节点元素，右子树元素均大于当前节点元素，左右子树都是二叉搜索树。

二叉搜索树的优点在于能够提供进行二分查找的能力，对于动态集合的数据操作，二叉搜索树是一种效率很高、时间复杂度很低的数据结构。

二叉搜索树的基本操作

二叉搜索树有四个基本操作：插入元素、删除元素、查找元素、遍历元素。下面我们一一介绍。

插入元素

1. 如果当前树为空，则将新节点插入。

2. 如果新节点的值小于当前节点的值，则从左子树继续进行插入操作。

3. 如果新节点的值大于当前节点的值，则从右子树继续进行插入操作。

示例代码：

public void insert(int value) {
    if (root == null) {
        root = new TreeNode(value);
        return;
    }

    insert(root, value);
}

private void insert(TreeNode node, int value) {
    if (node.value > value) {
        if (node.left == null) {
            node.left = new TreeNode(value);
        } else {
            insert(node.left, value);
        }
    } else {
        if (node.right == null) {
            node.right = new TreeNode(value);
        } else {
            insert(node.right, value);
        }
    }
}

删除元素

1. 如果要删除的元素不存在，则退出删除。

2. 如果要删除的元素小于当前节点的值，则从左子树继续进行删除操作。

3. 如果要删除的元素大于当前节点的值，则从右子树继续进行删除操作。

4. 如果要删除的元素等于当前节点的值，则判断当前节点的类型，分情况讨论：

   1. 如果当前节点只有一个子节点，则将子节点替换当前节点的位置。

   2. 如果当前节点有两个子节点，则从右子树中找到最小的节点，并将其值替换当前节点的值，再从右子树中删除这个最小节点。

示例代码：

public void remove(int value) {
    remove(null, root, value);
}

private void remove(TreeNode parent, TreeNode node, int value) {
    if (node == null) {
        return;
    }

    if (value < node.value) {
        remove(node, node.left, value);
    } else if (value > node.value) {
        remove(node, node.right, value);
    } else if (node.left != null && node.right != null) {
        node.value = getMinValue(node.right);
        remove(node, node.right, node.value);
    } else if (parent == null) {
        if (node.left != null) {
            root = node.left;
        } else if (node.right != null) {
            root = node.right;
        } else {
            root = null;
        }
    } else if (parent.left == node) {
        parent.left = node.left != null ? node.left : node.right;
    } else if (parent.right == node) {
        parent.right = node.left != null ? node.left : node.right;
    }
}

private int getMinValue(TreeNode node) {
    while (node.left != null) {
        node = node.left;
    }
    return node.value;
}

查找元素

1. 如果当前树为空，则退出查找。

2. 如果要查找的元素等于当前节点的值，则返回当前节点。

3. 如果要查找的元素小于当前节点的值，则从左子树继续进行查找操作。

4. 如果要查找的元素大于当前节点的值，则从右子树继续进行查找操作。

示例代码：

public TreeNode search(int value) {
    return search(root, value);
}

private TreeNode search(TreeNode node, int value) {
    if (node == null || node.value == value) {
        return node;
    }

    if (node.value > value) {
        return search(node.left, value);
    } else {
        return search(node.right, value);
    }
}

遍历元素

二叉搜索树有三种遍历方式：中序遍历、前序遍历和后序遍历。

中序遍历的实现方式是递归遍历当前节点的左子树，输出当前节点的值，再递归遍历当前节点的右子树。

前序遍历的实现方式是输出当前节点的值，递归遍历当前节点的左子树，递归遍历当前节点的右子树。

后序遍历的实现方式是递归遍历当前节点的左子树，递归遍历当前节点的右子树，输出当前节点的值。

示例代码：

public void inorderTraversal(TreeNode node) {
    if (node == null) {
        return;
    }

    inorderTraversal(node.left);
    System.out.print(node.value + " ");
    inorderTraversal(node.right);
}

public void preorderTraversal(TreeNode node) {
    if (node == null) {
        return;
    }

    System.out.print(node.value + " ");
    preorderTraversal(node.left);
    preorderTraversal(node.right);
}

public void postorderTraversal(TreeNode node) {
    if (node == null) {
        return;
    }

    postorderTraversal(node.left);
    postorderTraversal(node.right);
    System.out.print(node.value + " ");
}

示例说明

下面给出两个二叉搜索树的操作示例：

示例一

先创建一棵空的二叉搜索树：

BinarySearchTree bst = new BinarySearchTree();

插入元素1：

bst.insert(1);

插入元素3：

bst.insert(3);

插入元素2：

bst.insert(2);

遍历输出：

bst.inorderTraversal(bst.root); // 输出1 2 3

删除元素1：

bst.remove(1);

遍历输出：

bst.inorderTraversal(bst.root); // 输出2 3

示例二

创建包含多个元素的二叉搜索树：

BinarySearchTree bst = new BinarySearchTree();
bst.insert(5);
bst.insert(3);
bst.insert(7);
bst.insert(1);
bst.insert(9);

查找元素7：

bst.search(7); // 返回节点值为7的节点

删除元素5：

bst.remove(5);

遍历输出：

bst.inorderTraversal(bst.root); // 输出1 3 7 9