(2) 이 진 트 리 의 복원 과 옮 겨 다 니 기

이 진 트 리 의 역 사 는 선 서, 중 서, 후 서 를 세 가지 로 옮 겨 다 니 며 중 서 와 다른 하 나 를 알 면 완전 하고 유일한 이 진 트 리 를 얻 을 수 있 습 니 다.
본 고 는 재 귀적 인 방법 을 통 해 선서 와 중 서 서열 을 통 해 원래 의 이 진 트 리 를 얻 었 다.
환원 의 원 리 는 매우 간단 하 다. 우선 서열 의 모든 결점 은 뿌리 결점 으로 볼 수 있 고 뿌리, 왼쪽, 오른쪽 순서 이다. 반면에 중 서열 이 옮 겨 다 니 는 순 서 는 왼쪽, 뿌리, 오른쪽 이기 때문에 선 서열 에 따라 중 서열 의 뿌리 결점 을 찾 을 수 있 고 이 뿌리 결점 왼쪽 은 왼쪽 나무 이 고 오른쪽 은 오른쪽 나무 이다.
그 다음 에 현재 뿌리 노드 에 따라 왼쪽으로 재 귀 하여 왼쪽 서브 트 리 를 만 들 고 오른쪽으로 재 귀 하여 오른쪽 서브 트 리 를 생 성 할 수 있 습 니 다. 재 귀 할 때의 범 위 를 주의 하 십시오. 예 를 들 어 왼쪽으로 재 귀 하 는 것 은 서열 의 0 번 위치 에서 현재 뿌리 노드 위치의 왼쪽 이 어야 합 니 다. 색인 은 0 에서 시작 되 기 때문에 뿌리 노드 의 번 호 는 바로 옮 겨 다 니 는 요소 갯 수 입 니 다.
오른쪽으로 옮 겨 다 닐 때 먼저 순서 서열 에서 왼쪽 하위 트 리 로 돌아 갈 때 이미 사용 한 요 소 를 제거 해 야 합 니 다. 먼저 순 서 는 뿌리, 왼쪽, 오른쪽 순서 이기 때문에 포 지 셔 닝 뿌리 결점 에서 뒤로 i 번 (i 는 뿌리 결점 이 중간 순서 서열 에서 의 색인, 즉 재 귀적 으로 해결 해 야 할 요소 개수) 을 제거 한 후에 먼저 순서 서열 에서 뿌리 결점 뒤의 i 개 점 을 제거 해 야 합 니 다.여기 서부 터 가 져 온 것 이 야 말로 오른쪽 나무의 결점 이다.
위의 규칙 에 따라 옮 겨 다 니 는 길 이 를 계산 합 니 다. 길이 = 0 일 때 현재 요 소 는 0 의 결점 이 고 재 귀 되 는 것 을 설명 합 니 다.
구체 적 인 코드 는 다음 과 같다.

#include <iostream>
#include <stdio.h>
using namespace std;

#define MAXSIZE 50

typedef struct TreeNode *BinTree;
struct TreeNode{
	char data;
	BinTree left;
	BinTree right;
};

/*
	@param
	pre     
	med     
	len     
*/	
BinTree createBinTree(char *pre, char *med, int len){

	if (len == 0)
	{
		//      0          ，    
		return NULL;
	}

	BinTree T = (BinTree)malloc(sizeof(struct TreeNode));
	int i; //             ，               （   ）。

	T->data = *pre; //            
	for (i = 0; i < len; i++) {
		if (*pre == *(med + i)) break; //            
	}

	//      ，pre               ，                （   ），    i       
	//           ，  len  i。
	T->left = createBinTree(pre + 1, med, i);

	//      ，             pre        i   ，      i   ，     ，  i+1   ， 
	//                               ，       i    len  ，         len-i-1。
	T->right = createBinTree(pre + i + 1, med + i + 1, len - i - 1);
	
	return T;

}

void prePrint(BinTree T){

	if (T != NULL){
		printf("%c", T->data);
	}
	else{
		return;
	}

	prePrint(T->left);
	prePrint(T->right);

}

void medPrint(BinTree T){

	if (T == NULL) return;                                                                                                                                                                                                                                                            

	medPrint(T->left);
	printf("%c", T->data);
	medPrint(T->right);

}

void postPrint(BinTree T){

	if (T == NULL) return;

	postPrint(T->left);
	postPrint(T->right);
	printf("%c", T->data);
}

/*
    
9
ABDFGHIEC
FDHGIBEAC
*/

int main(){

	int N = 0;
	char pre[MAXSIZE], med[MAXSIZE];
	BinTree T = NULL;

	scanf("%d", &N);

	scanf("%s 
 %s", pre, med);

	T = createBinTree(pre, med, N);

	prePrint(T);
	cout << endl;
	medPrint(T);
	cout << endl;
	postPrint(T);
	cout << endl;

	return 0;
}