자료구조 - Chapter 08

트리(Tree)

트리

계층적인 관계(Hierarchical Relationship)을 표현하는 자료구조

 

https://gmlwjd9405.github.io/2018/08/12/data-structure-tree.html 님의 자료 트리 표현

• 노드(Node) : 트리의 구성 요서에 해당하는 A, B, C, D...같은 요소
• 간선(Edge) : 노드와 노드를 연결하는 연결선
• 루트 노드(root Node) : 트리 구조에서 최 상위에 존재하는 A와 같은 노드
• 단말 노드(terminal Node) : 아래로 다른 노드가 연결 되어 있지 않은 H, I, J, E, F, G 노드
• 내부 노드(internal Node) : 단말 노드를 제외한 모든 노드

이진트리(Binary tree)와 서브 트리(Sub tree)

 

서브 트리

큰 트리에 속한 작은 트리를 지칭한다.

 

이진 트리

루트 노드를 중심으로 두 개의 서브 트리로 나누어진다.

나뉘어진 두 서브 트리도 모두 이진 트리여야 한다.

 

위 조건 2개를 만족하면 이진트리가 된다. 이진 트리의 존재 자체가 재귀적이기 때문에 이렇게 정의한다.

 

포화 이진 트리(Full Binary tree)와 완전 이진 트리(Complete Binary Tree)

• 레벨 (level) : 트리의 각 층
• 높이(height) : 트리의 최고 레벨

포화 이진 트리

모든 레벨이 꽉 찬 이진트리를 지칭한다.

 

완전 이진트리

포화 이진 트리 처럼 모든 레벨이 꽉 찬 상태는 아니지만 빈 틈없이 노드가 채워진 이진트리

이진 트리의 구현

이진트리와 관련된 일부 연산은 재귀 호출의 형태를 보인다.

또한 아진 트리 역시 배열 기반, 연결 리스트 기반으로 구현이 가능하다.

 

예제 : 연결 리스트로 이진 트리 구현

 

이진트리 구현

BinaryTree.c

0.00MB

BinaryTree.h

0.00MB

ex8-1 BinaryTree.c

0.00MB

예제 : 이진트리 순회

순회 방법

• 전위 순회(Preorder Traversal) : 루트 노드 먼저
• 중위 순회(Inorder Traversal) : 루트 노드 중간
• 후위 순회(Postorder Traversal) : 루트 노드 마지막

이진트리 순회

BinaryTree_v.c

0.00MB

BinaryTree_v.h

0.00MB

ex8-2 TreeTraverse.c

0.00MB

예제 : 트리로 수식 계산

트리 수식 계산

ex8-3 ExpressionTree.c

0.00MB

ExpressionTree.c

0.00MB

ExpressionTree.h

0.00MB