Tree

Tree

Tree의 구성요소

• Node(노드): 트리를 구성하고 있는 각각의 요소
• Edge(간선): 트리에서 노드와 노드 사이를 연결하는 선
• Root Node(루트 노드): 트리 구조에서 최상단에 위치한 노드. 부모가 없는 노드
• Termanal Node(Leaf Node, 단말 노드): 하위에 더이상 다른 노드가 연결되어 있지 않은 노드. 자식이 없는 노드
• Internal Node(내부 노드, 비단말 노드): 단말 노드를 제외한 모든 노드. 루트 노드도 포함.
• 레벨(level, 깊이(depth)): 루트에서 어떤 노드까지의 경로 길이(간선의 수)
• 트리의 높이(height): 트리의 최고 레벨
• 부모 노드: 자신과 연결된 상위 노드
• 자식 노드: 자신과 연결된 하위 노드
• 형제 노드: 같은 부모를 가지는 노드
• 크기(size): 특정 노드가 자신을 포함한 자손의 수
• 노드의 차수(degree): 노드가 가진 자식 노드의 수
• 트리의 차수(degree): 노드의 차수 중 최댓값

트리의 순회 방식

1. 전위 순회
   • 트리에서 루트에서 시작하여 루트 노드 -> 왼쪽 하위 트리 -> 오른쪽 하위 트리 순서로 순회하는 방법
2. 중위 순회
   • 트리에서 루트에서 시작하여 왼쪽 하위 트리 -> 루트 노드 -> 오른쪽 하위 트리 순서로 순회하는 방법
3. 후위 순회
   • 트리에서 루트에서 시작하여 왼쪽 하위 트리 -> 오른쪽 하위 트리 -> 루트 노드 순서로 순회하는 방법
4. 레벨 순회
   • 루트 노드부터 계층별로 방문하는 방법

트리의 종류

1. 이진트리 (Binary tree)
   • 모든 노드의 차수가 2 이하인 트리
2. 포화 이진 트리 (Perfect Binary Tree)
   • 모든 레벨이 꽉 찬 이진 트리
3. 완전 이진 트리 (Complete Binary Tree)
   • 리프 노드를 제외한 모든 노드가 위에서 아래로, 왼쪽부터 오른쪽 순으로 차곡차곡 채워진 이진트리
4. 정 이진 트리 (Full Binary Tree)
   • 모든 노드가 0개 또는 2개의 자식 노드만을 가지고 있는 트리