이미 알고 있는 두 갈래 나무의 두 가지 반복 시퀀스 출력은 다른 반복 시퀀스를 구합니다

이미 알고 있는 두 갈래 트리의 후순과 중순 시퀀스 출력 전순 시퀀스 (선순)

분석: 뒷순서 서열의 마지막 부분은 항상 뿌리 결점이다. 중순서 서열에서 이 뿌리 결점을 찾으면 중순서 서열을 두 부분으로 분할할 수 있다. 왼쪽은 왼쪽 트리, 오른쪽은 오른쪽 트리이다.선행자 시퀀스의 출력 순서는 루트 > 왼쪽 트리 > 오른쪽 트리입니다.만약에 뒷순서 서열이post[]수조에 저장되고 중순서 서열은 in[]수조에 저장된다면postL과postR은 뒷순서 서열의 왼쪽 색인과 오른쪽 색인이고 inL과 inR은 각각 중순서 서열의 왼쪽 색인과 오른쪽 색인이다.두 갈래 나무의 뿌리는post[postR]이기 때문에 중차 서열을 훑어보고 뿌리 결점의 값과 같은 인덱스를 찾으면 중차 서열을 좌우 서브트리 두 부분으로 분할할 수 있습니다.변수 k로 중차 서열의 뿌리를 표시하는 인덱스는 왼쪽 트리의 결점수는numLeft=k-inL이기 때문에 왼쪽 트리의 후차 서열 시작 인덱스는 [postL,postL+numLeft-1], 왼쪽 트리의 중차 서열 시작 인덱스는 [inL,inL+numLeft-1], 오른쪽 트리의 후차 서열 시작 인덱스는 [postL+numLeft,postR-1], 오른쪽 트리의 중차 서열 시작 인덱스는 [inL+numLeft+1,inR]이다.그래서 뿌리 결점을 얻은 후에 출력하고 같은 방법으로 왼쪽 나무의 뿌리 결점을 훑어보고 출력하며 오른쪽 나무의 뿌리 결점을 훑어보고 출력한다. 먼저 훑어보는 과정을 모의하면 나무를 만드는 과정을 줄일 수 있다.
코드:

void pre(int postL,int postR,int inL,int inR){
	if(postL > postR) return ;
	int rootData = post[postR]; // data 
	printf("%d ",rootData);
	int k;
	for(int i=inL;i<=inR;i++){
		if(in[i] == rootData){
			k = i;
			break;
		}
	}
	int numLeft = k-inL;
	pre(postL,postL+numLeft-1,inL,inL+numLeft-1);
	pre(postL+numLeft,postR-1,inL+numLeft+1,inR);
}

테스트 용례:
입력:

후서: 2 3 1 5 7 6 4

중서: 1, 2, 3, 4, 5, 6, 7

출력:

전서: 41 3 2 6 57

이미 알고 있는 두 갈래 트리의 전순과 중순 시퀀스 출력 후순 시퀀스 (트리 만들기)

분석: 앞 서열의 첫 번째 부분은 항상 루트 결점이다. 중간 서열에서 이 루트 결점을 찾으면 중간 서열을 두 부분으로 분할할 수 있다. 왼쪽은 왼쪽 트리, 오른쪽은 오른쪽 트리이다.뒷순서 시퀀스의 출력 순서는 왼쪽 트리 > 오른쪽 트리 > 루트입니다.만약에 선순 서열이pre[] 그룹에 저장되고 중순 서열은 in[] 그룹에 저장된다면preL과preR은 각각 후순 서열의 왼쪽 색인과 오른쪽 색인이고 inL과 inR은 각각 중순 서열의 왼쪽 색인과 오른쪽 색인이다.두 갈래 나무의 뿌리는pre[prerR]이기 때문에 중차 서열을 훑어보고 뿌리 결점의 값과 같은 인덱스를 찾으면 중차 서열을 좌우 서브트리 두 부분으로 분할할 수 있습니다.변수 k로 중차 서열의 뿌리를 표시하는 인덱스는 왼쪽 트리의 결점수는numLeft=k-inL이기 때문에 왼쪽 트리의 선차 서열 시작 인덱스는 [preL+1,preL+numLeft], 왼쪽 트리의 중차 서열 시작 인덱스는 [inL,inL+numLeft-1], 오른쪽 트리의 선차 서열 시작 인덱스는 [preL+numLef+1,preR], 오른쪽 트리의 중차 서열 시작 인덱스는 [inL+numLeft+1,inR]이다.그래서 뿌리 결점을 얻은 후에 뒤에 왼쪽 트리를 훑어보고 뒤에 오른쪽 트리를 훑어보고 마지막으로 뿌리 결점의 값을 출력하여 뒤에 있는 과정을 모의하면 나무를 만드는 과정을 줄일 수 있다.
코드(없음):

void post(int preL,int preR,int inL,int inR){
	if(inL>inR) return;
	int rootData = pre[preL]; // data 
	int k;
	for(int i=inL;i<=inR;i++){
		if(in[i] == rootData){
			k = i;
			break;
		}
	}
	int numLeft = k-inL;
	post(preL+1,preL+numLeft,inL,inL+numLeft-1);
	post(preL+numLeft+1,preR,inL+numLeft+1,inR);
	printf("%d ",rootData);
}

코드(작성):

node* post(int preL,int preR,int inL,int inR){
	if(inL>inR) return NULL;
	int rootData = pre[preL]; // data 
	int k;
	node* root = new node;
	root->data = rootData;
	for(int i=inL;i<=inR;i++){
		if(in[i] == rootData){
			k = i;
			break;
		}
	}
	int numLeft = k-inL;
	root->lchild = post(preL+1,preL+numLeft,inL,inL+numLeft-1);
	root->rchild = post(preL+numLeft+1,preR,inL+numLeft+1,inR);
	printf("%d ",rootData);
	return root;
}