트리 자료구조

https://ratsgo.github.io/data%20structure&algorithm/2017/10/21/tree/

트리의 순회

https://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/

Depth First Traversal

Preorder (Root, Left, Right)

전위 순회: 1 2 4 5 3

Inorder (Left, Root, Right)

중위 순회: 4 2 5 1 3

Postorder (Left, Right, Root)

후위 순회: 4 5 2 3 1

Breadth-First (Level Order) Traversal

https://www.geeksforgeeks.org/level-order-tree-traversal/

너비 우선: 1 2 3 4 5

코드로 구현하기

#include <iostream>
using namespace std;

struct Node{
	int data;
	struct Node *left, *right; 
};

// create a new tree node
Node* newNode(int data){
	Node* temp = new Node;
	temp->data = data; 
	temp->left = temp->right = NULL;
	return temp;
}

// root, left, right
void printPreorder(struct Node* node){
	if(node == NULL){
		return;
	}

	// first print data of node 
    cout << node->data << " "; 
  
    // then recur on left subtree
    printPreorder(node->left);
  
    // now recur on right subtree 
    printPreorder(node->right);
}

// left, root, right 
void printInorder(struct Node* node){
	if (node == NULL){
        return;
	}
  
    // first recur on left child 
    printInorder(node->left);
  
    // then print the data of node
    cout << node->data << " ";
  
    // now recur on right child
    printInorder(node->right);
}

// left, right, root
void printPostorder(struct Node* node){
	if(node == NULL){
		return; 
	}

	// first recur on left subtree
    printPostorder(node->left);
  
    // then recur on right subtree
    printPostorder(node->right);
  
    // now deal with the node
    cout << node->data << " ";
}

int main()
{ 
	ios::sync_with_stdio(0);
    cin.tie(0);

	struct Node* root = newNode(1);
	root->left = newNode(2);
	root->right = newNode(3);
	root->left->left = newNode(4);
	root->left->right = newNode(5);

	printPreorder(root);
	cout << "\n";
	printInorder(root);
	cout << "\n";
	printPostorder(root);
	
	return 0;
}

1 2 4 5 3
4 2 5 1 3
4 5 2 3 1

---

문제

https://www.acmicpc.net/problem/2263

중위 순회와 후위 순회의 결과로부터 이진 트리의 root, left, right 구조를 유추하여, 전위 순회의 결과를 출력하는 문제!

풀이

https://donggoolosori.github.io/2020/10/15/boj-2263/

후위 순위의 마지막 원소는 항상 루트 노드이므로, 이를 통해 중위 순회에서의 루트 노드의 위치를 알아낼 수 있다. 그 루트 노드의 위치를 기준으로 left, right 영역을 나눠서 전위 순회 (root, left, right) 를 하면 된다.

#include <iostream>
using namespace std;

int Index[1000001];
int inorder[1000001];
int postorder[1000001];
int n; 

// 중위, 후위 순회의 시작과 끝 인덱스 
void getPreorder(int inStart, int inEnd, int postStart, int postEnd){
	// 더 이상 분할할 수 없으면 재귀 호출 종료 
	if(inStart > inEnd || postStart > postEnd){
		return; 
	}

	// 중위 순회에서 루트 노드의 위치 알아내기 
	int rootIndex = Index[postorder[postEnd]];
	int leftSize = rootIndex - inStart; 
	int rightSize = inEnd - rootIndex;

	// 중위 순회에서 루트 노드의 값 출력 
	cout << inorder[rootIndex] << " "; 

	// recur left : 중위, 후위 순회에서 left 부분의 시작과 끝 인덱스를 바탕으로  
	getPreorder(inStart, rootIndex - 1, postStart, postStart + leftSize - 1); 

	// recur right: 중위, 후위 순회에서 right 부분의 시작과 끝 인덱스를 바탕으로 
	getPreorder(rootIndex + 1, inEnd, postStart + leftSize, postEnd - 1); 
}

int main()
{ 
	ios::sync_with_stdio(0);
    cin.tie(0);

	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> inorder[i]; 

		// 중위 순회의 각 원소에 해당하는 인덱스를 저장해둔다. 
		// 나중에 루트 노드의 인덱스를 알아내기 위해 
		Index[inorder[i]] = i; 
	}

	for(int i = 1; i <= n; i++){
		cin >> postorder[i]; 
	}

	getPreorder(1, n, 1, n);
	
	return 0;
}