二叉搜索树是经典的数据结构,本文来总结一下二叉搜索树的插入和删除算法。
插入算法:
struct Node
{
int key;
struct Node *parent;
struct Node *left;
struct Node *right;
};
struct Node* tree_insert(struct Node *root,struct Node *newNode)
{
struct Node *y=NULL;
struct Node *x=root;
while(x!=NULL)
{
y=x;
if(newNode->key<x->key)
x=x->left;
else
x=x->right;
}
newNode->parent=y;
if(y==NULL)
root=newNode;
else
{
if(newNode->key<y->key)
y->left=newNode;
else
y->right=newNode;
}
return root;
}
主要思想:找到插入点的父节点y,然后进行插入。
删除算法:如果被删除节点z有俩个孩子,那么直接删除后继;否则直接删除z
struct Node* tree_delete(struct Node* &root,struct Node *z)
{
struct Node *x,*y;
if(z->left==NULL || z->right==NULL)
y=z;
else
y=tree_successor(z);
if(y->left!=NULL)
x=y->left;
else
x=y->right;
if(x!=NULL)
x->parent=y->parent;
if(y->parent==NULL)
root=x;
else if(y==y->parent->left)
y->parent->left=x;
else
y->parent->right=x;
if(y!=z)
z->key=y->key;
return y;
}