[자료구조] 트리 후위순회 결과와 깊이 순서로 트리 구조 구하기

*자료구조 시간에 문제풀다가 배운 내용을 정리한 것입니다.

 

입력: 후위 순회한 결과와 그 노드의 깊이

출력: 전위 순회한 결과

 

예를 들어 후위 순회한 결과가 다음과 같이 주어 졌을때,

값: 5 2 8 9 10 6 7 3 4 1

깊이: 2 1 3 3 3 2 2 1 1 0

 

출력은 다음과 같다

1 2 5 3 6 8 9 10 7 4

 

트리를 그림으로 그리면 다음과 같다.

트리를 직접 그려보았다.(너무 못그리네..)

 

#솔루션

 

우선 깊이의 개념을 이해해야한다. 깊이는 노드가 루트에서부터의 간선의 개수이다.

그리고 후위 순위는 가장 왼쪽 것부터 그리고 가장 깊이가 깊은 것부터 처리한다.

따라서 깊이의 변화로 이들의 관계가 무엇인지 알 수 있다.

 

우선 노드 1의 자식은 깊이가 1인 녀석들이다. 그래서 입력값으로부터 2 3 4 임을 알 수 있다.

여기서 더 내려가면 2부터 보면 2의 자식은 5밖에 없다. 왜냐하면 2이전에 5가 먼저 나왔고, 다른경우는 없기 때문이다.

3은 그의 자식인 6 7이 이전에 출력되어있다. 이런 규칙은 후위순위에 그 핵심키가 있다.

 

후위순위는 자식먼저 처리 후 자신을 처리한다. 따라서 오른쪽으로 갈수록 깊이가 얕아진다.

항상 그런것은 아니다. 왜냐하면 새로운 가지를 형성할때는 내가 지정한 서브트리의 루트의 깊이와 같거나 얕아지기 때문이다. 하지만 루트는 항상 맨 오른쪽에 나온다.

 

어떤 노드가 출력되기 위해서는 내 자식이 먼저 다 출력 되야한다.

주어진 값으로 자식이 어떤 것인지 알 수 있는 방법은

부모로 특정한 노드부터 시작해서 이전 노드를 하나하나씩 조사해서 나의 깊이보다 같거나 얕지 않으면 전부 자신의 노드의 후손이다. 여기서 바로 자신의 자식, 즉, 자신의 노드보다 1이 깊은 노드가 어디서 부터 시작하는지 파악한다.

그리고 그 지점 부터 하나씩 자신의 노드의 자식으로 등록을 한다. 

이거를 뒤에서부터 하나씩 부모로 특정해서 이 노드를 부모로 했을때 자식이 무엇인지 찾고, 등록을 해나가면 되는 것이다.

 

코드는 다음과 같다.

#include <iostream>
#include <string>
#include <vector>
using namespace std;

class Node {
public:
	int data;
	Node* par;
	vector<Node*> chi_v;
	Node(int e) :data(e) {
		par = NULL;
	}
};

class Tree {
public:
	Node* root;
	vector<Node*> node_v;
	Tree() {
		root = new Node(1);
		node_v.push_back(root);
	}
	void insert(int par, int data) { // 노드삽입
		for (int i = 0; i < node_v.size(); i++) {
			if (node_v[i]->data == par) {
				Node* newNode = new Node(data);
				newNode->par = node_v[i];
				node_v[i]->chi_v.push_back(newNode);
				node_v.push_back(newNode);
			}
		}
	}
	void inorder(Node* v) { //전위순회
		cout << v->data << ' ';
		for (int i = 0; i < v->chi_v.size(); i++) {
			inorder(v->chi_v[i]);
		}
	}
};

int main() {
	int t;
	cin >> t;
	for (int i = 0; i < t; i++) {
		int n,x;
		Tree t; vector<int> data[2];
		cin >> n;
		for (int j = 0; j < n; j++) {
			cin >> x;
			data[0].push_back(x);
		}
		for (int j = 0; j < n; j++) {
			cin >> x;
			data[1].push_back(x);
		}
		for (int par = n - 1; par > 0; par--) { //부모노드 지정
			int start = par; //자식노드의 첫 위치 변수
		
			for (int chi = par - 1; chi >= 0; chi--) { //자식노드 지정
				if (data[1][par] + 1 == data[1][chi]) {
					start = chi; //앞으로 넘어갈수록 자식노드의 첫부분을 갱신
				}
				else if(data[1][par] >= data[1][chi]){ //만약 깊이가 같거나 얕아지면
					break;
				}
			}
			for (int s = start; s < par; s++) { //첫부분부터 조사해서 자식노드 끝까지 등록
				if (data[1][par] + 1 ==  data[1][s]) {
					t.insert(data[0][par], data[0][s]);
				}
				
			}
		}
		t.inorder(t.root);
		cout << '\n';
	}
	return 0;
}