트리

노드와 노드 사이를 연결하는 엣지를 이용하여 계층을 구성

트리의 계층 구조를 화면에 도식적으로 나타내려면 말 그대로 나무 형태로 나타낼 수 있으며,

엣지는 나뭇가지처럼 표현

트리의 중심이 되는 노드를 루트 노드, 보통 가장 맨 위에 나타난다.

트리 구조를 그림으로 나타낼 때는 실제 나무와는 반대로 뿌리가 맨 위에 나타나는 상하 반전된 형태

 

한개의 노드가 두 개의 노드를 가지고 있는 게 이진 트리

각각의 노드는 다른 두 개의 노드(하위 노드)에 대한 링크를 가진다.

데이터의 계층 구조를 나타낼 수 있다.

노드에 원하는 형태로 확장할 수 있다.

 

특정 원소를 찾기 위해 트리를 탐색할 때, 해당 원소는 현재 노드이거나 왼쪽 또는 오른쪽 서브 트리에 있다.

가장 먼저 루트 노드를 검사하고, 만약 찾고자 하는 원소가 아니라면 왼쪽 서브 트리에서 다시 찾으려고 시도,

그래도 해당 원소를 찾지 못하면 오른쪽 서브 트리도 검사.

 

트리 순회

 

전위 순회(preorder traversal) : 현재 노드를 먼저 방문하고, 그 다음은 현재 노드의 왼쪽 하위 노드를, 마지막으로는 현재 노드의 오른쪽 하위 노드를 재귀적인 방식으로 방문 전위(pre)는 상위 노드를 하위 노드보다 먼저 방문한다는 뜻( 2 1 3 )

전위 순회는 항상 부모 노드를 방문한 다음 왼쪽 자식 노드, 오른쪽 자식 노드를 차례로 방문, 이러한 방식의 순회를 루트 노드에서만 수행하는 것이 아니라 루트 노드 아래의 모든 서브 트리에 대해 적용

 

중위 순회(in-order traversal) : 왼쪽 노드를 먼저 방문, 그 다음에는 현재 노드, 마지막으로 오른쪽 노드를 방문( 1 2 3 )

 

후위 순회(post-order traversal) : 후위 순회 방법은 두 자식 노드를 먼저 방문한 후, 현재 노드를 방문 ( 1 3 2 )

 

레벨 순서 순회(level order traversal) :  트리의 맨 위 레벨 부터 아래 레벨까지, 왼쪽 노드에서 오른쪽 노드 순서로 방문, 트리의 루트 노드부터 단계별로 차례대로 나열하는 것과 같다. ( 구현할 때 큐를 이용해서 구현하는 것이 편하다. )