tree.cpp

1.程序完整实现了异质树的遍历

#include <iostream>
#include <string>
#include "Person.h" 

using namespace std;

Tree::Tree()
{
}     
void Tree::travel(Person* tree)//前序遍历，递归
{
      if(tree!=NULL) 
	  {
	 	  travel(tree->l_Child);
			tree->print();
            travel(tree->r_Child);
	  }
      else
          {
		    return;
          }
}
  //删掉某个节点
void Tree::del(Person*tree,const string d)
{ 
	Person*p=findnode(tree,d);
	if(p==NULL)
	{
		cout<<"未找到该节点"<<endl;
		return;
	}
	if(p->r_Child !=NULL)//二叉排序树，有右孩子 
	{
		if(p->l_Child !=NULL)
		{
			insert_t(p->r_Child,p->l_Child);//如果有左孩子，则 把左孩子插入原节点的右子树 
			if(p->Father->r_Child == p)
				p->Father->r_Child=p->r_Child;
			else
				p->Father->l_Child=p->r_Child;
			p->r_Child->Father = p->Father;
		}
		else
		{
			if(p->Father->r_Child == p)//如果没有左孩子， 直接操作右孩子 
				p->Father->r_Child=p->r_Child;
			else
				p->Father->l_Child=p->r_Child;
			p->r_Child->Father = p->Father;
		}
		
	}	
	else//如果没有右孩子 ，直接操作左孩子 
	{
		if(p->l_Child != NULL)
		{
			if(p->Father->r_Child == p)
				p->Father->r_Child=p->l_Child;
			else
				p->Father->l_Child=p->l_Child;
			p->l_Child->Father= p->Father;
		}
		else//叶节点 
		{
			if(p->Father->r_Child == p)
				p->Father->r_Child = NULL;
			else
				p->Father->l_Child = NULL;		
		}
		
	}

	delete p;
	cout<<"删除成功"<<endl;
	return;
}


void Tree::insert_t(Person*tree,Person *p)//插入节点  
{
	Person *pre = NULL;
    Person *curr = tree; 
    	if(tree == NULL)
	{
		cout<<"根节点为空，请创建根节点"<<endl;
		return;
	}
    while(curr != NULL)
    {   
		pre = curr;
        if (curr->m_Name >= p->m_Name)//如果当前节点大于待插入节点，则搜索左子树
			 
            curr = curr->l_Child;       
        else
            curr = curr->r_Child; //否则，搜索右子树         
    }
    if(pre->m_Name >= p->m_Name)
	{
		pre->l_Child = p;
	}
	else
	{
		pre->r_Child = p;
	}
	p->Father = pre;
	cout<<"插入成功"<<endl;
}     

Person *Tree::findnode(Person* tree,string name)
{
    Person *curr = tree; 
    string find_temp;
    Person* F,* pre;
    find_temp = name;     
    F = NULL;
	if(tree == NULL)
	{
		cout<<"根节点为空，请创建根节点"<<endl;
		return NULL;
	}
    while(curr != NULL)//如果当前节点大于待查找节点，则继续搜索左子树；否则，搜索右子树 
    {   
		pre = curr;
        if (curr->m_Name > find_temp)
            curr = curr->l_Child;       
        else if(curr->m_Name < find_temp) 
            curr = curr->r_Child;            
        else
		{
            F = curr;
			return F;
		}
    }
	return F; 

}