二叉链表查找

二叉链表查找

Problem Description
有一棵二叉树，其结点值为字符型并假设各值互不相等，采用二叉链表存储。现输入其扩展二叉树的前序遍历序列，建立该二叉树，要求在该二叉树中查找字符值为x的结点，找到x时，输出x的相关信息，没找到x则输出"not find"。
Input
第一行为一个整数n，表示以下有n组数据，每组数据占两行，每组第一行表示扩展二叉树的前序遍历序列；第二行表示待查找的字符x。
Output
若查找成功，先输出该结点的双亲值，再输出其左右孩子值：(左孩子,右孩子)，若其双亲或者孩子值为空输出#；查找失败输出“not find”。

Sample Input
4
AB#D##C##
A
AB#D##C##
B
AB#D##C##
D
AB#D##C##
G
Sample Output
#(B,C)
A(#,D)
B(#,#)
not find
参考代码1：

#include<iostream>
using namespace std;
struct BiNode
{
	char data;
	BiNode *r,*l,*p;
};
BiNode *creat()
{
	char ch;
	cin>>ch;
	BiNode *root=NULL;
	if(ch!='#')
	{
		root=new BiNode;
		root->data=ch;
		root->l=creat();
		root->r=creat();
	}
	return root;
}
BiNode *haizi(BiNode *root,char x)
{
	if(root)
	{
		if(root->data==x)
		{
			return root;
		}
		else
		{
			BiNode *bt=haizi(root->l,x);
			if(bt)
				return bt;
			else
			{
				return haizi(root->r,x);
			}
		}
	}
		else
			return NULL;
}
BiNode *parent(BiNode *root,char x)
{
	if(root)
	{
	if(root->l&&root->l->data==x||
	  root->r&&root->r->data==x)
	{
		return root;
	}
	else 
	{
		BiNode *bt=parent(root->l,x);
		if(bt)
			return bt;
		else
			return parent(root->r,x);
	}
	}
	else 
		return NULL;
}
int main()
{
	int n;char b;
	while(cin>>n)
	{
		while(n--)
		{
			BiNode *child,*par;
			BiNode *root=creat();
			cin>>b;
			par=parent(root,b);
			child=haizi(root,b);
			if(child)
			{
				if(par)
					cout<<par->data;
				else 
					cout<<"#";
				if(child->l)
					cout<<"("<<child->l->data<<",";
				else 
					cout<<"("<<"#"<<",";
				if(child->r)
					cout<<child->r->data<<")"<<endl;
				else
					cout<<"#)"<<endl;
			}
			else
				cout<<"not find"<<endl;
		}
	}
	return 0;
}

参考代码2(三叉链表)：

#include<iostream>
using namespace std;
struct BiNode 
{
   char data;
   BiNode *lchild,
	   *rchild,*parent;
};
BiNode *creat()
{
	char ch;
	BiNode *bt=NULL;
	cin>>ch;
	if(ch!='#')
	{
		bt=new BiNode;
		bt->data=ch;
		bt->parent=NULL;
		bt->lchild=creat();
		if(bt->lchild)
		{
			bt->lchild->parent=bt;
		}
		bt->rchild=creat();
		if(bt->rchild)
		{
			bt->rchild->parent=bt;
		}
	}
	return bt;
}
void Release(BiNode *bt)
{
	if(bt)
	{
		Release(bt->lchild);
		Release(bt->rchild);
		delete bt;
	}
}
BiNode *Locate(BiNode *bt,char x)
{
	if(bt)
	{
		if(bt->data==x)
			return bt;
		BiNode *t=Locate(bt->lchild,x);
		if(t)
		{
          return t;
		}
		return Locate(bt->rchild,x);
	}
	else return NULL;
}
int main ()
{
    int n;
	char x;
	cin>>n;
	while(n--)
	{
       BiNode *t,*root=creat();
	   cin>>x;
	   t=Locate(root,x);
       if(t)
	   {
		   if(t->parent)
			   cout<<t->parent->data<<"(";
		   else
			   cout<<"#(";
		   if(t->lchild)
			   cout<<t->lchild->data<<",";
		   else
			   cout<<"#,";
		   if(t->rchild)
			   cout<<t->rchild->data<<")"<<endl;
		   else
			   cout<<"#)"<<endl;
	   }
	   else
		   cout<<"not find"<<endl;
	   Release(root);
	}
	return 0;
}