트리와 이진 트리

트리(tree)의 기본 개념

트리는 계층형 자료구조(hierarchical data structure)이다.

하나의 노드는 그 자체로 트리이며 이 노드 또한 이 트리의 루트(root)이다.

 

만일 n이 노드이고 T1, T2, T3, ..., Tk가 트리로서 n1, n2, n3, ..., nk를 각각 루트 노드로 가지고 있다고 할 때 n을 부모로 n1, n2, n3 ..., nk를 연결하면 새로운 트리가 만들어진다.

여기서 n은 루트(root)이고, T1, T2, T3, ..., Tk는 루트 n의 서브 트리(subtree), 노드 n1, n2, n3, ..., nk는 노드 n의 자식들(children)이다.

 

트리 참고 이미지

용어 및 개념 정리

• 노드(node) : 데이터 필드 + 링크 필드
• 노드의 차수(degree)
  
  • 한 노드가 가지고 있는 서브 트리의 수
  • 리프(leaf), 단말 또는 터미널(terminal) 노드
    • C, E, H, I, J, K, L
  • 비단말(nonterminal) 노드
• 노드의 부모 및 자식(parent/children)
  • 자식(children) : 노드 x의 서브 트리의 루트들
  • 부모(parent) : 노드 x를 자식들의 부모라고 부른다.
    • 노드 D의 자식들 : G, H, I
    • D의 부모 : A
• 형제(silblings)
  • 한 부모의 자식들
    • 노드 G, H, I는 형제들
• 트리의 차수(degree of tree)
  • 그 트리에 있는 노드들의 차수 중에 최대 차수
    • 트리 T의 차수 : 3
• 노드의 레벨(level)
  • 루트 : 0
  • 한 노드가 레벨 k에 속하면, 그 자식들은 레벨 k+1에 속한다.

level(v)
	if(v = root) then return 0;
    else return(1 + level(v의 부모));
end level()

 

• 노드의 높이(height)
  • 루트에서 그 노드에 이르는 경로의 길이
  • 루트에서 그 노드에 이르는 간선의 수
• 트리의 높이(height) 또는 깊이(depth)
  • 그 트리의 최대 레벨
    • 트리 T의 높이 : 3
• 노드의 레벨 순서(level order)
  • 트리의 노드들에 레벨 별로 위에서 아래로, 같은 레벨 안에서는 왼편에서 오른편으로 차례대로 순서를 매긴 것.

 

• 포레스트(forest)
  • n ≥ 0개의 분리된 트리의 집합
    • 트리 T에서 루트 A를 제거한 결과를 얻은 포레스트
• 트리를 기술하는 다른 방법
  • 리스트(list) 표현
    • 각 서브 트리를 또 다시 리스트로 표현
      • (A (B (E, F(J, K)), C, D (G (L), H, I)))
    • 메모리 표현(연결 리스트 표현)
      • 노드 A : | 데이터 | 링크 1 | 링크 2 | 링크 3 |
      • 노드 B : | 데이터 | 링크 1 | 링크 2 |

 

이진 트리 - Binary Tree

이진 트리(binary tree : BT) 의 정의

노드의 유한 집합으로서 공백이거나 루트와 두 개의 분리된 이진 트리인 왼쪽 서브 트리(left subtree)와 오른쪽 서브 트리(right subtree)로 구성된다.

 

특징

가장 많이 활용되는 중요한 트리 구조이며 최대 2개의 서브 트리를 갖는다. 

서브 트리는 공백이 될 수 있으며 왼쪽 서브 트리와 오른쪽 서브 트리가 구별된다.

 

이진 트리 예시

위 이진 트리에서 리프 노드(leaf node)는 D, H, F, I이다.

노드 E는 공백 왼쪽 서브 트리와 오른쪽 서브 트리 H를 가지고 있다.

노드 G는 왼쪽 서브 트리 I와 공백 오른쪽 서브 트리를 가지고 있다

 

이진 트리 - 일반 트리와 차이점

이진 트리에는 공백 이진 트리가 있지만, 일반 트레이는 공백 트리가 없다. 또 이진 트리에서는 서브 트리의 순서를 구분하지만 일반 트리에서는 구분하지 않는다.

 

상이한 두 이진 트리

 

이진 트리의 주요 성질로는 

- 레벨 i (i ≥ 0)의 최대 노드 수 : 2^i

- 높이가 h(h ≥ 0)인 이진 트리의 최대 노드 수 : 2^(h+1) - 1

 

 

이진 트리 - 포화 이진 트리(full binary tree)

포화 이진 트리는 높이가 h일 때 노드의 수가 2^(h+1) - 1 인 이진 트리를 말한다.

 

포화 이진 트리 번호(full binary tree number)는 루트 노드를 1번으로 하고 레벨 별로 왼편에서 오른편으로 차례로 노드 위치에 번호를 2^(h+1) - 1 까지 유일하게 부여한 것을 말한다.

 

 

이진 트리 - 완전 이진 트리(complet binary tree)

완전 이진 트리는 높이가 h이고 노드 수가 n인 (n ≤ 2^(h+1) - 1) 이진 트리를 노드의 레벨 순서에 따라서 번호를 붙일 때, 번호들의 각 위치의 높이가 h인 포화 이진 트리 번호 1에서 n까지 모두 일치하는 트리를 말한다.

 

 

 

 

이진 트리 순회

이진 트리에서 각 노드를 빠짐없이 한 번씩 방문하는 체계적인 방법이 3가지 있다.

 

전위 순회(Preorder Traversal)

• 루트 노드(root node)를 방문한다.
• 왼쪽 서브 트리(left subtree)를 전위 순회한다.
• 오른쪽 서브 트리(right subtree)를 전위 순회한다.

중위 순회(Inorder Traversal)

• 왼쪽 서브 트리(left subtree)를 중위 순회한다.
• 루트  노드(root node)를 방문한다.
• 오른쪽 서브 트리(right subtree)를 중위 순회한다.

후위 순회(Postorder Traversal)

• 왼쪽 서브 트리(left subtree)를 후위 순회한다.
• 오른쪽 서브 트리(right subtree)를 후위 순회한다.
• 루트 노드(root node)를 방문한다.

전위, 중위, 후위 순회 경로의 방문 순서