懒猫老师-数据结构-(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、被删除的节点既有左子树又有右子树

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