[자료구조] 트리

트리의 개념
트리(Tree): 노드(node) 또는 정점(vertex)으로 구성된 논리적인 계층 구조. 데이터 간의 계층 관계와 포함 관계를 나타내는 자료구조.
루트(Root): 부모를 갖지 않는 노드.
노드(Node): 트리를 구성하는 항목.
내부 노드(Internal Node): 루트도 잎도 아닌 노드.
잎(Leaf): 자식이 없는 노드.
형제(Sibling): 같은 부모를 갖는 노드들.

트리의 용어
차수(Degree):

진입 차수(In-degree): 특정 노드로 들어오는 선의 개수.
진출 차수(Out-degree): 특정 노드에서 나가는 선의 개수.
노드의 차수: 진출 차수로 정의.
트리의 차수: 트리 내의 각 노드의 차수 중 최대 차수.
레벨(Level): 루트로부터 특정 노드까지 이어진 경로의 길이.

이진 트리
이진 트리(Binary Tree): 모든 노드의 차수가 2 이하인 트리.
가득 찬 이진 트리(Perfect Binary Tree): 각 레벨이 허용되는 최대 개수의 노드를 가질 때의 이진 트리.
완전 이진 트리(Complete Binary Tree): 높이가 k인 이진 트리가 레벨 0부터 k-2까지 모두 채우고, 마지막 k-1 레벨에서 왼쪽부터 오른쪽으로 노드가 채워진 경우.

 

트리의 순회
순회(Traversal): 트리의 각 노드를 한 번씩 방문하는 과정.
전위 순회(Preorder Traversal): 루트를 먼저 방문한 후 왼쪽 서브트리, 오른쪽 서브트리를 순회.
중위 순회(Inorder Traversal): 왼쪽 서브트리를 먼저 방문한 후 루트를 방문하고, 오른쪽 서브트리를 순회.
후위 순회(Postorder Traversal): 왼쪽 서브트리, 오른쪽 서브트리를 먼저 방문한 후 루트를 방문.

 

학습 목표
트리의 용어와 표현 방법 이해.
트리의 추상 자료형 이해.
이진 트리의 개념과 구현 방법 이해.
이진 트리의 순회 연산 및 생성, 삽입, 삭제 연산 이해.
이와 같은 내용을 바탕으로 트리에 대한 이해를 깊이 있게 할 수 있습니다.