二叉搜索树(binary search tree)

组别:入门组
难度:4

一棵二叉搜索树应该满足以下条件:
1.非空左子树的所有键值都小于其根节点的键值
2.非空右子树的所有键值都大于其根节点的键值
3.左右子树都是二叉搜索树

How to Implement Binary Search Trees and Tree Traversal in JavaScript | by  Matthew Aquino | JavaScript in Plain English

代码实现:

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
/**************************************************************** 
 * Description:  C++ implementation of Binary Search Tree(BST)
 * Author: Alex Li
 * Date: 2023-06-10 21:10:46
 * LastEditTime: 2023-06-16 20:57:46
****************************************************************/

#include <iostream>
using namespace std;

struct node{
    int data;
    struct node *left,*right;
};

//create a new node 
struct node* newNode(int item){
    struct node *temp=new node;
    temp->data=item;
    temp->left=NULL;
    temp->right=NULL;
    return temp;
}

//inorder traversal 
void inorder(node *root){
    if(root!=NULL){
        //travese left 
        inorder(root->left);
        //travese root 
        cout<<root->data<<"->";
        //tralverse right 
        inorder(root->right);
    }
}

// insert a node
struct node* insertNode(node *node, int data){
    //return new node if the tree is empty
    if(node==NULL) return newNode(data);
        
    //travese to the left and insert node
    if(data<node->data) node->left=insertNode(node->left,data);
    else  node->right=insertNode(node->right,data);
    return node;
    }

    
// Find the min value node 
struct node *minValueNode(struct node *node) {
  struct node *current = node;

  // Find the leftmost leaf
  while (current && current->left != NULL)
    current = current->left;

  return current;
}

// Deleting a node
struct node *deleteNode(struct node *node, int data) {
  // Return if the tree is empty
  if (node == NULL) return node;

  // Find the node to be deleted
  if (data < node->data)
    node->left = deleteNode(node->left, data);
  else if (data > node->data)
    node->right = deleteNode(node->right, data);
  else {
    // If the node is with only one child or no child
    if (node->left == NULL) {
      struct node *temp = node->right;
      delete node;
      return temp;
    } else if (node->right == NULL) {
      struct node *temp = node->left;
      delete node;
      return temp;
    }
 // If the node has two children
 //// Find the min value node of right leaf as inorder successor
    struct node *temp = minValueNode(node->right);

    // Place the inorder successor in position of the node to be deleted
    node->data = temp->data;

    // Delete the inorder successor
    node->right = deleteNode(node->right, temp->data);
  }
  return node;
}

    int main(){
        struct node *root=NULL;
        root = insertNode(root, 8);
        root = insertNode(root, 3);
        root = insertNode(root, 1);
        root = insertNode(root, 6);
        root = insertNode(root, 7);
        root = insertNode(root, 10);
        root = insertNode(root, 14);
        root = insertNode(root, 4);
        
        cout << "Inorder traversal: ";
        inorder(root);
       
        root=deleteNode(root,10);
         cout << "\nAfter deleting 10\n";
        inorder(root);
       
    }
Scroll to Top