트리: 계층적인 구조를 나타내는 자료구조 (부모-자식)관계






용어:

> 노드 : 트리의 구성요소 (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)를 저장시켜 놓은 트리




이진 탐색 트리: 탐색,삽입,삭제





+ Recent posts