[ 자료구조 ] level order iterative inorder tree traversal

[ 자료구조 ] level order iterative inorder tree traversal

 

 

1. 반복적 중위 탐색(inorder traversal) 알고리즘 

 

트리 탐색을 꼭 순환 알고리즘으로 작성해야 하는 것은 아니다. 아래 예는 중위 탐색 알고리즘을 반복적인 알고리즘으로 작성한 것이다. 각 노드를 방문하면서 과거 노드를 LIFO 순으로 기억해야 하기 때문에 스택을 사용하였다.

 

void iter_inorder(tree_ptr node){
	int top = -1;
    tree_ptr stack[MAX_STACK_SIZE];
    while(1){
    	while(node){
        	push(&top, node);
            node = node->left_child;
        }
        node = pop(&top);
        if(!node) break;
        printf("%d", node->data);
        node = node->right_child;
    }
}

 

 

2. 레벨 탐색(level order traversal)

 

레벨 i를 탐색할 때 방문 노드의 자식 노드를 저장해둔 뒤 다음 레벨 i를 모두 방문하면 다음 방문자는 저장해둔 노드를 꺼내어 방문한다. 이때 저장해 둔 노드들은 먼저 저장된 노드를 먼저 꺼내어 방문한다. 즉 큐(FIFO) 자료구조를 사용한다.

 

void level_order(tree_ptr ptr){
	int front = rear = 0;
    tree_ptr queue[MAX_QUEUE_SIZE];
    if(!ptr) return;
    add(front, &rear, ptr);
    for(;;){
    	ptr = delete(&front, rear);
        if(ptr){
        	printf("%d", ptr->data);
            if(ptr->left_child)
            	add(front, &rear, ptr->left_child);
            if(ptr->right_child)
            	add(front, &rear, ptr->right_child);
        }
        else break;
    }
    
}