问. 构建二叉搜索树并执行删除和中序遍历程序。

2025年3月17日 | 阅读 14 分钟

说明

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

Program to construct a Binary Search Tree and perform deletion and inorder traversal

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

插入

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

删除

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

算法

定义一个 Node 类，它有三个属性：data、left 和 right。其中，left 表示节点的左子节点，right 表示节点的右子节点。
创建节点时，数据将传递到节点的 data 属性，left 和 right 都将设置为 null。
定义另一个类，该类有一个 root 属性。
1. Root 表示树的根节点，并将其初始化为 null。
insert() 函数将新值插入二叉搜索树。
1. 它会检查根节点是否为 null，这意味着树是空的。新节点将成为树的根节点。
2. 如果树不为空，则将新节点的值与根节点进行比较。如果新节点的值大于根节点，则将新节点插入到右子树中。否则，将其插入到左子树中。
deleteNode() 函数将从树中删除特定节点。
1. 如果要删除的节点值小于根节点，则在左子树中搜索节点。否则，在右子树中搜索节点。
2. 如果找到节点并且它没有子节点，则将该节点设置为 null。
3. 如果节点只有一个子节点，则该子节点将取代该节点的位置。
4. 如果节点有两个子节点，则找到其右子树中的最小值的节点。这个最小值的节点将替换当前节点。

解决方案

Python

#Represent a node of binary tree
class Node:
    def __init__(self,data):
        #Assign data to the new node, set left and right children to None
        self.data = data;
        self.left = None;
        self.right = None;
 
class BinarySearchTree:
    def __init__(self):
        #Represent the root of binary tree
        self.root = None;
        
    #insert() will add new node to the binary search tree
    def insert(self, data):
        #Create a new node
        newNode = Node(data);
        
        #Check whether tree is empty
        if(self.root == None):
            self.root = newNode;
            return;
        else:
            #current node point to root of the tree
            current = self.root;
            
            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 == None):
                        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 == None):
                        parent.right = newNode;
                        return;
                        
    #minNode() will find out the minimum node
    def minNode(self, root):
        if(root.left != None):
            return self.minNode(root.left);
        else:
            return root;
            
    #deleteNode() will delete the given node from the binary search tree
    def deleteNode(self, node, value):
        if(node == None):
            return None;
        else:
            #value is less than node's data then, search the value in left subtree
            if(value < node.data):
                node.left = self.deleteNode(node.left, value);
            
            #value is greater than node's data then, search the value in right subtree
            elif(value > node.data):
                node.right = self.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 None
                if(node.left == None and node.right == None):
                    node = None;
                    
                #If node to be deleted has only one right child
                elif(node.left == None):
                    node = node.right;
                
                #If node to be deleted has only one left child
                elif(node.right == None):
                    node = node.left;
                    
                #If node to be deleted has two children node
                else:
                    #then find the minimum node from right subtree
                    temp = self.minNode(node.right);
                    #Exchange the data between node and temp
                    node.data = temp.data;
                    #Delete the node duplicate node from right subtree
                    node.right = self.deleteNode(node.right, temp.data);
        return node;
                
    #inorder() will perform inorder traversal on binary search tree
    def inorderTraversal(self, node):
        #Check whether tree is empty
        if(self.root == None):
            print("Tree is empty");
            return;
        else:
            if(node.left != None):
                self.inorderTraversal(node.left);
            print(node.data, end=" ");
            if(node.right != None):
                self.inorderTraversal(node.right);
                
bt = 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);
 
print("Binary search tree after insertion:");
#Displays the binary tree
bt.inorderTraversal(bt.root);
 
#Deletes node 90 which has no child
deletedNode = bt.deleteNode(bt.root, 90);
print("\nBinary search tree after deleting node 90:");
bt.inorderTraversal(bt.root);
 
#Deletes node 30 which has one child
deletedNode = bt.deleteNode(bt.root, 30);
print("\nBinary search tree after deleting node 30:");
bt.inorderTraversal(bt.root);
 
#Deletes node 50 which has two children
deletedNode = bt.deleteNode(bt.root, 50);
print("\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

C

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
 
//Represent a node of binary tree
struct node{
    int data;
    struct node *left;
    struct node *right;
};
 
//Represent the root of binary tree
struct node *root= NULL;
 
//createNode() will create a new node
struct node* createNode(int data){
    //Create a new node
    struct node *newNode = (struct node*)malloc(sizeof(struct node));
    //Assign data to newNode, set left and right children to NULL
    newNode->data= data;
    newNode->left = NULL;
    newNode->right = NULL;
    
    return newNode;
}
 
//insert() will add new node to the binary search tree
void insert(int data) {
    //Create a new node
    struct node *newNode = createNode(data);
    
    //Check whether tree is empty
    if(root == NULL){
        root = newNode;
        return;
      }
    else {
        //current node point to root of the tree
        struct 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
struct node* minNode(struct node *root) {
    if (root->left != NULL)
        return minNode(root->left);
    else 
        return root;
} 
 
//deleteNode() will delete the given node from the binary search tree
struct node* deleteNode(struct 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
                struct 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
void inorderTraversal(struct node *node) {
      
    //Check whether tree is empty
    if(root == NULL){
        printf("Tree is empty\n");
          return;
     }
    else {
          
        if(node->left!= NULL)
            inorderTraversal(node->left);
        printf("%d ", node->data);
        if(node->right!= NULL)
          inorderTraversal(node->right);
          
    }      
}
      
int main()
{
    //Add nodes to the binary tree
    insert(50);
    insert(30);
    insert(70);
    insert(60);
    insert(10);
    insert(90);
    
    printf("Binary search tree after insertion: \n");
    //Displays the binary tree
    inorderTraversal(root);
    
    struct node *deletedNode = NULL;
    //Deletes node 90 which has no child
    deletedNode = deleteNode(root, 90);
    printf("\nBinary search tree after deleting node 90: \n");
    inorderTraversal(root);
    
    //Deletes node 30 which has one child
    deletedNode = deleteNode(root, 30);
    printf("\nBinary search tree after deleting node 30: \n");
    inorderTraversal(root);
    
    //Deletes node 50 which has two children
    deletedNode = deleteNode(root, 50);
    printf("\nBinary search tree after deleting node 50: \n");
    inorderTraversal(root);
 
    return 0;
}

输出

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

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

C#

 using System;
namespace Tree 
{                     
    public class Program
    {
        //Represent a node of binary tree
        public class Node<T>{
            public T data;
            public Node<T> left;
            public Node<T> right;
            
            public Node(T data) {
                //Assign data to the new node, set left and right children to null
                this.data = data;
                this.left = null;
                this.right = null;
            }
        }
        
        public class BinarySearchTree<T> where T : IComparable<T>{
            //Represent the root of binary tree
            public Node<T> root;
            
            public BinarySearchTree(){
                root = null;
            }
            
        //insert() will add new node to the binary search tree
        public void insert(T data) {
          //Create a new node
          Node<T> newNode = new Node<T>(data);
          
          //Check whether tree is empty
          if(root == null){
              root = newNode;
              return;
            }
          else {
              //current node point to root of the tree
              Node<T> 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.CompareTo(current.data) < 0) {
                      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<T> minNode(Node<T> 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<T> deleteNode(Node<T> node, T value) {
          if(node == null){
              return null;
           }
          else {
              //value is less than node's data then, search the value in left subtree
              if(value.CompareTo(node.data) < 0)
                  node.left = deleteNode(node.left, value);
              
              //value is greater than node's data then, search the value in right subtree
              else if(value.CompareTo(node.data) > 0)
                  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<T> 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<T> node) {
          
          //Check whether tree is empty
          if(root == null){
              Console.WriteLine("Tree is empty");
              return;
           }
          else {
              
              if(node.left!= null)
                  inorderTraversal(node.left);
              Console.Write(node.data + " ");
              if(node.right!= null)
                  inorderTraversal(node.right);
              
          }      
        }
    }
        
        public static void Main()
        {
            BinarySearchTree<int> bt = new BinarySearchTree<int>();
            //Add nodes to the binary tree
            bt.insert(50);
            bt.insert(30);
            bt.insert(70);
            bt.insert(60);
            bt.insert(10);
            bt.insert(90);
            
            Console.WriteLine("Binary search tree after insertion:");
            //Displays the binary tree
            bt.inorderTraversal(bt.root);
            
            Node<int> deletedNode = null;
            //Deletes node 90 which has no child
            deletedNode = bt.deleteNode(bt.root, 90);
            Console.WriteLine("\nBinary search tree after deleting node 90:");
            bt.inorderTraversal(bt.root);
            
            //Deletes node 30 which has one child
            deletedNode = bt.deleteNode(bt.root, 30);
            Console.WriteLine("\nBinary search tree after deleting node 30:");
            bt.inorderTraversal(bt.root);
            
            //Deletes node 50 which has two children
            deletedNode = bt.deleteNode(bt.root, 50);
            Console.WriteLine("\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

PHP

<!DOCTYPE html>
<html>
<body>
<?php
//Represent a node of binary tree
class Node{
    public $data;
    public $left;
    public $right;
    
    function __construct($data){
        //Assign data to the new node, set left and right children to NULL
        $this->data = $data;
        $this->left = NULL;
        $this->right = NULL;
    }
}
class BinarySearchTree{
    //Represent the root of binary tree
    public $root;
    function __construct(){
        $this->root = NULL;
    }
    
    //insert() will add new node to the binary search tree
    function insert($data) {
        //Create a new node
        $newNode = new Node($data);
          
        //Check whether tree is empty
        if($this->root == NULL){
            $this->root = $newNode;
            return;
        }
        else {
            //current node point to root of the tree
            $current = $this->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
    function minNode($root) {
        if ($root->left != NULL)
            return $this->minNode($root->left);
        else 
            return $root;
    } 
    
    //deleteNode() will delete the given node from the binary search tree
    function deleteNode($node, $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 = $this->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 = $this->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
                    $temp = $this->minNode($node->right);
                    //Exchange the data between node and temp
                    $node->data = $temp->data;
                    //Delete the node duplicate node from right subtree
                    $node->right = $this->deleteNode($node->right, $temp->data);
                }
            }
            return $node;
        }
    }
      
    //inorder() will perform inorder traversal on binary search tree
    function inorderTraversal($node) {
        
        //Check whether tree is empty
        if($this->root == NULL){
            print("Tree is empty <br>");
            return;
        }
        else {
          
            if($node->left != NULL)
              $this->inorderTraversal($node->left);
            print("$node->data  ");
            if($node->right != NULL)
              $this->inorderTraversal($node->right);
          
        }      
    }
}
$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);
 
print("Binary search tree after insertion: <br>");
//Displays the binary tree
$bt->inorderTraversal($bt->root);
 
//Deletes node 90 which has no child
$deletedNode = $bt->deleteNode($bt->root, 90);
print("<br>Binary search tree after deleting node 90: <br>");
$bt->inorderTraversal($bt->root);
 
//Deletes node 30 which has one child
$deletedNode = $bt->deleteNode($bt->root, 30);
print("<br>Binary search tree after deleting node 30: <br>");
$bt->inorderTraversal($bt->root);
 
//Deletes node 50 which has two children
$deletedNode = $bt->deleteNode($bt->root, 50);
print("<br>Binary search tree after deleting node 50: <br>");
$bt->inorderTraversal($bt->root);
?>
</body>
</html>

输出

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

下一个主题程序列表

问. 构建二叉搜索树并执行删除和中序遍历程序。

说明

插入

删除

算法

解决方案

Python

C

JAVA

C#

PHP

联系信息

关注我们

教程

面试题

在线编译器

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

程序

问. 构建二叉搜索树并执行删除和中序遍历程序。

说明

插入

删除

算法

解决方案

Python

C

JAVA

C#

PHP

相关帖子

从单链表开头删除新节点的程序

检查迪沙里数（Disarium number）的程序

将一个数组的所有元素复制到另一个数组的程序

确定所有叶子是否在同一级别的程序

计算球体表面积的程序

计算两个矩阵之差的程序

编写查找六棱柱（Hexagonal Prism）体积的程序

创建和显示单向链表的程序

计算矩阵每行每列之和的程序

将给定二叉树转换为双向链表的程序

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器