实现二叉搜索树

JavaJavaBeginner
立即练习

💡 本教程由 AI 辅助翻译自英文原版。如需查看原文,您可以 切换至英文原版

简介

在本实验中,我们将学习如何在 Java 中实现一个二叉搜索树(Binary Search Tree)。二叉搜索树是一种二叉树数据结构,其中每个节点的值大于或等于其左子树中的所有值,且小于或等于其右子树中的所有值。


Skills Graph

%%%%{init: {'theme':'neutral'}}%%%% flowchart RL java(("`Java`")) -.-> java/BasicSyntaxGroup(["`Basic Syntax`"]) java(("`Java`")) -.-> java/DataStructuresGroup(["`Data Structures`"]) java(("`Java`")) -.-> java/ProgrammingTechniquesGroup(["`Programming Techniques`"]) java(("`Java`")) -.-> java/ObjectOrientedandAdvancedConceptsGroup(["`Object-Oriented and Advanced Concepts`"]) java/BasicSyntaxGroup -.-> java/variables("`Variables`") java/BasicSyntaxGroup -.-> java/if_else("`If...Else`") java/DataStructuresGroup -.-> java/collections_methods("`Collections Methods`") java/ProgrammingTechniquesGroup -.-> java/recursion("`Recursion`") java/ObjectOrientedandAdvancedConceptsGroup -.-> java/classes_objects("`Classes/Objects`") java/ObjectOrientedandAdvancedConceptsGroup -.-> java/constructors("`Constructors`") java/ObjectOrientedandAdvancedConceptsGroup -.-> java/oop("`OOP`") subgraph Lab Skills java/variables -.-> lab-117459{{"`实现二叉搜索树`"}} java/if_else -.-> lab-117459{{"`实现二叉搜索树`"}} java/collections_methods -.-> lab-117459{{"`实现二叉搜索树`"}} java/recursion -.-> lab-117459{{"`实现二叉搜索树`"}} java/classes_objects -.-> lab-117459{{"`实现二叉搜索树`"}} java/constructors -.-> lab-117459{{"`实现二叉搜索树`"}} java/oop -.-> lab-117459{{"`实现二叉搜索树`"}} end

创建 BSTNode

首先,让我们创建一个 Java 类来表示二叉搜索树的节点,并将其命名为 BSTNode。二叉搜索树中的一个节点应该包含一个值以及两个子节点——一个左子节点和一个右子节点。

class BSTNode {
    int value;
    BSTNode leftChild;
    BSTNode rightChild;

    BSTNode(int val) {
        this.value = val;
        this.leftChild = null;
        this.rightChild = null;
    }
}

向二叉搜索树中插入元素

要向二叉搜索树中插入元素,我们遵循以下算法:

  • 如果新值小于当前节点的值,则递归到左子节点
  • 如果新值大于当前节点的值,则递归到右子节点
  • 如果当前节点为空,则在此位置添加新值
public static BSTNode insert(int value, BSTNode current) {
    if (current == null) {
        BSTNode newNode = new BSTNode(value);
        return newNode;
    } else {
        if (value < current.value)
            current.leftChild = insert(value, current.leftChild);
        else
            current.rightChild = insert(value, current.rightChild);
    }
    return current;
}

为了测试这个方法,创建二叉搜索树并插入一些元素:

public static void main(String[] args) {
    BSTNode root = new BSTNode(12);
    root = insert(7, root);
    root = insert(20, root);
    root = insert(5, root);
    root = insert(9, root);
    root = insert(21, root);

    // 打印树以验证插入
    System.out.println("Traversal after insertion: ");
    inorderTraversal(root);
}

// 中序遍历树的函数
public static void inorderTraversal(BSTNode current) {
    if (current == null)
        return;
    inorderTraversal(current.leftChild);
    System.out.print(current.value + " ");
    inorderTraversal(current.rightChild);
}

输出:

Traversal after insertion:
5 7 9 12 20 21

在二叉搜索树中搜索元素

要在二叉搜索树中搜索元素,我们遵循以下算法:

  • 如果当前节点的值与我们试图查找的值匹配,则返回 true
  • 如果当前节点的值大于我们试图查找的值,则递归到左子节点
  • 如果当前节点的值小于我们试图查找的值,则递归到右子节点
  • 如果当前节点为空,则返回 false
public static boolean search(int key, BSTNode current) {
    if (current == null)
        return false;
    if (current.value == key)
        return true;
    else {
        if (key < current.value)
            return search(key, current.leftChild);
        else
            return search(key, current.rightChild);
    }
}

为了测试这个方法,搜索一些元素:

public static void main(String[] args) {
    BSTNode root = new BSTNode(12);
    root = insert(7, root);
    root = insert(20, root);
    root = insert(5, root);
    root = insert(9, root);
    root = insert(21, root);

    // 搜索元素
    System.out.println(search(7, root));
    System.out.println(search(9, root));
    System.out.println(search(17, root));
}

输出:

true
true
false

从二叉搜索树中删除元素

从二叉搜索树中删除元素比之前的步骤稍微复杂一些,因为我们需要根据节点的类型处理不同的情况:

  • 如果节点没有子节点(叶子节点),直接删除它。
  • 如果节点只有一个子节点,用其唯一的子节点替换它。
  • 如果节点有两个子节点,用右子树中的最小值或左子树中的最大值替换它。
public static BSTNode delete(int value, BSTNode current) {
    if (current == null)
        return current;
    if (value < current.value)
        current.leftChild = delete(value, current.leftChild);
    else if (value > current.value)
        current.rightChild = delete(value, current.rightChild);
    else if (value == current.value) {
        if (current.leftChild != null && current.rightChild != null) {
            int min = current.rightChild.value;
            BSTNode temp = current.rightChild;
            while (temp.leftChild != null) {
                min = temp.leftChild.value;
                temp = temp.leftChild;
            }
            current.value = min;
            current.rightChild = delete(min, current.rightChild);
        } else if (current.leftChild == null)
            return current.rightChild;
        else if (current.rightChild == null)
            return current.leftChild;
    }
    return current;
}

为了测试这个方法,删除一些节点并打印树:

public static void main(String[] args) {
    BSTNode root = new BSTNode(12);
    root = insert(7, root);
    root = insert(20, root);
    root = insert(5, root);
    root = insert(9, root);
    root = insert(21, root);

    // 删除一些节点
    root = delete(12, root);
    root = delete(20, root);
    root = delete(9, root);

    // 打印树以验证删除
    System.out.println("Traversal after deletion: ");
    inorderTraversal(root);
}

输出:

Traversal after deletion:
5 7 21

遍历二叉搜索树

我们可以通过不同的方式遍历二叉搜索树:

  • 中序遍历(左-根-右)
  • 前序遍历(根-左-右)
  • 后序遍历(左-右-根)
  • 层序遍历(广度优先搜索,BFS)
public static void inorderTraversal(BSTNode current) {
    if (current == null)
        return;
    inorderTraversal(current.leftChild);
    System.out.print(current.value + " ");
    inorderTraversal(current.rightChild);
}

public static void preorderTraversal(BSTNode current) {
    if (current == null)
        return;
    System.out.print(current.value + " ");
    preorderTraversal(current.leftChild);
    preorderTraversal(current.rightChild);
}

public static void postorderTraversal(BSTNode current) {
    if (current == null)
        return;
    postorderTraversal(current.leftChild);
    postorderTraversal(current.rightChild);
    System.out.print(current.value + " ");
}

public static void levelOrderTraversal(BSTNode root) {
    Queue<BSTNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        BSTNode temp = queue.poll();
        System.out.print(temp.value + " ");
        if (temp.leftChild != null)
            queue.add(temp.leftChild);
        if (temp.rightChild != null)
            queue.add(temp.rightChild);
    }
}

为了测试这些方法,使用每种遍历技术打印树:

public static void main(String[] args) {
    BSTNode root = new BSTNode(12);
    root = insert(7, root);
    root = insert(20, root);
    root = insert(5, root);
    root = insert(9, root);
    root = insert(21, root);

    System.out.print("Inorder Traversal: ");
    inorderTraversal(root);
    System.out.print("\nPreorder Traversal: ");
    preorderTraversal(root);
    System.out.print("\nPostorder Traversal: ");
    postorderTraversal(root);
    System.out.print("\nLevel-order Traversal: ");
    levelOrderTraversal(root);
}

输出:

Inorder Traversal: 5 7 9 12 20 21
Preorder Traversal: 12 7 5 9 20 21
Postorder Traversal: 5 9 7 21 20 12
Level-order Traversal: 12 7 20 5 9 21

总结

在本实验中,我们学习了如何在 Java 中创建二叉搜索树、插入元素、搜索元素、删除元素以及遍历二叉搜索树。

我们首先创建了 BSTNode 类,它表示二叉搜索树中的一个节点。然后,我们使用二叉搜索树特有的算法实现了插入、搜索和删除功能。最后,我们学习了如何使用不同的遍历技术(如中序、前序、后序和层序遍历)来遍历二叉搜索树。

通过这些概念,你应该能够在自己的 Java 程序中实现二叉搜索树。

您可能感兴趣的其他 Java 教程