二叉排序树的查找、删除、插入

#include<iostream> using namespace std; typedef int KeyType; struct BSTree { KeyType key; BSTree *lchild,*rchild; }; BSTree *InitBSTNode() { BSTree *T=NULL; return T; } BSTree *InsertBST(BSTree *T,KeyType k) { BSTree *p=T; BSTree *f=p;//用来暂存当前查找的节点 while(p) { if(p->key==k) return T; f=p; p=(k<p->key)?p->lchild:p->rchild; } p=new BSTree; p->key=k; p->lchild=p->rchild=NULL; if(T==NULL) T=p; else { if(k<f->key) f->lchild=p; else f->rchild=p; } return T; } void TravesBST(BSTree *T) { if(T) { TravesBST(T->lchild); cout<<T->key<<" "; TravesBST(T->rchild); } } BSTree *SearchBST(BSTree *T,KeyType k) { if(!T||k==T->key) return T; else { if(k<T->key) return SearchBST(T->lchild,k); else return SearchBST(T->rchild,k); } } BSTree *DelBST(BSTree *T,KeyType k) { BSTree *p=T,*f=NULL; while(p) { if(p->key==k) break; f=p; p=(k<p->key)?p->lchild:p->rchild; } if(!p) return T; if(!p->lchild) { if(p==T) T=p->rchild; else { if(f->lchild==p) f->lchild=p->rchild; else f->rchild=p->rchild; } delete p; } return T; } int main() { BSTree *T=InitBSTNode(); T=InsertBST(T,32); T=InsertBST(T,26); T=InsertBST(T,45); T=InsertBST(T,35); T=InsertBST(T,12); T=InsertBST(T,20); TravesBST(T); cout<<endl; cout<<"查找12结果："<<endl; if(SearchBST(T,12)==NULL) cout<<"没找到"<<endl; else cout<<"找到"<<endl; cout<<"查找23结果:"<<endl; if(SearchBST(T,23)==NULL) cout<<"没找到"<<endl; else cout<<"找到了"<<endl; cout<<"删除26"<<endl; T=DelBST(T,26); TravesBST(T); cout<<"删除22"<<endl; T=DelBST(T,22); TravesBST(T); return 0; }