제6장. 자료구조 트리

1. 트리

1) 트리는 계층구조를 표현할때 사용하는 자료구조이다.

2) 노드와, 노드와 노드를 연결한 링크(link)로 구성되어 있다.

3) 가장 위에 있는 노드를 root node라고 하고 가장 아래에 있는 노드를 단말노드(terminal node) 또는 leaf node라고 한다.

4) parent node 부모 노드는 어느 노드 위에 있는 노드를, child node 자식 노드는 어느 노드 아래의 노드를 말하고 '학과 노드의 부모 노드는 대학노드이다' 이런 식으로 말한다.

5) sibling node 형제 노드는 같은 부모 노드를 가진 노드들을 말한다.

 

6) subtree서브 트리는 트리 아래에 있는 트리를 말한다.

 

7) level 레벨은 루트 노드에서 임의의 노드까지 방문한 노드의 수를 말한다.

8) depth깊이는 트리의 최대 레벨을 말한다. 아래의 그림에서 깊이는 4이다.

2. 이진 트리

1) 이진 트리는 모든 노드들의 자식 노드가 두 개 이하인 트리를 말한다.

2) 왼쪽 서브 트리와 오른쪽 서브 트리로 구분되어 있다.

 

 

2.1 완전 이진 트리

1) 이진트리 중에서 단말노드를 제외한 모든 노드가 두개의 자식노드를 가지고 있으며 단말노드는 왼쪽부터 채워져 있는 트리를 완전 이진 트리라고 한다.

O)

 

X)

2.2 포화 이진 트리

1) 포화 이진 트리는 완전 이진 트리 중에서 모든 노드가 채워진 이진 트리이다.

2) 모든 노드가 채워져 있기 때문에 리프 노드가 아닌 노드들은 모두 2개의 자식을 가지고, 모든 리프 노드의 레벨이 동일하다.

3) 포화 이진 트리는 완전이진 트리이다.

포화 이진 트리 ⊂ 완전 이진 트리 ⊂ 이진  트리

3. 이진 트리의 표현, 구현

1) 이진 트리는 배열이나 연결리스트를 이용해서 구현할 수 있으나 주로 연결 리스트를 이용해서 표현한다.

2) 이진 트리의 모든 노드를 특정한 순서대로 한번씩 방문하는 것을 순회라고 한다.

3) 전위 순회 : preorder traverser

전위 순회는­루트 노드를 먼저 방문하고 왼쪽 서브 트리, 오른쪽 서브 트리 순으로 방문

4) 중위순회 : inorder traverser

: 루트 노드 중간을 방문

5) 후위 순회 : postorder traverser

 

4. 이진 탐색 트리에 데이터 삽입과 삭제

binary search tree 이진 탐색 트리는 이진 트리 중에서 같은 데이터를 갖는 노드가 없으며,

­왼쪽 서브 트리에 있는 모든 데이터가 현재 노드의 데이터보다 작고,

­오른쪽 서브 트리에 있는 모든 데이터가 현재 노드의 데이터보다 큰 트리

 

3 2 6 5 < 7 < 11 8 15

 

삽입)

11보다 작다 --> 왼쪽,              8보다  크다 --> 오른쪽

삭제)

밑의 노드 이동 필요