数据结构——二叉排序树

懒猫老师-数据结构-(58)二叉排序树的删除(二叉查找树)_哔哩哔哩_bilibili

概念

(1)若它的左子树不空，则左子树上所有结点的值均小于根结点的值;

(2)若它的右子树不空，则右子树上所有结点的值均大于根结点的值;

(3)它的左右子树也都是二叉排序树。

通过递归的方法来定义

中序遍历二叉排序树可以得到一个按关键码有序的序列。

操作

创建二叉树

// 定义二叉查找树的节点  
typedef struct Node {  
    int key;  
    struct Node* left;  
    struct Node* right;  
} Node;  
  

插入操作

Node* insert(Node* node, int key) {  
    if (node == NULL) return newNode(key);  
  
    if (key < node->key) {  
        node->left = insert(node->left, key);  
    } else if (key > node->key) {  
        node->right = insert(node->right, key);  
    } 
    return node;  
}  

也可用循环进行多次插入

查找操作

// 查找特定键值  
Node* search(Node* root, int key) {  
    if (root == NULL) {  
        return NULL;  
    }  
  
    if (key == root->key) {  
        return root;  
    }  
  
    if (key < root->key) {  
        return search(root->left, key);  
    }  
  
    return search(root->right, key);  
}  
  

删除操作（重要）

1、删除节点为叶子结点

直接删除

2、被删除的节点只有左子树或只有右子树

3、被删除的节点既有左子树又有右子树

以左子树中最大的节点或右子树中最小的节点替代被删除的节点