5二叉排序树的建立和查找
#include
using namespace std;
typedef int KeyType;
typedef struct tree//声明树的结构
{
struct tree *left; //存放左子树的指针
struct tree *right; //存放又子树的指针
KeyType key; //存放节点的内容
} BSTNode, * BSTree; //声明二叉树的链表
BSTree insertBST(BSTree tptr,KeyType key)// 在二叉排序树中插入结点
{ //若二叉排序树tptr中没有关键字为key的结点，则插入，否则直接返回
BSTree f,p=tptr; //p的初值指向根结点
} while(p) //查找插入位置，循环结束时，p是空指针，f指向待插入结点的双亲 { if(p->key==key) //树中已有key，无须插入 return tptr; f=p; //f保存当前查找的结点，即f是p的双亲 p=(key
key)?p->left:p->right; } p=(BSTree )malloc(sizeof(BSTNode)); //生成新结点 p->key=key; p->left=p->right=NULL; if(tptr==NULL) //原树为空，新插入的结点为新的根 tptr=p; else if(keykey) f->left=p; else f->right=p; return tptr;
BSTree createBST()//建立二叉树
{
BSTree t=NULL; //根结点 KeyType key; cin>>key; while(key!=0) { t=insertBST(t,key); cin>>key; } return t;
}
void inorder_btree(BSTree root)// 中序遍历打印二叉排序树
{
BSTree p=root; if(p!=NULL){ } inorder_btree(p->left ); coutkeyright );
}
int searchBST(BSTree t,KeyType key)//查找
{
if(t==NULL) return 0; if(key==t->key) return 1;
else
if(keykey)
return searchBST(t->left,key);
else if(key>t->key)
return searchBST(t->right,key);
else
return 0;
}
BSTree deleteBST(BSTree tptr,KeyType key)//删除
{
BSTree p,tmp,parent=NULL;
p=tptr;
while(p)
{
if(p->key==key)
break;
parent=p;
p=(key
key)?p->left:p->right;
}
if(!p) return NULL;
tmp=p;
if(!p->right&&!p->left) /*p的左右子树都为空*/
{
if(!parent) //要删根，须修改根指针
tptr=NULL;
else if(p==parent->right)
parent->right=NULL;
else
parent->left=NULL;
free(p);
}
else if(!p->right) //p的右子树为空，则重接p的左子树
{
p=p->left;
if(!parent) //要删根，须修改根指针
tptr=p;
else if(tmp==parent->left)
parent->left=p;
else
parent->right=p;
free(tmp);
}
else if(!p->left) //的左子树为空，则重接p的左子树
{
p=p->right;
if(!parent) //要删根，须修改根指针
tptr=p;
else if(tmp==parent->left)
parent->left=p;
else
parent->right=p;
free(tmp);
}
else if(p->right&&p->left) //p有左子树和右子树，用p的后继覆盖p然后删去后继 { //另有方法：用p的前驱覆盖p然后删去前驱||合并p的左右子树
parent=p; //由于用覆盖法删根，则不必特殊考虑删根
p=p->right;
while(p->left)
{
parent=p;
p=p->left;
}
tmp->key=p->key;
if(p==parent->left)
parent->left=NULL;
else
parent->right=NULL;
free(p);
}
return tptr;
}
int main()
{
KeyType key;
int flag,test;
char cmd; BSTree root; do { cout>cmd; flag++; }while(cmd!='a'&&cmd!='A'); if(cmd=='A'||cmd=='a') { cout
inorder_btree(root);
cout
cout
cout
**"
cout
**"
cout
switch(cmd)
{
case 's':
case 'S':
cout
cin>>key; test=searchBST(root,key); if(test==0) cout
break; case 'i': case 'I': cout>key; root=insertBST(root,key); //注意必须将值传回根 break; case 'd': case 'D': cout>key; root=deleteBST(root,key); //注意必须将值传回根 if(root==NULL) cout
} } }while(cmd!='q'&&cmd!='Q'); } }while(cmd!='b'&&cmd!='B'); return 0;