알고리즘 자료구조 - 11

10장

1)
트리
 - 데이터 사이의 계층관계를 표현하는 비선형 자료구조
 - 나무와 같은 모양을 가지며, 노드(node)와 가지(edge)를 구성요소로 가진다

 - 루트(root): 트리의 가진 윗부분에 위치한 노드
 - 리프(leaf): 트리의 가진 아랫부분에 위치한 노드(==끝 노드(terminal node), 바깥 노드(external node))
 - 부모(parent): 어떤 노드와 연결된 위쪽노드
 - 자식(child): 어떤 노드와 연결된 아랫쪽노드
 - 형제(sibling): 같은 부모를 가지는 노드들
 - 레벨(level): 루트로부터 떨어져있는 거리
 - 차수(degree): 어떤 노드기준 가지는 자식의 수(거리가 아니다. 자식의 수이다)
                 또한, 트리를 구성하는 각 노드의 자식중 가장 많은 자식을 가지는 노드의 차수를 따와 n진 트리라 한다
 - 높이(height): 루트로부터 가장 멀리 떨아진 리프의 거리(즉, 가장 큰 레벨값과 같다)
 - 서브 트리(subtree): 어떤 노드를 루트로 정하고 그 전체 자손으로 이루어진 트리
 - 널 트리(null tree): 노드, 가지가 없는 트리

 - 순서트리(ordered tree): 형제노드의 순서가 존재하는 트리
 - 무순서트리(unordered tree): 형제노드의 순서를 고려하지 않는 트리
    ex) 같은 구성을 가지고, 형제데이터만 서로 치환된 트리가 있을 경우 해당 트리들은 무순서 트리면서 다른 순서트리이다


2)
순서 트리 탐색방법
 - 너비우선탐색(breath-first search): 낮은 레벨에서 높은 레벨로, 왼쪽에서 오른쪽으로 검색하는 방법
 - 깊이우선탐색(depth-first search): 루트에서 리프까지 내려가면서 검색을 진행하며, 더이상 검색이 불가할시 부모로 올라가 다른 자식을 검색하는 방법

 - 깊이우선탐색시 사용하는 탐색법
    전위순회(preorder): 노드->왼쪽자식->오른쪽자식
    중위순회(inorder): 왼쪽자식->노드->오른쪽자식
    후위순회(postorder): 왼쪽자식->오른쪽자식->노드


3)
이진트리(binary tree)
 - 각 노드의 자식을 2명 이하를 가지는 트리

완전이진트리(complete binary tree)
 - 이진트리 구조에서, 루트로부터 마지막 레벨 이전까지의 레벨은 노드가 채워져 있으면서, 마지막 레벨에서는 왼쪽에서 오른쪽순으로 노드가 채워져있는 트리
 - 높이가 k인 완전이진트리의 노드개수의 최대 값: 2^(k+1)-1
 - n개의 노드를 저장할 수 있는 완전이진트리의 높이: log n

이진검색트리(binary search tree)
 - 아래의 조건을 만족하는 이진트리
   : 트리 내의 어떤 노드 x를 기준으로 왼쪽 서브트리를 이루는 모든 노드의 키 값은 x보다 작아야한다
   : 오른쪽 서브트리를 이루는 모든 키 값은 x보다 큰값을 가진다
   : 같은 키 값을 가지는 노드는 존재하지 않는다

 - 검색은 깊이 우선 탐색 중 중위순회 검색을 수행한다
 - 중위순회 검색을 하는 이진검색트리는 구조가 단순, 이진검색과 비슷하게 검색이 가능, 노드삽입이 쉽다 등등의 장점이 있다

 - 노드 구조체는 데이터, 왼쪽 자식(노드)를 가리키는 포인터, 오른쪽 자식(노드)를 가리키는 포인터로 구성된다
 - 함수구성
    search, add, remove, printtree(노드값을 오름차순으로 출력), freetree

     - 포인터를 계속 옮기지 않고 루트에서 검색하기 때문에 init함수는 필요가 없다
     - add: 이진검색트리의 조건을 맞추어 노드를 추가해야한다
            포인터가 널일경우 해당노드에, 같은값이 존재시 에러, 데이터가 현재 노드값보다 작을시 왼쪽자식으로, 클경우 오른쪽 자식으로 재귀함수 구성
     - printtree: 중위 순회방법으로 트리 검색 및 노드 값 출력
     - freetree: 후위순회 방법으로 트리를 검색하며 노드 메모리 해제