트리: 계층적인 구조를 나타내는 자료구조 (부모-자식)관계
용어:
> 노드 : 트리의 구성요소 (A ~ J)
> 루트 : 부모가 없는 노드 (A)
> 서브트리 : 하나의 노드와 그 노드들의 자손들로 이루어진 트리 (B,E,F,G) (C,H) (D,I,J)
> 단말노드 : 자식이없는 노드 (E~J)
> 비단말노드 : 적어도 하나의 자신을 가지는 노드 (B,C,D)
> 자식,부모,형제,조상,자손
조상노드 - 루트노드에서 임의의 노드까지의 경로를 이루고 있는 노드들을 뜻함
자손노드 - 임의의 노드 하위에 연결된 모드 노드들을 말한다.
> 레벨 : 트리의 각 층의 번호 (루트(A)=1, B,C,D=2, E~J=3)
> 높이 : 트리의 최대 레벨 (3)
> 차수 : 노드가 가지고 있는 자식 노드의 개수 (B=3, C=1, D=2)
이진트리 : 모든 노드가 최대 2개의 서브트리를 가질 수 있는 트리, 각 노드에는 최대 2개까지의 자식 노드가 존재
특성:
> 노드의 개수가 n이면 간선의 개수는 n-1이다.
> 높이가 h이면, 최소 h개의 노드를 가지며, 최대 2^h-1개의 노드를 가진다.
> 노드의 개수가 n개이면 이진트리의 높이는 최대n이거나 최소 log2(n+1)이 된다.
표현:
> 배열로 구현 : 포화이진트리로 가정하고 각 노드에 번호를 붙여 배열의 인덱스에 저장
> 연결리스트로 구현 : 포인터를 이용해 부모노드가 자식노드를 가리키게 한다.
순회:
> 전위순회 (preorder) -> 자손보다 루트노드를 먼저 방문한다.
<부모노드 처리후 자식노드를 처리해야 하는 경우>
> 중위순회 (inorder) -> 왼쪽 자손, 루트 , 오른쪽 자손 순으로 방문한다.
> 후위순회 (postorder) -> 루트보다 자손을 먼저 방문한다.
<자식노드 처리후 부모노드를 처리해야 하는 경우>
노드개수, 높이 구하기
> 노드개수 구하기 : 루트(1) + 왼쪽(순환) + 오른쪽(순환)
> 높이 구하기 : 루트(1) + MAX(왼쪽(순환) VS 오른쪽(순환))
수식트리 : 후위순회를 사용, 서브트리의 값을 순환호출로 계산
스레드 이진 트리: NULL링크에 중위 순회시에 후속 노드인 중위 후속자(inorder successor)를 저장시켜 놓은 트리
이진 탐색 트리: 탐색,삽입,삭제