二叉チェーンテーブルで二叉検索ツリーを実現する(二)

</pre><pre code_snippet_id="367806" snippet_file_name="blog_20140528_2_6875764" name="code" class="cpp">/*
	          ：
	        ,    ；
	    ；
	author:    
	Date:2014-5-28
	Version:3.0
*/
#include <iostream>
#include <string>
typedef int T;//         
using namespace std;
class BiTree
{
private:
	struct BiNode{
		T data;
		BiNode *lchild,*rchild;
		BiNode(T d){
			data=d;
			lchild=nullptr;
			rchild=nullptr;
		}
	};
	BiNode *root;
public:
	BiTree(){
		//root=root->rchild=root->rchild=nullptr;
		root=nullptr;
	}
	~BiTree(){
		
	}
	//         
	//           
	//       （    ）
	bool addBiNode(BiNode *&nodeRoot,T d){
		if(nodeRoot==nullptr){
			BiNode *p=new BiNode(d);
			nodeRoot=p;
			cout<<p->data<<"  insert success!"<<endl;
			return true;
		}else if(nodeRoot!=nullptr&&d<nodeRoot->data){
			//      
			addBiNode(nodeRoot->lchild,d);
		}else if(nodeRoot!=nullptr&&d>(nodeRoot)->data){
			//      
			addBiNode(nodeRoot->rchild,d);
		}else{
			cout<<"       "<<endl;
			return false;
		}
	}
	BiNode *&getRoot(){//        
		return root;
	}
	BiNode *getPtrToRoot()const{
		return root;
	}
	bool Traverse(const BiNode *b,string type)const{
		if(type=="PreOrderTraverse"){
			cout<<"
        :"<<endl;
			PreOrderTraverse(b);
			return true;
		}else if(type=="InOrderTraverse"){
			cout<<"
        :"<<endl;
			InOrderTraverse(b);
			return true;
		}else if(type=="PostOrderTraverse"){
			cout<<"
        :"<<endl;
			PostOrderTraverse(b);
			return true;
		}else{
			cout<<"      !"<<endl;
			return false;
		}
			
	}
	
	//            
	bool Search(BiNode *&nodeRoot,T d){
		if(nodeRoot==nullptr)
			return false;
		else{
			if(nodeRoot->data==d){
				return true;
			}else if(nodeRoot->data<d){
				return  Search(nodeRoot->rchild,d);
			}else
				return  Search(nodeRoot->lchild,d);
		}
	}
	//             
	bool DeleteBST(BiNode *&nodeRoot,T d){
		if(nullptr==nodeRoot)//      
			return false;
		else{
			if(nodeRoot->data==d){//
				return Delete(nodeRoot);
				//Delete(nodeRoot);
			}else if(nodeRoot->data<d){
				return DeleteBST(nodeRoot->rchild,d);
				//DeleteBST(nodeRoot->rchild,d);
			}else
				return DeleteBST(nodeRoot->lchild,d);
				//DeleteBST(nodeRoot->lchild,d);
			}
	}
protected:
	//    
	//      
	//          ，           ，            
	//      
	//              ，        
	//nodeRoot       
	//      ，     ，      
		bool Delete(BiNode *&nodeRoot){
		//             ，        
		if(nullptr==nodeRoot->rchild){
			BiNode *temp=nodeRoot;
			nodeRoot=nodeRoot->lchild;
			delete temp;
			return true;
		}else if(nullptr==nodeRoot->lchild){//           
			BiNode *temp=nodeRoot;
			nodeRoot=nodeRoot->rchild;
			delete temp;
			return true;
		}else{//       
			//                        
			//                         
			//              
			BiNode *temp=nodeRoot->lchild;//temp           
			BiNode *preTemp=nodeRoot->lchild;
			while(nullptr!=temp->rchild){
				preTemp=temp;// preTemp         
				temp=temp->rchild;//          
				//temp        
			}
			//   temp         
			nodeRoot->data=temp->data;//    ，          ，          。
			/*
							50
						30		70
					 20
				      50， preTemp=temp=&30
			*/
			if(temp!=preTemp)
				preTemp->rchild=temp->lchild;//                    
			else
				nodeRoot->lchild=temp->lchild;
			delete temp;//     
			return true;
		}
		return false;
	}

	//T          ，   <<   
	void Visit(const BiNode *r)const{
		cout<<r->data<<" ";
	}
	//      ，           
	//    ,    
	void PreOrderTraverse(const BiNode *nodeRoot)const{
		if(nodeRoot!=nullptr)
			Visit(nodeRoot);
		if(nodeRoot->lchild!=nullptr)
			PreOrderTraverse(nodeRoot->lchild);
		if(nodeRoot->rchild!=nullptr)
			PreOrderTraverse(nodeRoot->rchild);
	}
	//    
	void InOrderTraverse(const BiNode *nodeRoot)const{
		if(nodeRoot->lchild!=nullptr)
			InOrderTraverse(nodeRoot->lchild);
		if(nodeRoot!=nullptr)//        
			Visit(nodeRoot);
		if(nodeRoot->rchild!=nullptr)
			InOrderTraverse(nodeRoot->rchild);
	}
	//    
	void PostOrderTraverse(const BiNode *nodeRoot)const{
		if(nodeRoot->lchild!=nullptr)
			PostOrderTraverse(nodeRoot->lchild);
		if(nodeRoot->rchild!=nullptr)
			PostOrderTraverse(nodeRoot->rchild);
		if(nodeRoot!=nullptr)
			Visit(nodeRoot);
	}
};

        return        。

      ，            。

<pre name="code" class="cpp">#include "bit4.cpp"
int main()
{
	
	BiTree b;
	//b.addBiNode(&b.root,50);//      //      
	b.addBiNode(b.getRoot(),50);//       
	int i;
	int arr[9]={30,40,35,27,100,90,110,95,-999};
	for(int j=0;j<9;j++)
	{
		i=arr[j];
		if(i==-999)
			break;
		b.addBiNode(b.getRoot(),i);
	}
	b.Traverse(b.getPtrToRoot(),"PreOrderTraverse");
	b.Traverse(b.getPtrToRoot(),"InOrderTraverse");
	b.Traverse(b.getPtrToRoot(),"PostOrderTraverse");
	while(true)
	{
	int k;
	cout<<"
       :"<<endl;
	cin>>k;
	if(b.Search(b.getRoot(),k))
		cout<<"OK"<<endl;
	else
		cout<<"NO"<<endl;
	}
	cin.get();
	system("pause");
	return 0;
}