二叉搜索树的插入与删除
- 插入：
BSTree Insert(BSTree BST, ElementType X){BSTree Insert(BSTree BST, ElementType X){
if(!BST){//如果是一颗空的二叉树，就新建一个二叉搜索树并返回
BST = (BSTree)malloc(sizeof(struct TNode));
BST->Data = X;
BST->Left = BST->Right = NULL;
}else{
if(X < BST->Data)
BST->Left = Insert(BST->Left,X);//递归插入左子树
else if(X > BST->Data)
BST->Right = Insert(BST->Right,X);//递归插入右子树
//else x存在就不插入了 什么也不做
}
return BST;
} - 删除：
BSTree Delete(BSTree BST, Element X){
if(!BST)
print(“未找到要删除的元素”);
else{
if(X < BST->Data)
BST->Left = Delete(BST->Left,X);
else if(X>BST->Data)
BST->Right = Delete(BST->Right,X);
else{//此节点就是要删除的节点
if(BST->Left && BST->Right){
Tmp = FindMin( BST->Right );
BST->Data = tmp->Data;
BST->Right = Delete(tmp->Data,BST->Right);
}
else{
Tmp = BST;
if(!BST->Left)
BST = BST->Right;
else if(!BST->Right)
BST = BST->Left;
free(Tmp);
}
}
}
return BST;
}
总结：二叉树的插入比较好解决，只需要简单的递归判断即可。麻烦一点的是二叉树的删除。分三种情况：
1：左右子树都空，直接删除。
2：左右子树有一个为空，两个都不空，只要将该点的不空的子树替代该点即可。
3：左右子树都不空，这是删除里最麻烦的。又有两个方法：
（1）从左子树找最大值，替换该节点。并从左子树里删除最大的节点。
（2）从右子树找最小值，替换该节点。并从右子树里删除最小的节点。
查看5道真题和解析