[Data Structure & Alogrithm] Tree

📝Tree

📌 핵심 요약

"트리는 계층적 관계를 표현하는 자료구조이다. 트리는 부모-자식 노드 관계로 재귀적으로 구성된다."

📌 설명

• 노드 : 트리의 구성요소
• 간선(edge) : 노드-노드를 연결하는 연설선
• 루트 노드 : 최상위에 위치하는 부모 노드가 없는 노드
• 단말 노드 : 자식 노드가 없는 노드
• 내부 노드 : 단말 노드를 제외한 모든 노드
• 형제 노드 : 같은 부모 노드를 갖는 노드
• 높이 : 가장 긴 루트 경로의 길이

📝Binary Tree (이진트리)

📌 핵심 요약

"이진 트리는 각 노드가 최대 두 개의 자식 노드를 갖는 트리를 말한다. 이진 트리의 종류에 따라 정(full) 이진트리, 완전(Complete) 이진 트리, 포화(perfect) 이진 트리 등으로 나뉜다."

📌 설명

• Full binary tree (정 이진 트리) : 트리내 노드의 자식수는 0개 또는 2개만 가능한 트리
• Perfect binary tree (포화 이진 트리) : 모든 레벨이 꽉찬 이진 트리
• Complete binary tree (완전 이진 트리) : 노드가 위에서 아래로, 왼쪽에서 오른쪽 순서로 채워진 이진 트리
• Skewed Binary Tree (사향 이진 트리) : 한쪽으로 기울어진 이진 트리

📌 이진 트리의 순회

• 전위 순회(Pre oder traversal) : “현재 노드 -> 왼쪽 가지 -> 오른쪽 가지” 순으로 조회

  

• 중위 순회(Inorder traversal) : “왼쪽 가지 -> 현재 노드 -> 오른쪽 가지” 순으로 조회

• 후위 순회(post order traversal) : “왼쪽 가지 -> 오른쪽 가지 -> 현재 노드” 순으로 조회

🔥 참고

• https://devmjun.github.io/archive/BinaryTree
• https://ddmix.blogspot.com/2016/03/binary-tree-errata.html