1) 전위 순회 - 루트 > 왼쪽 서브트리 > 오른쪽 서브트리를 차례로 방문.
- 1. 노드가 NULL이면 더이상 순환 호출을 하지 않는다.
- 2. 노드의 데이터를 출력한다.
- 3. 노드의 왼쪽 서브트리를 순환 호출하여 방문한다.
- 4. 노드의 오른쪽 서브트리를 순환 호출하여 방문한다.
preorder(TreeNode *root) {
if(root) {
printf("%d ", root->data);
preorder(root->left);
preorder(root->right);
}
}
2) 중위 순회 - 왼쪽 서브트리 > 루트 > 오른쪽 서브트리
inorder(TreeNode *root) {
if(root) {
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
}
3) 후위 순회 - 왼쪽 서브트리의 모든 노드 > 오른쪽 서브트리의 모든 노드 > 루트노드
postorder(TreeNode *root) {
if(root) {
postorder(root->left);
postorder(root->right);
printf("%d ", root->data);
}
}
*링크법으로 생성된 이진트리 - 순회
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
typedef struct TreeNode {
int data;
struct TreeNode *left, *right;
} TreeNode;
TreeNode n1 = { 1, NULL, NULL }; //노드의 정적 생성(malloc를 사용하지 않는것)
TreeNode n2 = { 4, &n1, NULL }; //노드를 간편하게 만들수 있으나 노드개수가 한정되어 있다.
TreeNode n3 = { 16, NULL, NULL }; //실제로는 잘 사용되지 않는다고 한다.
TreeNode n4 = { 25, NULL, NULL };
TreeNode n5 = { 20, &n3, &n4 };
TreeNode n6 = { 15, &n2, &n5 };
TreeNode *root = &n6;
inorder(TreeNode *root) //전위순회
{
if(root) {
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
}
preorder(TreeNode *root) //중위순회
{
if(root) {
printf("%d ", root->data);
preorder(root->left);
preorder(root->right);
}
}
postorder(TreeNode *root) //후위순회
{
if(root) {
postorder(root->left);
postorder(root->right);
printf("%d ", root->data);
}
}
void main()
{
inorder(root);
printf("\n");
preorder(root);
printf("\n");
postorder(root);
printf("\n");
}
4) 레벨순회
- 각 노드를 레벨 순으로 검사한다.
- 동일한 레벨일 때는 좌->우로 방문한다.
- 큐를 사용하는 순회법이다.
*트리 레벨 순회 알고리즘
level_order(root)
{
initialize queue; //큐 초기화
enqueue(queue, root); //루트 노드를 큐에 삽입
while is_empty(queue) != TRUE do //큐가 공백이 될때까지 계속 다음을 반복한다.
x <- dequeue(queue); //큐 맨처음에 있는 노드 x를 꺼내온다.
if(x != NULL) //x가 NULL이 아니면
then print x->data; //x의 데이터값을 출력하고
enqueue(queue, x->left); //x의 왼쪽 자식을 큐에 삽입
enqueue(queue, x->right); //x의 오른쪽 자식을 큐에 삽입
}
