이 진 트 리 의 옮 겨 다 니 기 + 동 구성 판단

두 갈래 나무의 옮 겨 다 니 기
최근 에 데이터 구조 가 나 무 를 배 웠 으 니 컴퓨터 에서 과거 코드 의 물건 을 꺼 내 복습 해 보 세 요.(지난 5 월 팀 프로 그래 밍 사다리 경기 GPLT 관련 문 제 를 만 났 는데 level 2 에서 이 진 트 리 에 관 한 문 제 를 만 났 는데 아직 배 운 적 이 없다 는 것 을 알 게 되 었 습 니 다. 서둘러 독학 을 하고 다음 코드 를 입력 하 세 요. 대부분의 코드 는 베 낀 것 이거 나 인터넷 에 있 는 것 이 었 습 니 다. 그 때 는 그런 의식 이 없 었 습 니 다. 인용 원 을 제때에 기록 하지 못 했 습 니 다. 죄송합니다.)데이터 구조 에서 나무 라 는 것 도 제 가 가장 철저하게 배 웠 습 니 다. 그때 제 가 열심히 노력 한 것 에 감 사 드 립 니 다. 종이 에 프로 그래 밍, 종이 에 추론 을 한 다음 에 분 산 된 수학 공부, 각종 코드 를 결합 시 켰 습 니 다.
두루

#include 
#include 
#include
#include
#include
#define MAX 20
#include
#define type char
using namespace std;
//typedef struct BTNode *Position;
//typedef Position btree;
typedef struct BTNode
{
	type data;
	BTNode* lchild, *rchild;
} btree;
btree* CreateBTree(btree *bt, bool isRoot)
{
	char ch;
	if (isRoot)
		printf("Root: ");
	fflush(stdin);         /*       */
	cin>>ch;
	fflush(stdin);
	if (ch != '#')
	{
		isRoot = false;
		bt = new BTNode;
		bt->data = ch;
		bt->lchild = NULL;
		bt->rchild = NULL;
		printf("%c's lchild child is: ", bt->data);
		bt->lchild = CreateBTree(bt->lchild, isRoot);
		printf("%c's rchild child is: ", bt->data);
		bt->rchild = CreateBTree(bt->rchild, isRoot);
	}
	return bt;
}
void preorder1(btree *node)
{
	if(node)
	{
		cout<<node->data<<" ";
		preorder1(node->lchild);
		preorder1(node->rchild);
	}
}
void preorder2(btree *root)
{
	btree* temp;
	stack<btree*> S;
	temp=root;
	while(temp||!S.empty())
	{
		while(temp)
		{
			cout<<temp->data<<" ";
			S.push(temp);
			temp=temp->lchild;
		}
		if(!S.empty())
		{
			temp=S.top();
			S.pop();
			temp=temp->rchild;
		}
	}
}
void inorder1(btree *node)
{
	if(node)
	{
		inorder1(node->lchild);
		cout<<node->data<<" ";
		inorder1(node->rchild);
	}
}
void inorder2(btree *root)
{
	btree* temp;
	stack<btree*> S;
	temp=root;
	while(temp||!S.empty())
	{
		while(temp)
		{
			S.push(temp);
			temp=temp->lchild;
		}
		if(!S.empty())
		{
			temp=S.top();
			S.pop();
			cout<<temp->data<<" ";
			temp=temp->rchild;
		}
	}
}
void postorder1(btree* node)
{
	if(node)
	{
		postorder1(node->lchild);
		postorder1(node->rchild);
		cout<<node->data<<" ";
	}
}
void postorder2(btree *root)
{
	if (!root)
		return;
	stack<btree*> s;
	stack<btree*> output;
	s.push(root);
	while (!s.empty())
	{
		btree *curr= s.top();
		output.push(curr);
		s.pop();
		if (curr->lchild)
			s.push(curr->lchild);
		if (curr->rchild)
			s.push(curr->rchild);
	}
	//cout<
	while (!output.empty())
	{
		cout << output.top()->data << " ";
		output.pop();
	}
}
void postorder3(btree *root)
{
	if (!root)
		return;
	stack<btree*> s;
	s.push(root);
	btree *prev = NULL;
	while (!s.empty())
	{
		btree *curr= s.top();
		// we are traversing down the tree
		if (!prev||prev->lchild== curr|| prev->rchild == curr)
		{
			if (curr->lchild)
			{
				s.push(curr->lchild);
			}
			else if (curr->rchild)
			{
				s.push(curr->rchild);
			}
			else
			{
				cout << curr->data << " ";
				s.pop();
			}
		}
		// we are traversing up the tree from the lchild
		else if (curr->lchild == prev)
		{
			if (curr->rchild)
			{
				s.push(curr->rchild);
			}
			else
			{
				cout << curr->data << " ";
				s.pop();
			}
		}
		// we are traversing up the tree from the rchild
		else if (curr->rchild == prev)
		{
			cout << curr->data << " ";
			s.pop();
		}
		prev = curr;  // record previously traversed node
	}
}
void levelorder(btree* root)
{
	queue<btree*> q;
	btree *temp;
	if(!root)
		return;
	q.push(root);
	while(!q.empty())
	{
		temp=q.front();
		q.pop();
		cout<<temp->data<<" ";
		if(temp->lchild)
			q.push(temp->lchild);
		if(temp->rchild)
			q.push(temp->rchild);
	}
	return;
}
int height(btree *root)
{
	int HL,HR,MAXH;
	if(root)
	{
		HL=height(root->lchild);
		HR=height(root->rchild);
		MAXH=(HL>HR)?HL:HR;
		return (MAXH+1);
	}
	else
		return 0;
}
int main()
{
	btree *bt;
	bt = CreateBTree(bt, true);//    
	cout<<"      "<<endl;
	preorder1(bt);//	      
	cout<<endl;
	cout<<"      （   ）"<<endl;
	preorder2(bt);//	       
	cout<<endl;
	cout<<"      "<<endl;
	inorder1(bt);//		      
	cout<<endl;
	cout<<"      （   ）"<<endl;
	inorder2(bt);//		       
	cout<<endl;
	cout<<"      "<<endl;
	postorder1(bt);//		      
	cout<<endl;
	cout<<"      （   ）"<<endl;
	//postorder2(bt);
	postorder3(bt);//		        3
	cout<<endl;
	cout<<"      （      ）"<<endl;
	postorder2(bt);//		        2
	cout<<endl;
	cout<<"      "<<endl;
	levelorder(bt);//	       
	cout<<endl;
	cout<<"       （  ): ";
	cout<<height(bt)<<endl;//	         
	return 0;
}

동구
이 부분 은 저장 성 빅 데이터 구조 mooc 를 베 낀 것 이다.

#include
#define type char
#define type char
#define MAX 20
using namespace::std;
struct treenode
{
	type data;
	int lchild;
	int rchild;
} tree1[MAX],tree2[MAX];
int buildtree(treenode tree[])
{
	bool book[MAX]= {false};
	int root;
	int N,i;
	char left,right;
	cin>>N;
	if(N)
	{
		for(i=0; i<N; i++)
		{
			cin>>tree[i].data>>left>>right;
			if(left!='-')
			{
				tree[i].lchild=left-'0';
				book[tree[i].lchild]=1;
			}
			else
				tree[i].lchild=-1;
			if(right!='-')
			{
				tree[i].rchild=right-'0';
				book[tree[i].rchild]=true;
			}
			else
				tree[i].rchild=-1;
		}
		for(i=0; i<N; i++)
			if(book[i])
				break;
		root=i;
		return root;
	}
	else
		return -1;
}
bool isomorphic(int R1,int R2)
{
	if(R1==-1&&R2==-1)
		return true;
	if((R1==-1&&R2!=-1)||(R1!=-1&&R2==-1))
		return false;
	if(tree1[R1].data!=tree2[R2].data)
		return false;
	if(tree1[R1].lchild==-1&&tree2[R2].lchild==-1)
		return isomorphic(tree1[R1].rchild,tree2[R2].rchild);
	if(tree1[R1].rchild==-1&&tree2[R2].rchild==-1)
		return isomorphic(tree1[R1].lchild,tree2[R2].lchild);
	if((tree1[R1].lchild!=-1&&tree2[R2].lchild!=-1)
	        &&(tree1[tree1[R1].lchild].data==tree2[tree2[R2].lchild].data))
		return isomorphic(tree1[R1].lchild,tree2[R2].lchild)
		       &&isomorphic(tree1[R1].rchild,tree2[R2].rchild);
}
void display(treenode tree[])
{
	for(int i=0; tree[i].data!='\0'; i++)
	{
		cout<<tree[i].data<<" ";
		cout<<tree[i].lchild<<" ";
		cout<<tree[i].rchild<<endl;
	}
	return;
}
int main()
{
	int root1=buildtree(tree1);
	int root2=buildtree(tree2);
	if(isomorphic(root1,root2))
		cout<<"YES"<<endl;
	else
		cout<<"No"<<endl;
	cout<<"tree1:"<<endl;
	display(tree1);
	cout<<"tree2:"<<endl;
	display(tree2);
	return 0;
}