二叉搜索树(binary search tree)

数据结构与算法第四章树(tree) 二叉搜索树(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

代码实现：

/**************************************************************** 
 * Description:  二叉搜索树 C++ implementation of Binary Search Tree(BST)
 * Author: Alex Li
 * Date: 2023-06-10 21:10:46
 * LastEditTime: 2024-08-08 10:44:11
****************************************************************/

#include <iostream>
using namespace std;

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

// 创建一个新节点
struct node* newNode(int item){
    struct node *temp = new node;
    temp->data = item;
    temp->left = NULL;
    temp->right = NULL;
    return temp;
}

// 中序遍历
void inorder(node *root){
    if(root != NULL){
        // 遍历左子树
        inorder(root->left);
        // 遍历根节点
        cout << root->data << "->";
        // 遍历右子树
        inorder(root->right);
    }
}

// 插入节点
struct node* insertNode(node *node, int data){
    // 如果树为空，返回新节点
    if(node == NULL) return newNode(data);
        
    // 遍历左子树并插入节点
    if(data < node->data) node->left = insertNode(node->left, data);
    else node->right = insertNode(node->right, data);
    return node;
}

// 找到最小值节点
struct node *minValueNode(struct node *node) {
    struct node *current = node;

    // 找到最左边的叶子节点
    while (current && current->left != NULL)
        current = current->left;

    return current;
}

// 删除节点
struct node *deleteNode(struct node *node, int data) {
    // 如果树为空，返回节点
    if (node == NULL) return node;

    // 找到要删除的节点
    if (data < node->data)
        node->left = deleteNode(node->left, data);
    else if (data > node->data)
        node->right = deleteNode(node->right, data);
    else {
        // 如果节点只有一个子节点或没有子节点
        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;
        }
        // 如果节点有两个子节点
        // 找到右子树的最小值节点作为中序后继节点
        struct node *temp = minValueNode(node->right);

        // 用中序后继节点替换要删除的节点
        node->data = temp->data;

        // 删除中序后继节点
        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);
}