二叉排序树详解
二叉排序树(Binary Sort Tree或Binary Search Tree) 的定义为：二叉排序树或者是空树，或者是满足下列性质的二叉树。
(1) ：若左子树不为空，则左子树上所有结点的值(关键字)都小于根结点的值；
(2) ：若右子树不为空，则右子树上所有结点的值(关键字)都大于根结点的值；
(3) ：左、右子树都分别是二叉排序树。
结论：若按中序遍历一棵二叉排序树，所得到的结点序列是一个递增序列。
BST仍然可以用二叉链表来存储
节点结构定义如下：
[cpp] <SPAN style="FONT-SIZE: 18px">struct BiTNode
{
int data;
struct BiTNode *lchild,*rchild;
};
typedef struct BiTNode BiTNode,*biTree;</SPAN>
struct BiTNode
{
int data;
struct BiTNode *lchild,*rchild;
};
typedef struct BiTNode BiTNode,*biTree;
一、二叉排序树的查找
1 查找思想
首先将给定的K值与二叉排序树的根结点的关键字进行比较：若相等：则查找成功；
①给定的K值小于BST的根结点的关键字：继续在该结点的左子树上进行查找；
② 给定的K值大于BST的根结点的关键字：继续在该结点的右子树上进行查找。
2 代码实现
[cpp] <SPAN style="FONT-SIZE: 18px">biTree SearchBST(biTree T,int key)
{
//在根指针T所指的二叉排序树中递归地查找某关键字等于key的数据元素
//若查找成功，则返回指向数据元素节点的指针，否则，返回空指针
if (T==NULL)
{
return NULL;
}
else
{
if (key==T->data)
{
return T;
}
else if (key<T->data)
{
return (SearchBST(T->lchild,key));
}
else
{
return(SearchBST(T->rchild,key));
}
}
}
</SPAN>
biTree SearchBST(biTree T,int key)
{
//在根指针T所指的二叉排序树中递归地查找某关键字等于key的数据元素
//若查找成功，则返回指向数据元素节点的指针，否则，返回空指针
if (T==NULL)
{
return NULL;
}
else
{
if (key==T->data)
{
return T;
}
else if (key<T->data)
{
return (SearchBST(T->lchild,key));
}
else
{
return(SearchBST(T->rchild,key));
}
}
}
二、插入
1，插入思想
在BST树中插入一个新结点x时，若BST树为空，则令新结点x为插入后BST树的根结点；否则，将结点x的关键字与根结点T的关键字进行比较：
①若相等：不需要插入；
② 若x.key<T->key：结点x插入到T的左子树中；
③ 若x.key>T->key：结点x插入到T的右子树中
2，代码实现
[cpp] <SPAN style="FONT-SIZE: 18px">void InsertBST (biTree &T , int key)
{
if (T==NULL)
{
biTree x;
x=new BiTNode;
x->data=key;
x->lchild=x->rchild=NULL;
T=x;
cout<<"插入成功\n";
}
else
{
if (T->data==key)
{
cout<<"节点已存在\n"<<endl;
}
else if (key<T->data)
{
InsertBST(T->lchild,key);
}
else
{
InsertBST(T->rchild,key);
}
}
}</SPAN>
void InsertBST (biTree &T , int key)
{
if (T==NULL)
{
biTree x;
x=new BiTNode;
x->data=key;
x->lchild=x->rchild=NULL;
T=x;
cout<<"插入成功\n";
}
else
{
if (T->data==key)
{
cout<<"节点已存在\n"<<endl;
}
else if (key<T->data)
{
InsertBST(T->lchild,key);
}
else
{
InsertBST(T->rchild,key);
}
}
}
三、删除
1，删除思想
从BST树上删除一个结点，仍然要保证删除后满足BST的性质。设被删除结点为p，其父结点为f ，删除情况如下：
① 若p是叶子结点：直接删除p，如图9-5(b)所示。
② 若p只有一棵子树(左子树或右子树)：直接用p的左子树(或右子树)取代p的位置而成为f的一棵子树。即原来p是f的左子树，则p的子树成为f的左子树；原来p是f的右子树，则p的子树成为f的右子树
③ 若p既有左子树又有右子树：处理方法有以下两种，可以任选其中一种。
◆ 用p的直接前驱结点代替p。即从p的左子树中选择值最大的结点s放在p的位置(用结点s的内容替换结点p内容)，然后删除结点s。s是p的左子树中的最右边的结点且没有右子树，对s的删除同②，如图9-5(e)所示。
◆用p的直接后继结点代替p。即从p的右子树中选择值最小的结点s放在p的位置(用结点s的内容替换结点p内容)，然后删除结点s。s是p的右子树中的最左边的结点且没有左子树，对s的删除同②
补充：软件开发 , C++ ,
