1.)트리의 대한 정의: 1개의 root가 존재하며, 루트 노드에서 간선(edge)으로 다른 노드를 연결하여, loop가 허용되지 않는 구조이고, 루트 노드 제거시 t1 t2... tn개의 subtree 의 집합으로 구성됩니다.
2.) 트리의 용어: ROOT NODE - CHILD NODE - PARENT NODE - SIBLING - ANCESTOR -
TERMINAL NODE - LEAF NODE - DEGREE - DEPTH - FOREST - LEVEL
3.) 트리의 종류
1. FULL binary (정이진 트리)
2. complete binary (전 이진 트리)
3. knuth's binary (사항 트리)
4. skwed tree : 한쪽 방향으로 치우친 트리
5. 차수가 k인 k진 트리
4.) 트리의 표현
1. 배열을 이용: 부모 노드에 대한 접근이 용이하며, 정이진 트리인 경우에는 기억장속의 활용도가 높으며 배열을 이용하여 트리를 구현하는 경우에 데이터의 추가와 삭제시 데이터들이 많은 이동이 필요하며 사향트리인 경우 기억장소의 낭비가 심한 단점을 가진다
2. 링크드 리스트를 이용 : n개의 노드를 가진 k진 트리는 nk개의 링크를 가지며, n(k -1)+1개의 null link를 가지며 널링크로 인한 기억장소의 낭비를 발생하므로 k진 트리를 이진트리로 변경하여 사용
5.) 운행(순회)
inorder : left node, root node, right node
preorder : root node, left node, right node
postorder: left node, right node, root node
6.) 산술식의 표현
F= A+(B*C)-D7.) Threaded binary tree
이진 트리에서 사용되지 않는 null링크 부분을 트리의 운행에 사용하는 방법
