binarysorttree.cpp

异质树构造c++实现

/*--------------------------------------------------------------------------------
chenhai 20071128
实现排序树
----------------------------------------------------------------------------------*/  
#include "stdafx.h" 
 
/**-------------------------------------------------------------------------------
//添加一个 节点：排序二叉树，规则是：如果新节点person.age小于当前节点person.age,
//则加入左孩子，否则加入右孩子
//入参：根指针,被增加的节点指针
//返回：树根指针
-------------------------------------------------------------------------------*/
   
 Node* BinarySortTree::generateTree(Node *root,Node *childNode){
	 if( root == NULL){
		 root = childNode;                                                              //第一个节点，直接作为根
	 }else{
		 Node* p = root;
		 while(1){
			 //cout<<childNode->person->getId();
			 if( strcmp( ( childNode->person->getId() ) , ( p->person->getId() ) )<0 ){ //判断字符串字典顺序strcmp
					 
					 if( p->lchild!=NULL){
					 p = p->lchild;
					 }else{
						p->lchild = childNode;
						break;
					 }
				 }else{
					 if(p->rchild!=NULL){
						 p=p->rchild;
					 }else{
						 p->rchild=childNode;
					 break;
					 }
				 }
				 
			 }
	  
	 }
	  
	 return root;                                           //返回根
 }
 
/**------------------------------------------------------------------------------
//销毁一棵树，释放每个节点的内存
//入参：根指针
//返回：无
--------------------------------------------------------------------------------*/
 Node* BinarySortTree::destroyTree(Node *root){

	 
	 if( root!= NULL){                                     //采用后根遍历，并删除节点
		 destroyTree( root->lchild);
		 destroyTree( root->rchild);
		 delete root;
		 root = NULL;
		 return root;
	 } 
	 return NULL;
}
/**------------------------------------------------------------------------------
//打印树，按中根遍历,打印一个树节点列表
//入参：树的根指针
//返回值：无
--------------------------------------------------------------------------------*/
 void BinarySortTree::listTree(Node *root){  
 
 
	 if(root != NULL){

		 listTree(root->lchild);                      //遍历左子树

		 cout<<root->person->getId()<<",";
		 
		 cout<<root->person->getName()<<",";            //打印节点信息

				root->person->eat() ;                   //多态打印不同信息
		 cout<<endl;

		 listTree(root->rchild);                      //遍历右子树
	 } 
 
 
}
 /**---------------------------------------------------------------
 //找出被删节点的指针并返回
 入参：根；被删节点ID
 返回：被删节点指针
 -------------------------------------------------------------------*/
Node* BinarySortTree::findDeletingNode(Node* root, char* id){
		Node* deletingNode = NULL;                             //存返回指针
		Node* curr_p = NULL;                                   //存查找指针

		if(id == NULL ) return NULL;
		curr_p = root;
		while(curr_p != NULL){
			if( strcmp(curr_p->person->getId()   , id ) == 0 ){ //找到了ID对应节点
				deletingNode = curr_p;
				break;
			}
			if(strcmp(id, curr_p->person->getId()     ) < 0 ){   //ID 比当前节点小，则在左树找
				curr_p= curr_p->lchild;
			}else{                                                //否则在右树找
				curr_p = curr_p->rchild;
			}
		}
		return deletingNode;
	}
	 /**---------------------------------------------------------------
 //找出被删节点的父指针并返回
 入参：根；被删节点指针
 返回：被删节点父指针
 -------------------------------------------------------------------*/
Node* BinarySortTree::findDeletingParent(Node* root, Node* child){
		Node* deletingNodeParent = NULL;                            //保存被删节点的父指针
		Node* curr_p = NULL;                                 //存查找指针

		curr_p = root;
		while(curr_p != NULL){
			if( curr_p->lchild == child || curr_p->rchild == child ){            //找到父亲了
				deletingNodeParent = curr_p;
				break;
			}
			if( strcmp( child->person->getId(),curr_p->person->getId()   ) < 0 ){ //子节点比当前节点小则在左树找
				curr_p = curr_p->lchild;
			}else{                                                               //在右树找
				curr_p = curr_p->rchild;
			}

		}

		return deletingNodeParent;
	}  
/*----------------------------------------------------------------------------
删除指定节点
入参：根；被删节点；被删节点的父节点
返回：根
-----------------------------------------------------------------------------*/
Node* BinarySortTree::deleteNode(Node *root,char* id ){

	Node* deletingNode = NULL;                                                    //被删节点
	Node* deletingNodeParent = NULL;                                              //被删的父
	//Node* root_primary = root;                                                    //记住根以便返回
	

	deletingNode = this->findDeletingNode( root,   id);                   //得到被删节点
	if(deletingNode==NULL) return root;
	//if(deletingNode == root_primary){                                     //如果想删的是整个树，则直接销毁树                        
		//	this->destroyTree(root_primary);
		//	return NULL;
	//}
	deletingNodeParent = this->findDeletingParent( root,  deletingNode); //得到被删节点父节点

												//被删节点为空，无操作

	if( ( deletingNode->lchild == NULL )&&(deletingNode->rchild == NULL) ){			//是叶子节点，直接删除
		if( deletingNode != NULL){

            if( deletingNodeParent->lchild == deletingNodeParent )                      //如果被删节点是父的左孩子
			{
				deletingNodeParent->lchild = NULL;									//被删的节点父的左孩子指针置NULL
			}else{
				deletingNodeParent->rchild = NULL;                                     //被删的节点父的右孩子指针置NULL
			}
			delete deletingNode;
			deletingNode = NULL;
			return root;
		}

	}
                                                                     //非叶子时，分4种情况
	Node* r;
	Node* s;
	int flag=0;
	if( deletingNode->lchild == NULL){                               //1 被删点左孩子为空，使用其右子树根取代被删点
		if( deletingNode == root )
			root = deletingNode->rchild;
		else{
			r=deletingNode->rchild;
			flag=1;
		}
	}else	if( deletingNode->rchild == NULL) 							//2 被删点右孩子为空，使用其左子树根取代被删点
			if(deletingNode == root)
				root = deletingNode->lchild;
			else{
				r = deletingNode->lchild;
				flag = 1;
			}
		 else{                                                      //3 左右子树均存在，则找被删点右子树中的最小点，
			                                                        //  以此取代被删点。
			s=deletingNode;

			r=s->rchild;
			while( r->lchild != NULL){
				s=r;
				r=r->lchild;
			}
			r->lchild = deletingNode->lchild;
			if( s!=deletingNode){
				s->lchild = r->rchild;
				r->rchild = deletingNode->rchild;
			}
			if( deletingNode == root )
				root = r;
			else
				flag=1;
		 
	}
	if(flag==1) 
		if(deletingNode == deletingNodeParent->lchild)
			deletingNodeParent->lchild = r;
		else
			deletingNodeParent->rchild = r;

 

	            /*if( deletingNodeParent->lchild == deletingNodeParent )                      //如果被删节点是父的左孩子
			{
				deletingNodeParent->lchild = NULL;									//被删的节点父的左孩子指针置NULL
			}else{
				deletingNodeParent->rchild = NULL;                                     //被删的节点父的右孩子指针置NULL
			}*/
			if( deletingNode != NULL){
				delete deletingNode;
				deletingNode = NULL;
			}
	return root;

}   
/*----------------
返回树深度
入参：根
返回: 树深度
-----------------*/                       
int  BinarySortTree::getDepth(Node* root){
	int leftdep,rightdep;
	if( root == NULL){
		return 0;
	}else{
		leftdep = getDepth( root->lchild );
		rightdep = getDepth( root->rchild );
		return leftdep>rightdep? (leftdep+1) : (rightdep + 1) ;
	}
}
/**---------------------
打印一个可视化树
-----------------------*/
void BinarySortTree::printTree(Node* root){
    //Node* p = root;

    int x=0;
	if( root != NULL){
		  //cout.width(x);


 
				printTree( root->lchild);
		 
 
			  printTree( root->rchild);
 
		  cout<<root->person->getId()<<" ";
		  cout<<endl;
	}

}
/*
#include<queue.h>
  void   HiberarchyRetriveATree( Node   *root,void   (*   visit)( Node))   
  {   
                queue< Node*>   tree;   
                 Node*   tmp   =   NULL;   
                tree.push(root);   
                while   (!tree.empty())   
                {   
                              tmp   =   tree.front();   
                              tree->pop();   
                              (*visit)(tmp);   
                              if   (tmp->lchild   !=   NULL)   
                                            tree->push(tmp->lchild);   
    
                              if   (tmp->rchild   !=   NULL)   
                                          tree->push(tmp->rchild);   
                }   
  }   
    
  void   Visit( Node*   node)   
  {   
                cout<<node->person->getId()<<"   ";   
  }  */