[1주차 TIL] KnockOn Bootcamp Pre.Rev : 트리

트리

트리란?

나뭇가지처럼 노드들이 연결된 비선형적이고 계층적인 자료구조이다.

부모노드와 자식노드의 관계로 노드들이 연결되며, 트리구조를 이룬다.

트리의 구조

구분	설명	예시
Node	트리를 구성하는 기본 원소	A,B,C,D,E,F,G,H,I,J
Rootnode	부모가 없는 최상위 루트 노드	A
Leafnode	자식이 없는 노드	H,I,J,F,G
Degree (차수)	하위 트리개수 / 각 노드가 지닌 가지의 수(연결된 자식 노드의 수)	A의 차수 = 2
계수	자식 노드들 중 최대 개수	2
Depth (깊이)	루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수	H 깊이 : 3
Level	특정 깊이를 가지는 노드의 집합	A레벨 : 0
Height	특정 노드에서 가장 멀리있는 리프노드까지의 간선 개수	A 높이 : 3
Size	특정 노드가 자신을 포함한 자손 수	B의 크기 : 6
부모 노드	선조 : 부모노드와 그의 부모들	D,E의 부모노드는 B
자식노드	자식 : 자식 노드와 그 자식들	B의 자식노드는 D,E

트리의 순회방법

• 전위순회 : 노드 → 왼쪽 서브트리 → 오른쪽 서브트리
• 후위순회 : 왼쪽 서브트리 → 오른쪽 서브트리 → 노드
• 중위순회 : 왼쪽 서브트리 → 노드 → 오른쪽 서브트리

위 그림에 따라 각 순회별로 생각하면

• 전위순회 : A → B → D → H → I → E → J → C → F → G
• 후위순회 : H → I → D → J → E → B → F → G → C → A
• 중위순회 : H → D → I → B → E → J → A → F → C → G

이진트리, 완전 이진트리

• 이진트리
  • 트리중에서도 각 노드가 최대 2개의 자식노드를 가질 때 이진트리라고 한다.
  • 최대 2개이기 때문에 자식이 없을 수도, 한개만 있을 수도 있다.
• 완전이진트리
  • 마지막 레벨을 제외한 모든 레벨이 가득 차 있어야 한다.
  • 마지막 레벨의 노드들은 왼쪽에서 오른쪽으로 순서대로 배치된다.
    • 오른쪽에만 노드가 있을 경우 완전 이진트리가 아님
  • 포화 이진 트리는 모든 레벨이 가득 차 있지만, 완전 이진트리는 마지막 레벨이 가득차 있지 않을 수 있다.
  • 단, 마지막 레벨이 가득차지 않더라도, 왼쪽부터 채워져야 한다.
  • 완전 이진트리인경우

        1
      /   \
     2     3
    / \   /
    4   5 6

  • 완전 이진트리가 아닌 경우

          1
        /   \
       2     3
      / \     \
     4   5     6

• 포화이진트리
  • 모든 노드가 2개의 자식을 가지고 Leaf 노드가 모두 같은 레벨일 때의 트리를 말함.
  • 높이가 h일 때, 노드 개수=(2^h)−1

이진 탐색 트리

이진 탐색 트리는 이진트리의 종류로

1. 각 노드는 최대 두개의 자식을 가진다.
2. 왼쪽 서브트리의 모든 노드는 부모노드보다 작아야한다.
3. 오른쪽 서브 트리의 모든 노드는 부모 노드 보다 커야한다.
4. 각 서브트리도 이진 탐색트리다

각 내용을 충족해야 이진 탐색트리이다.

실습

이번 실습 간에는 헤더파일을 이용하여 구조체를 활용하여 트리노드를 구현하고, 각 순회 알고리즘을 만들 것이다.

(추가예정)

끝.