[알고리즘]이진트리의 순회

순회 : 이진 트리의 모든 노드를 방문하는 일 

•  Inorder
• preorder
• postorder
• level order

 

Inorder 순회

1. 먼저 T_L을 inorder로 순회하고

2. r을 순회하고

3. T_R을 inorder로 순회 

INORDER-TREE-WALK(x)
if x != NIL
	then INORDER-TREE-WALK(left[x])
    	print key[x]
        INORDER-TREE-WALK(right[x])

x를 루트로 하는 트리를 inorder 순회 = 시간복잡도 O(n)

 

PREORDER-TREE-WALK(x)
	if x != NIL
    then print key[x]
    	 PRE-ORDER-TREE-WALK(left[x])
         PRE-ORDER-TREE-WALK(right[x])
         
POSTORDER-TREE-WALK(x)
	if x != NIL
    then	POST-ORDER-TREE-WALK(left[x])
    		POST-ORDER-TREE-WALK(right[x])
            print key[x]

 

LEVEL ORDER

이진 트리를 레벨 순서대로 방문하겠다는 것입니다. 레벨 순으로 방문, 동일 레벨에서는 왼쪽에서 오른쪽 순서로

가장 적합한 자료구조는 큐입니다. 하나의 큐를 이용해서 레벨 큐를 구성할 수 있는데 큐에 3을 넣고시작해서 3을 빼고 순서대로 노드들을 큐에 놓습니다. 그 다음 큐에서 하나를 꺼내고 큐에 넣고 이러면 꺼낸 자식을 큐에 넣고 자식이 없으면 끝나고 큐에서 하나를 꺼내고 이 자식을 큐에 넣고 순서대로 꺼내는 것을 반복합니다.

 

큐가 비게되면 종료됩니다. 

LEVEL-ORDER-TREE-TRAVERSAL()
	visit the root;
    Q <- root;
    while Q is not empty do
    	v <- dequeue(Q);
        VISIT CHILDREN OF V;
        enqueue children of v into Q;
    end
end