[자료구조 & 알고리즘] 6. 트리, 이진 트리, 트리 순회, BFS, DFS
트리, 이진 트리, 트리 순회, BFS, DFS1. 트리 (Tree)• 서로 연결된 Node의 계층형 자료구조로써, Root와 부모-자식 관계의 Subtree로 구성.• 관련 용어 정리 - 노드 (Node) : 트리를 구성하는 기본 원소 - 간선 (Edge) : 노드 간에 연결된 선 - 루프 노드 (Root) : 트리는 항상 루트에서 시작. 가장 위에 있는 노드. - 리프 노드 (Leaf) : 더 이상 뻗어나갈 수 없는 마지막 노드 - 자식 노드 (Child), 부모 노드 (Parent), 형제 노드 (Sibling) - 차수 (Degree) : 각 노드가 갖는 자식의 수. 모든 노드의 차수가 n개 이하인 트리를 n진 트리라고 함. - 조상 (Ancest..
재귀 (Recursion)1. 재귀 함수• 자신을 정의할 때 자기 자신을 재참조하는 함수를 재귀 함수라고 함.public int factorial(int i) { if(i == 1) return 1; return i * factorial(i-1);}public int fibonacci(int i) { if(i == 1 || i == 2) return 1; return fibonacci(i-1) + fibonacci(i-2);}• 재귀의 구성 요소 - 점화식(Recurrence Relation) : f(n)을 f(n-1), f(n-2), ..., f(2), f(1)의 관계식으로 표현하는 것 - 탈출 조건(Base Case) - 더 이상 재귀 호출을 하지 않아도 값을 반환할 수..