二叉ソートツリーの作成、挿入、削除、検索、4種類の遍歴C++完全実現

#include<iostream>
#include<string>
#include<queue>
using namespace std;

typedef int KeyType;
#define NUM 13
class BinSTree;
class BinStreeNode
{
public:
	KeyType key;
	BinStreeNode *lchild;
	BinStreeNode *rchild;
	BinStreeNode()
	{
		lchild=NULL;
		rchild=NULL;
	}
};

class BinSTree
{
public:
	BinStreeNode *root;
	BinSTree()
	{
		root=NULL;
	}
	~BinSTree()
	{
		//delete root;
	}
	BinStreeNode *BSTreeSearch(/*BinStreeNode *bt,*/KeyType k,BinStreeNode *&p);//      NULL,p         
	void BSTreeInsert(KeyType k);//bt   ，        ，    root
	int BSTreeDelete(KeyType k);
	void BSTreePreOrder(BinStreeNode *bt);
	void BSTreeInOrder(BinStreeNode *bt);
	void BSTreeAfOrder(BinStreeNode *bt);
	void BSTreeLevelTraverse(BinStreeNode *bt);//    
	bool IsEmpty()
	{
		return root==NULL;
	}
};
/*
*          
*      bt           k   ，     ，           
*      ，  p        ;     ，  p  k       
*/
BinStreeNode *BinSTree::BSTreeSearch(/*BinStreeNode *bt,*/KeyType k,BinStreeNode *&p)
{
	BinStreeNode *q=NULL;
	q=root;
	while(q)
	{
		p=q;
		if(q->key==k)
			return p;
		else if(q->key>k)
			q=q->lchild;
		else
			q=q->rchild;
	}
	return NULL;
}
//    
void BinSTree::BSTreeInsert(KeyType k)
{
	BinStreeNode *p=NULL,*q;
	q=root;
	if(BSTreeSearch(k,p)==NULL)//        
	{
		BinStreeNode *r=new BinStreeNode;
		r->key=k;
		if(q==NULL)//     
		{
			root=r;
			return ;
		}
		if(p&&k<p->key)
			p->lchild=r;
		else if(p&&k>p->key)
			p->rchild=r;
	}
}
//    
void BinSTree::BSTreePreOrder(BinStreeNode *bt)
{
	if(bt)
	{
		cout<<bt->key<<" ";
		BSTreePreOrder(bt->lchild);
		BSTreePreOrder(bt->rchild);
	}
}
//    
void BinSTree::BSTreeInOrder(BinStreeNode *bt) //     O(N);
{
	if(bt)
	{
		
		BSTreeInOrder(bt->lchild);
		cout<<bt->key<<" ";
		BSTreeInOrder(bt->rchild);
	}
}
//    
void BinSTree::BSTreeAfOrder(BinStreeNode *bt)
{
	if(bt)
	{
		
		BSTreeAfOrder(bt->lchild);
		BSTreeAfOrder(bt->rchild);
		cout<<bt->key<<" ";
	}
}
//    
void BinSTree::BSTreeLevelTraverse(BinStreeNode *bt)
{
	queue<BinStreeNode*> q;
	if(bt)
		q.push(bt);
	while(!q.empty())
	{
		cout<<q.front()->key<<" ";//      
		if(q.front()->lchild)
			q.push(q.front()->lchild);
		if(q.front()->rchild)
			q.push(q.front()->rchild);
		q.pop();
	}
	cout<<endl;
}
//         ，      1，    0.
int BinSTree::BSTreeDelete(KeyType k)
{
	BinStreeNode *f,*p,*q,*s;
	p=root;
	f=NULL;
	//      k   ，            
	while(p&&p->key!=k)
	{
		f=p; //f     
		if(p->key>k)
			p=p->lchild;
		else
			p=p->rchild;
	}
	if(!p)//           
		return 0;
	if(p->lchild==NULL) //           
	{
		if(f==NULL)//         
			root=p->rchild;
		else if(f->lchild==p)//               
			f->lchild=p->rchild;
		else                //               
			f->rchild=p->rchild;
		delete p;
	}
	else //         
	{
		q=p;
		s=p->lchild;
		while(s->rchild) //                  ,               
		{
			q=s;
			s=s->rchild;
		}
		if( q == p )  
            q->lchild = s->lchild;  
        else  
            q->rchild = s->lchild;  
        p->key = s->key;  //        
        delete s; 
	}
	return 1;
}


int main()
{
	int a[NUM]={34, 18, 76, 13,12,11, 52, 82, 16, 67, 58, 73, 72 };
	BinSTree bst;
	BinStreeNode *pBt = NULL, *p = NULL, *pT = NULL;
	for(int i=0;i<NUM;i++)
	{
		bst.BSTreeInsert(a[i]);
	}
	pT = bst.BSTreeSearch(51, p ); //        
	bst.BSTreeLevelTraverse(bst.root);
	if(pT)
	{
		cout<<pT->key<<endl;
	}
    bst.BSTreePreOrder(bst.root);  
    cout << endl;  
    bst.BSTreeDelete(13);   //           
    bst.BSTreePreOrder(bst.root);  
    cout << endl;  
    bst.BSTreeDelete( 76 );   //           
    bst.BSTreePreOrder(bst.root);  
    cout << endl;
	system("pause");
	return 0;
}

二叉ソートツリーの作成、挿入、削除、検索、4種類の遍歴方式のC++完全実装版