6.46复制二叉树.cpp

严蔚敏 数据结构题集 第六章 答案 自己做的

#include<iostream.h>
typedef char ElemType;
#include"BTree.h"
void CopyBTree(BTreeNode *&BT2,BTreeNode *BT1)
{
	BTreeNode *s1[10],*s2[10],*p1,*p2;
	if(BT1==NULL){BT2=NULL;return;}
    int top=-1;
	p1=BT1;
	p2=NULL;
	top++;
	s1[top]=p1;
	BT2=new BTreeNode;
	BT2->data=p1->data;
	p2=BT2;
	s2[top]=BT2;
	while(top>=0)
	{
		while((p1=s1[top])&&p1!=NULL&&(p2=s2[top]))
		{
			p2->data=p1->data;
			if(p1->left!=NULL)
			{
				p2->left=new BTreeNode;
				
			}
			else {p2->left=NULL;}

			p2=p2->left;
         	top++;
			s1[top]=p1->left;
			s2[top]=p2;
			
		}
		top--;
		if(top>=0)
		{
			p1=s1[top];
			p2=s2[top];
			top--;

			if(p1->right!=NULL)
			{
				p2->right=new BTreeNode;
				p2=p2->right;
				p2->data=p1->data;
			}
			else 
			{
				p2->right=NULL;
				p2=p2->right;
			}
			top++;
			s1[top]=p1->right;
			s2[top]=p2;
		}
	}
}
void main()
{
	BTreeNode *BT1,*BT2=NULL;
	InitBTree(BT1);
	char *a;
	a=new char[30]; 
	int i=0;
	cout<<"输入二叉树以@结束:"<<endl;
	cin>>*a;
	while(*(a+i)!='@')
	{
		i++;
		cin>>*(a+i);
	}
	CreateBTree(BT1,a);
	CopyBTree(BT2,BT1);
	cout<<"复制结果为："<<endl;
	PrintBTree(BT2);

}