Written by nodejs-style
on 2021-11-29

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

728x90

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

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

void iter_inorder(tree_ptr node){ int top = -1; tree_ptr stack[MAX_STACK_SIZE]; while(1){ while(node){ push(⊤, node); node = node->left_child; } node = pop(⊤); 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; } }

728x90

from http://psy-er.tistory.com/88 by ccl(A) rewrite - 2021-11-29 03:01:25

Top