트리 구현과 순회 - 이론 및 문제 정리

https://www.acmicpc.net/step/23

트리 단계

백준 트리문제에 종만북을 참고하여 정리함.

- tree 일반 개념

• 트리: 계층적인 구조를 표현 - 노드node, 간선edge 으로 구성됨
• depth: root~특정 노드까지의 간선 수 , height: root~leaf노드까지의 간선 수(트리의 높이) 
• 트리의 기본적인 성질: 노드가 N개인 트리는 항상 N-1개의 간선를 가진다
• 트리에서 루트에서 어떤 노드로 가는 경로는 유일하다. 또한 임의의 두 노드 간의 경로도 유일하다.
• 트리의 재귀적 속성에서 중요한 포인트: 모든 트리는 루트와 루트 밑에 있는 서브트리의 집합이다.

struct Node {
	string label; // 저장할 자료
    Node* parent; // 부모 노드를 가리키는 포인터
    vector<Node*> children; // 자손 노드를 가리키는 포인터의 배열
}

 

트리의 노드 표현을 이렇게 할 수 있지만 이렇게 구현하지만 실제 문제풀이 시에 트리를 구현할 때는 보다 간단하게 구현을 함. 

문제에서 노드의 갯수 n값이 주어지고, children의 갯수가 2개인 이진트리 같은 경우에는 left,right노드를 pair로 표기하고 value를 배열의 index를 이용하여 그래프처럼 표현할 수 도 있다.

BOJ 1991 트리순회 에서는  노드의 갯수가 정해져있고, 노드에 저장할 자료가 대문자 알파벳이기 때문에 보다 간단한 구현이 가능해진다

void print(Node* root) { // 트리 순회하며 노드값 출력
	cout << root -> label << endl;
    for(int i = 0; i<root->children.size(); ++i){
    	print(root -> children[i]);
    }
}

int height(Node* root) { // 트리 높이 리턴
	int h = 0;
    for(int i = 0; i< root -> children.size(); ++i){
    	h = max(h, 1 + height(root->children[i]);
    }
    return h;
}

•  모든 트리는 각 자식들을 루트로 하는 서브트리와 루트로 나눌 수 있다. 따라서 트리의 루트가 주어지면 루트를 방문한 뒤에 각 서브트리를 재귀적으로 방문하는 함수를 작성하면 트리의 모든 노드를 순회할 수 있다. (트리 순회)
• 루트의 각 자식들을 루트로 하는 서브트리의 높이를 재귀적으로 구할 수 있다. (노드의 depth, 루트의 depth == 트리의 height)
• 순회방식은 전위 pre-order(root-left-right), 중위 in-order(left-root-right), 후위 post-order(left-right-root)

 

• BOJ 2263 트리의 순회 문제에서 이진트리의 inorder순회 순서와 postorder순회 순서가 주어졌을 때 preorder순회 순서를 해야한다. (이 문제는 preorder, inorder가 주어졌을 때 postorder를 구하는 종만북 TRAVERSAL 문제와 거의 똑같음)