Java 构建二叉搜索树并进行删除和中序遍历的程序

17 Mar 2025 | 5 分钟阅读

在此程序中，我们需要创建一个二叉搜索树，从树中删除一个节点，并通过中序遍历（左 -> 根 -> 右）来显示树的节点。在中序遍历中，对于给定节点，我们首先遍历左子节点，然后是根节点，最后是右子节点。

Java program to construct a Binary Search Tree and perform deletion and In-order traversal

在二叉搜索树中，所有位于根节点左侧的节点都将小于根节点，而位于右侧的节点将大于根节点。

插入

如果新节点的值小于根节点，则它将被插入到左子树中。
如果新节点的值大于根节点，则它将被插入到右子树中。

删除

如果待删除的节点是叶节点，则该节点的父节点将指向空。例如，如果我们删除90，则父节点70将指向空。
如果待删除的节点有一个子节点，则该子节点将成为父节点的子节点。例如，如果我们删除30，则作为30左子节点的节点10将成为50的左子节点。
如果待删除的节点有两个子节点，则我们从该当前节点的右子树中找到具有最小值的节点（minNode）。当前节点将被其后继节点（minNode）替换。

算法

定义Node类，它有三个属性：data、left和right。其中，left表示节点的左子节点，right表示节点的右子节点。
创建节点时，数据将传递给节点的数据属性，left和right都将设置为null。
定义另一个类，该类有一个 root 属性。
- Root 表示树的根节点，并将其初始化为 null。

a. insert() 将新值插入到二叉搜索树中

它检查根节点是否为null，这意味着树是空的。新节点将成为树的根节点。
如果树不为空，它将比较新节点的值与根节点。如果新节点的值大于根节点，则新节点将被插入到右子树中。否则，它将被插入到左子树中。

a. deleteNode() 将从树中删除特定节点

如果待删除节点的值小于根节点，则在左子树中搜索节点。否则，在右子树中搜索。
如果找到节点且它没有子节点，则将该节点设置为null。
如果节点有一个子节点，则子节点将取代节点的位置。
如果节点有两个子节点，则从其右子树中找到一个最小值节点。该最小值节点将替换当前节点。

程序

public class BinarySearchTree {

    //Represent a node of binary tree
    public static class Node{
        int data;
        Node left;
        Node right;

        public Node(int data){
            //Assign data to the new node, set left and right children to null
            this.data = data;
            this.left = null;
            this.right = null;
        }
      }

      //Represent the root of binary tree
      public Node root;

      public BinarySearchTree(){
          root = null;
      }

      //insert() will add new node to the binary search tree
      public void insert(int data) {
          //Create a new node
          Node newNode = new Node(data);

          //Check whether tree is empty
          if(root == null){
              root = newNode;
              return;
            }
          else {
              //current node point to root of the tree
              Node current = root, parent = null;

              while(true) {
                  //parent keep track of the parent node of current node.
                  parent = current;

                  //If data is less than current's data, node will be inserted to the left of tree
                  if(data < current.data) {
                      current = current.left;
                      if(current == null) {
                          parent.left = newNode;
                          return;
                      }
                  }
                  //If data is greater than current's data, node will be inserted to the right of tree
                  else {
                      current = current.right;
                      if(current == null) {
                          parent.right = newNode;
                          return;
                      }
                  }
              }
          }
      }

      //minNode() will find out the minimum node
      public Node minNode(Node root) {
          if (root.left != null)
              return minNode(root.left);
          else
              return root;
      }

      //deleteNode() will delete the given node from the binary search tree
      public Node deleteNode(Node node, int value) {
          if(node == null){
              return null;
           }
          else {
              //value is less than node's data then, search the value in left subtree
              if(value < node.data)
                  node.left = deleteNode(node.left, value);

              //value is greater than node's data then, search the value in right subtree
              else if(value > node.data)
                  node.right = deleteNode(node.right, value);

              //If value is equal to node's data that is, we have found the node to be deleted
              else {
                  //If node to be deleted has no child then, set the node to null
                  if(node.left == null && node.right == null)
                      node = null;

                  //If node to be deleted has only one right child
                  else if(node.left == null) {
                      node = node.right;
                  }

                  //If node to be deleted has only one left child
                  else if(node.right == null) {
                      node = node.left;
                  }

                  //If node to be deleted has two children node
                  else {
                      //then find the minimum node from right subtree
                      Node temp = minNode(node.right);
                      //Exchange the data between node and temp
                      node.data = temp.data;
                      //Delete the node duplicate node from right subtree
                      node.right = deleteNode(node.right, temp.data);
                  }
              }
              return node;
          }
      }

      //inorder() will perform inorder traversal on binary search tree
      public void inorderTraversal(Node node) {

          //Check whether tree is empty
          if(root == null){
              System.out.println("Tree is empty");
              return;
           }
          else {

              if(node.left!= null)
                  inorderTraversal(node.left);
              System.out.print(node.data + " ");
              if(node.right!= null)
                  inorderTraversal(node.right);

          }
      }

      public static void main(String[] args) {

          BinarySearchTree bt = new BinarySearchTree();
          //Add nodes to the binary tree
          bt.insert(50);
          bt.insert(30);
          bt.insert(70);
          bt.insert(60);
          bt.insert(10);
          bt.insert(90);

          System.out.println("Binary search tree after insertion:");
          //Displays the binary tree
          bt.inorderTraversal(bt.root);

          Node deletedNode = null;
          //Deletes node 90 which has no child
          deletedNode = bt.deleteNode(bt.root, 90);
          System.out.println("\nBinary search tree after deleting node 90:");
          bt.inorderTraversal(bt.root);

          //Deletes node 30 which has one child
          deletedNode = bt.deleteNode(bt.root, 30);
          System.out.println("\nBinary search tree after deleting node 30:");
          bt.inorderTraversal(bt.root);

          //Deletes node 50 which has two children
          deletedNode = bt.deleteNode(bt.root, 50);
          System.out.println("\nBinary search tree after deleting node 50:");
          bt.inorderTraversal(bt.root);
      }
}

输出

Binary search tree after insertion:
10 30 50 60 70 90 
Binary search tree after deleting node 90:
10 30 50 60 70 
Binary search tree after deleting node 30:
10 50 60 70 
Binary search tree after deleting node 50:
10 60 70

下一个主题Java 程序

Java 构建二叉搜索树并进行删除和中序遍历的程序

插入

删除

算法

程序

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java 程序

Java 构建二叉搜索树并进行删除和中序遍历的程序

插入

删除

算法

程序

相关帖子

如何在 Java 中将 int 转换为 char

Java 创建 N 个节点的循环链表并计算节点数的程序

查找字符串中重复单词的 Java 程序

Java 计算字符串中元音和辅音总数的程序

Java 从三叉树创建双向链表的程序

Java 中的范围和计数问题

将二叉树转换为二叉搜索树的 Java 程序

Java 中将二进制矩阵转换为零矩阵的最小翻转次数

Java 中在角为 1 的矩阵中查找矩形

查找字符串中重复字符的 Java 程序

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器