정처기 필기 ] 트리 정리.

트리 이미지

 

1.트리의 차수와 단말 노드

※ 차수(Degree) : 전체 트리에서 가장 큰 차수.

※ 단말노드(Terminal node) : 자식이 없는 노드.

 

아래 '트리 이미지'에서 트리의 차수와 단말 노드의 수는 어떻게 될까?

 

① 차수는 A,B 각각 2개씩 가지고 있기 때문에 2개이다.

② 단말 노도의 수는 D,E,C 3개이다.

2. 트리 순회의 종류.

※ 트리 순회의 종류.

 ① 전위 순회 : 루트노트에서부터 찾는다. (Root → Left → Right)

 ② 중위 순회 : 좌측 하위노드부터 방문한 뒤 루트 노드를 찾는다. (Left → Root → Right)

 ③ 후위 순회 : 하위노드를 찾은 후 루트 노드를 찾는다. (Left → Right → Root)

 

그렇다면 '트리 이미지'에서 각각의 순회들이 노드를 찾은 순서는 어떻게 될까?

 

① 전위 순회 : ABDEC

② 중위 순회 : DBEAC

③ 후위 순회 : DEBCA