00348307江云亮hw4_0401.cpp

二叉树的最短路径

	*/
	void Insert(char father,char child,int check);
	/*函数名称：void Insert(char father,char child,int check);
	函数功能描述：//将值child建立一个结点作为值为father的结点的子结点（check=1左子结点，check=2右子结点）
	函数调用之前的预备条件：树存在
	返回值：无
	函数的输入参数：字符型father,child,为父子的值，整型check为关系
	函数的输出参数：无
	*/	
	friend int Distance(BinaryTreeNode* root,BinaryTreeNode* p,BinaryTreeNode* q,int& len);
	//友函数，返回p，q两个结点的最小距离
};

BinaryTree::BinaryTree(char val)
{   
	root=new BinaryTreeNode;  //开辟空间
	root->setValue(val);      //赋值
	root->setLeftchild(NULL); //左子树为空
	root->setRightchild(NULL);//右子树为空
}

BinaryTree::~BinaryTree()
{   
	DeleteBinaryTree(root);  //删根结点
}

void BinaryTree::DeleteBinaryTree(BinaryTreeNode* root)
{   
	if (root)  
	{
		DeleteBinaryTree(root->left);  //删左子树
		DeleteBinaryTree(root->right); //删右子树
		delete root;                   //删本身
	}
}

BinaryTreeNode* BinaryTree::Root()  
{   
	return root;                 //返回根结点
}

bool BinaryTree::isEmpty()
{   
	if (root==NULL) return 1;    //空树
	return 0;
}

BinaryTreeNode* BinaryTree::PreOrdersearch(BinaryTreeNode* root,char val)
{
	BinaryTreeNode* ret;  //临时变量，作为标记，如果找到val直接返回
	if (root!=NULL)
	{
		if (root->value()==val)  //如果当前结点的值为val
			return root;         //返回当前结点的指针，退出整个过程
		else                     
		{
			ret = PreOrdersearch(root->leftchild(),val); //访问左子树
			if (ret!=NULL) return ret;  //找到val，返回相应的指针
			ret = PreOrdersearch(root->rightchild(),val); //访问右子树
			if (ret!=NULL) return ret;  //找到val，返回相应的指针
		}
	}
	return NULL;  //没找到，返回空指针
}

void BinaryTree::Insert(char father,char child,int check)
{
	BinaryTreeNode* p=new BinaryTreeNode; //新建一个结点p
	p->setLeftchild(NULL);  //左子树为空
	p->setRightchild(NULL); //右子树为空
	p->setValue(child);     //child值赋给p的数据域 
	BinaryTreeNode* temp=PreOrdersearch(root,father); //临时指针指向父结点
	if (check==1)           //左子结点
		temp->setLeftchild(p);  //将p设为temp的左子结点
	else                    //右子结点
		temp->setRightchild(p); //将p设为temp的右子结点
}

int Distance(BinaryTreeNode* root,BinaryTreeNode* p,BinaryTreeNode* q,int& len)
{
	/*函数名称：int Distance(BinaryTreeNode* root,BinaryTreeNode* p,BinaryTreeNode* q,int& len)
	函数功能描述：友函数，返回p，q两个结点的最小距离
	函数调用之前的预备条件：树存在
	返回值：整型变量，记录p，q两个结点的距离
	函数的输入参数：二叉树结点指针root，p，q，整型的引用len代表该结点到p或q的距离
	函数的输出参数：整型变量
	*/	
	int len1,len2,length,check;
    //len1,len2：记录该结点到p或q的距离
	//length：记录p，q的最小距离
	//check：标记该结点与p，q的关系。
	//check=2说明该结点与p，q均有关系（有关系定义为：其结点及左子树，右子树含有p或q）
	//check=1说明该结点与p或q有关系。check=0说明没关系
	check=0;  //初始化
    if (p==q)	//p==q
		return 0;  //距离为0
	if (root==NULL)  //当前结点为空
	{
		len=0;          //标记为0
		return 0;       //距离为0
	}
	if (root==p||root==q)  //root为p或q
		check++;           //check标记
	length=Distance(root->leftchild(),p,q,len1);//递归搜索左子树
	if (length!=0)         //找到所求的祖先结点
		return length;     //立刻返回
	if (len1>0)            //左子树中找到p或q
		check++;           //check标记
	length=Distance(root->rightchild(),p,q,len2);//递归搜索右子树
	if (length!=0)         //找到所求的祖先结点
		return length;     //立刻返回
	if (len2>0)            //右子树中找到p或q
		check++;           //check标记
    if (check==2)          //该结点为所求的祖先结点
		return len1+len2;  //返回两距离之和
	if (check==1)          //该结点和p或q中的一个有关系
	{
		len=len1+len2+1;   //距离加1
		return 0;
	}
	len=0;                 //没关系,距离为0
	return 0;
}


void main()
{
	BinaryTree * onetree;  //新建一棵树
	BinaryTreeNode * temp1;  //临时变量
	BinaryTreeNode * temp2;  //临时变量
	BinaryTreeNode * head;   //临时变量记录头结点
	char father,child,nod1,nod2;//father,child:父子的值,nod1,nod2:待查两结点的值
	int check,distance,len; //check父子关系 distance两结点距离 
	cout <<"请先输入头结点(例如头结点为a,输入a)：";
	cin >>father;  //输入头结点
    onetree=new BinaryTree(father);  //构造函数用father值作为头结点的值建立树
	while (1)  //重复输入结点
	{
		cout <<"请输入需要插入的结点。输入方法如下："<<endl;
		cout <<"按父结点、子结点、关系的顺序输入，父结点、子结点的数据类型为字符型，关系的数据类型为整型，1表示左子树，2表示右子树，其它数无意义，0退出输入。"<<endl;
		cout <<"例如：父结点为a，左子结点为b，输入：a b 1，注意空格的输入是必要的。"<<endl;
        cout <<"如果想停止输入,请输入在输入关系的整型变量的时候输入0,例如“a b 0”,“1 2 0”均为结束标志"<<endl;	
		cin >>father>>child>>check;  
		if (check==0)  //结束标志
			break;
		if (check!=1 && check!=2)  //关系输入有误，重新输入
		{
			cout <<"输入错误，重新输入"<<endl;
			continue;
		}
		head=onetree->Root();  //head指向头结点
		temp1=onetree->PreOrdersearch(head,father);  //查找father在树中的位置
		if (temp1==NULL)       //father尚不在树中，不能建立以father为父结点的子结点，重新输入
		{
			cout <<"输入错误，重新输入"<<endl;
			continue;
		}
		if (check==1)          //结点为左子结点
			temp1=temp1->leftchild();  //temp1指向当前父结点的左子结点
		else temp1=temp1->rightchild();  //结点为右子结点
		if (temp1!=NULL)       //当前的位置已有结点，不能再插入结点，重新输入
		{
			cout <<"输入错误，重新输入"<<endl;
			continue;
		}
		temp1=onetree->PreOrdersearch(head,child);  //查找child在树中的位置
		if (temp1!=NULL)        //child已出现过，不能再做子结点，重新输入
		{
			cout <<"输入错误，重新输入"<<endl;
			continue;
		}
		onetree->Insert(father,child,check); //输入正确，插入树中
	}
	cout <<"此树已建立完毕"<<endl;
	while (1)
	{
		cout <<"输入两个结点，求其最小距离，例如：要求a和b的距离，输入：a b"<<endl;
		cout <<"如要停止求距离，输入0 0"<<endl;
		cout <<"输入：";
		cin >>nod1>>nod2;  //输入两结点的值
		if (nod1=='0' && nod2=='0')  //结束标志
			break;
		head=onetree->Root();  //head指向头结点
		temp1=onetree->PreOrdersearch(head,nod1);  //查找第一个结点在树中的位置
		if (temp1==NULL)       //没找到，不能查找它与其它结点的位置，重新输入
		{
			cout <<"输入错误，重新输入"<<endl;
			continue;
		}
		temp2=onetree->PreOrdersearch(head,nod2);  ////查找第二个结点在树中的位置
		if (temp2==NULL)      //没找到，不能查找它与其它结点的位置，重新输入
		{
			cout <<"输入错误，重新输入"<<endl;
			continue;
		}
		distance=Distance(head,temp1,temp2,len);//输入正确，求得最小距离
		cout <<"结点"<<nod1<<"与结点"<<nod2<<"的最小距离是"<<distance<<endl; //输出
	}
}