두 갈래 나무의 중순과 후순을 두루 훑어보고, 전순을 두루 훑어보기를 구하다.

1166 단어 물문제
먼저 두 갈래 트리를 구축한 후 중순으로 훑어보다
1. 뒷 순서의 마지막 노드는 두 갈래 나무의 뿌리 노드, 즉 앞의 순서가 흐르는 첫 번째 노드이다. 중간 순서가 흐르는 위치를 찾아 글자 수와 오른쪽 하위 트리 두 부분으로 나뉜다. A/\CBH DE
2. 왼쪽 트리의 노드가 뒤의 루트에서 가장 오른쪽에 있는 노드는 현재 루트 노드이며, 중간 루트에서 위치를 찾습니다. 이와 같이 왼쪽 트리와 오른쪽 트리를 각각 찾습니다.
A/\B D/\C H E 이전 순서 반복 결과: ABCHDE
#include 
#include 
using namespace std;

typedef struct no
{
	char data;
	struct no *lchild,*rchild;
}*node;
void create(node &sa,string in,string post)
{
	if(in.length()==0)
		return;
	sa=new no();
	sa->data=post[post.length()-1];// 
	sa->lchild=sa->rchild=NULL;
	string inl,inr,postl,postr;
	int i=in.find(post[post.length()-1]);
	inl=in.substr(0,i);
	inr=in.substr(i+1,in.length());
	postl=post.substr(0,inl.length());
	postr=post.substr(inl.length(),inr.length());
	create(sa->lchild,inl,postl);
	create(sa->rchild,inr,postr);
}

void pre(node &sa)
{
	if(sa!=NULL)
	{
		cout<data;
		pre(sa->lchild);
		pre(sa->rchild);
	}
}
int main()
{
	string inorder,postorder;
	cout<>inorder;
	cout<>postorder;
	node head=new no();
	create(head,inorder,postorder);
	cout<

좋은 웹페이지 즐겨찾기