두 갈래 나무의 중순과 후순을 두루 훑어보고, 전순을 두루 훑어보기를 구하다.
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<