트리순회(Tree Traversal) 전위, 중위, 후위, 레벨순회

[트리순회는 재귀호출로 이해될 수 있다]

트리순회(Tree Traversal)

1. Pre-order Traversal

2. In-order Traversal

3. Post-order Traversal

4. Level-order Traversal

의 순회 방법들이 있는데 이러한 순회 방법이 있는 이유는

트리는 선형이 아닌 비선혀이기 때문에 모드 노드들을 거쳐가기 위한 방법이 필요하게 된다

그리하여 위와 같은 순회 방법이 나오게 되었다

( 반례 : list 의 경우 선형이기 때문에 특별한 노드를 거쳐가는 방법을 필요로 하진 않는다)

sub 트리 : 트리의 부분 집합 참고 : http://www.cyworld.com/sjh0628/6850615

서브트리는 자식을 하나라도 가지고 있는 노드가 있다면 그 노드를 중심으로 서브트라 볼 수 있다

전위순회 (Pre-order)

Pre-Order Traversal

1. Root 를 방문한다

2. 왼쪽 subtree를 방문한다

3. 오른쪽 subtree 를 방문한다

특징 : 루트가 가장 먼저 나온다

노드를 먼저 들린다, 그래서 Pre

PreOrderTraversal( Node* pNode ){

if( pNode != m_pNodeTail )

{

visit(pNode); // 해당 노드에서 왼쪽, 또는 오른쪽으로 갈지를 정하기 전에 해당 노드를 들린다

PreOrderTraversal(pNode->pLeft );

PreOrderTraversal(pNode->pRight );

}

}

tip : 노드와 처음 마주칠때 방문한다

중위순회 (in-order)

1. 왼쪽 Subtree 를 방문한다

2. Root 를 방문한다.

3. 오른쪽

특징 : 가장 왼쪽노드가 먼저 나온다

노드를 중간에 들린다, 그래서 In

InOrderTraversal( Node* pNode ){

if( pNode != m_pNodeTail )

{

InOrderTraversal(pNode->pLeft );

visit(pNode); // 왼쪽 먼저 트리를 찾아 갔다가 왼쪽이 없으면 방문하고 오른쪽을 가기 때문에 중위 순회

InOrderTraversal(pNode->pRight );

}

}

tip : 왼쪽으로 갔다가(왼쪽 끝까지 갔다가) 다시 올라올때 방문한다

후위순회 (post-order)

1. 왼쪽 subtree 를 방문한다.

2. 오른쪽 subtree 를 방문한다.

3. root 를 방문한다

특징

1. 가장 온쪽 노드가 첫번째 나온다

2.루트가 가장 나중에 나온다

노드를 마지막에 들린다, 그래서 Post

PostOrderTraversal( Node* pNode ){

if( pNode != m_pNodeTail )

{

PostOrderTraversal(pNode->pLeft );

PostOrderTraversal(pNode->pRight );

visit(pNode); // 왼쪽, 오른쪽 다 들린 후 마지막에 올라올때 들린다

}

}

tip : 현재 노드에서 오른쪽으로 갔다가 오른쪽 끝까지 간 후 다시 올라올때 방문한다

레벨순회 (Level-order)

특징 : 루트가 가장 먼저 나온다

큐를 이용

PreOrderTraversal( Node* pNode ){

ListQueue<Node*> queue;

queue.Put(pNode);

while( !queue.IsEmpty() ) // iteration

{

pNode = queue.Get();

if( pNode != m_pNodeTail )

{

visit(pNode);

queue.Put(pNode->pLeft );

queue.Put(pNode->pRight );

}

}

}

정리하면 A 에 딸려 있는 바로 아래 자식들을 큐에 순서대로 추가 한다( A를 큐에서 제거 후 B,C 추가)

순서적으로 B,C 의 순이니 추가된 B를 제거 후 B 의 바로 한칸 아래 자식들을 다시 큐에 추가 하면

C , D, E 의 순이 된다

그러면 다시 C 에 대한 자식 F 를 큐에 추가 하고 C 를 제거(즉 앞에 있는 것을 제거 하면

트리 각 레벨에서 왼쪽에서 오른쪽의 순으로 큐 뒤에 추가 하는 것이 된다

즉 큐에서 제거 되는 노드의 자식들을 큐 뒤에 추가 함으로써 위에서 아래로, 왼쪽에서 오른쪽으로의 노드를 순회 할 수 있게 된다

tip : 큐의 가장 처음 즉 queue.Get() 할때의 노드를 제거 하면서 제거되는 노드들의 자식(2개 또는 1개) 을 큐의 뒤에 추가해준다

자식을 추가 하기 전에 노드를 방문한다