[알고리즘] 트리

트리의 정의, 성질

• 무방향, 사이클이 없는 연결 그래프 - Undirected Acyclic Connected Graph
• 임의의 두 점을 잇는 Simple Path(중복 정점이 없는 경로)가 유일한 그래프
• 정점: V개, 간선: V-1개
• 트리의 부분 또한 트리이다.(서브트리) -> 재귀적 특성

구현

그래프와 동일하게 구현이 가능하다.
이진트리의 경우 왼쪽, 오른쪽 자식만을 갖기에 문제에 따라 다음과 같은 구현이 가능하다.

#define MAX 101 //최대 노드의 개수

struct treeNode {
  int lChild, rChild;
};

treeNode tree[MAX];

// tree[a].lChild : a번 노드의 왼쪽 자식

이진트리의 특성을 활용해 배열로 구현할 수도 있는데, 완전이진트리가 아닌 경우 메모리 낭비가 심하지만, 완전이진트리의 경우 편리하다.

int tree[MAX];
// 1번노드가 루트 노드
// tree[a]의 왼쪽 자식노드는 tree[a*2]
//          오른쪽 자식노드는 tree[a*2+1]
// tree[b]의 부모 노드는 tree[b/2]

이진 트리의 순회

재귀적 특성에 따라 전위, 후위, 중위의 재귀적 순회가 존재한다.
그래프와 동일한 DFS, BFS도 물론 가능하다.

• 전위 순회 (preorder)
  루트 - 왼쪽 서브트리 - 오른쪽 서브트리
• 중위 순회 (inorder)
  왼쪽 서브트리 - 루트 - 오른쪽 서브트리
• 후위 순회 (postorder)
  왼쪽 서브트리 - 오른쪽 서브트리 - 루트

구현은 다음과 같다.

#include <iostream>
#define MAX 1000

struct treeNode {
  int lChild, rChild;
};

treeNode tree[MAX];
// 자식이 없는 경우는 -1

// 전위
void preorder(int par) {
  if (par == -1) return;
  cout << par;
  preorder(tree[par].lChild);
  preorder(tree[par].rChild);
}

// 중위
void inorder(int par) {
  if (par == -1) return;
  inorder(tree[par].lChild);
  cout << par;
  inorder(tree[par].rChild);
}

// 후위
void postorder(int par) {
  if (par == -1) return;
  postorder(tree[par].lChild);
  postorder(tree[par].rChild);
  cout << par;
}

추천 문제

11725번: 트리의 부모 찾기

1991번: 트리 순회