🥕조건 05 Sub Tree : 주어진 노드의 모든 하위 목록 (그 계층을 삼각형 틀로 보면 됨. ex. 나, 금쪽이, 우리 아빠)
🥕조건 06 (중요도🌟🌟🌟) 🌟degree of a node : 특정 노드가 가지고 있는 자식 노드의 수 (주의, 자식과 자손은 다름. 자손은 포함하지 않음) 🌟degree of a tree : 가장 높은 차수를 가진 노드의 차수(즉, 특정 노드가 가지고 있는 자식 노드의 수가 가장 많은 차수를 말함)
🥕조건 07 (중요도 🌟 🌟🌟) Depth : 노드에서 루트까지의 edge 수 Height : 루트 노드와 가장 먼 leaf 사이의 edge 수 Level : depth + 1
depth of a node : root -> each node의 edge의 수(나뭇가지의 수) 🌟depth of a tree(height) : root -> 가장 깊은 node까지의 edge 수 width of a tree : 각 계층에서 node의 최대 node 수
🌲 Tree의 종류
🍃 Binary Tree(이진 트리)
🍃 Non-Binary Tree
🌲 이진 트리
🍃최대 자식의 수가 2임 🍃차수가 2임
🔸이진 트리 특징(중요도🌟🌟🌟)
i번째 레벨의 최대 노드 수 : 2^(i-1) (각 계층의 2의 제곱임) 깊이가 k인 이진 트리의 최대 노드 수 : 2^k - 1
🔸이진 트리의 종류
🌲포화 이진 트리 - 모든 노드가 0개 또는 2개의 자식 노드 - 모든 내부 모드는 두개의 자식 노드를 가져야함 - 모든 리프 노드는 동일한 깊이에 있어야함 - 모든 레벨의 노드가 모두 차있는 트리 - 노드의 수 = 2^depth - 1
🌲완전 이진 트리 - 마지막 레벨을 제외한 모든 레벨이 완전히 채워져있고 - 마지막 레벨의 노드들은 왼쪽에서 오른쪽으로 채워진 트리 (레프트차일드랑 라이트차일드가 다 있어야 됨. 라이트차일드만 있으면 완전 이진트리가 아님)
🌲트리의 순회 Search == Traversal (탐색 == 순회) - 어떠한 값이 주어졌을 때 해당 값이 일치하는 노드가 있는지 보는 것 - 즉 모든 노드를 봐야함
🔸순회방법
🍎Depth-first search (DFS) (깊이 우선 탐색)
- 계층 순서대로 탐색 (할아버지 - 아버지 - 나)
- 트리의 한 경로를 끝까지 탐색한 후 다른 경로를 탐색하는 방법
- 스택, 재귀 이용하여 구현함
▼이진트리는 특히 세가지 방법으로 구현할 수 있음▼
🥕 Preorder Traversal (전위순회) (A - B - C) (루트 -> 왼쪽 -> 오른쪽) 👉A B D H I E C F G 🥕 Inorder Traversal (중위순회) (B - A - C) 왼쪽 -> 루트 -> 오른쪽 👉H D I B E A F C G 🥕 Postorder Traversal (후위순회) (B - C - A) 왼쪽 -> 오른쪽-> 루트 👉H I D E B F G C C A
💡전위, 중위, 후위가 헷갈리다면? >>> "루트"에 집중할 것! - 전위는 루트 > 왼쪽 > 오른쪽 - 중위는 왼쪽 > 루트 > 오른쪽 - 후위는 왼쪽 > 오른쪽 > 루트
