[자료구조/트리(tree)] 중위순회,후위순회,전위순회,레벨 순회 - 컴도리돌이

 

기본적인 트리의 구조를 알았으면 이제 트리에서 제일 중요한 순회를 배워보았습니다.

---

이진트리의 기본 순회

이진트리(binary tree)

• 전위 순회(preorder traversal) 그림 예시 && c언어 코드

전위순회(preorder traversal) 그림 예시

 

1. 루트 노드를 방문한다

2. 왼쪽 서브 트리를 방문한다

3. 오른쪽 서브 트리를 방문한다

 

전위순회(preorder traversal) c언어 코드

처음 printf로 루트 노드의 값(value)을 처리하고 왼쪽 서브 트리와 오른쪽 서브 트리를 순서대로 순환 호출하여 전위 순회 문제를 해결합니다.

 

• 중위 순회(inorder traversal) 그림 예시 && c언어 코드

중위순회(inorder traversal) 그림예시

 

1. 왼쪽 서브 트리를 방문한다

2. 루트 노드를 방문한다

3. 오른쪽 서브 트리를 방문한다

 

중위순회(inorder traversal) c언어 코드

왼쪽 서브트리를 먼저 순환 재귀 호출로 방문하고 printf로 루트 노드의 값(value)을 처리합니다. 마지막으로 오른쪽 서브 트리를 순환 재귀 호출로 방문합니다.

 

• 후위 순회(postorder traversal) 그림예시 && c언어 코드

후위 순회(postorder traversal) 그림 예시

 

1. 왼쪽 서브 트리를 방문한다

2. 오른쪽 서브 트리를 방문한다

3. 루트 노드를 방문한다

 

 

후위 순회(postorder traversal) c언어 코드

마지막으로 후위 순회는 왼쪽 서브 트리와 오른쪽 서브 트리 순서대로 순환 재귀 호출로 방문하여 마지막으로 루트 노드의 값을 처리함으로써 종료됩니다.

 

• 레벨 순회(level traversal) 그림 예시 && c언어 코드

레벨 순회(level traversal) 그림 예시

레벨 순회(level traversal)에서 사용되는 큐(queue) 코드

레벨 순회(level traversal) c언어 코드

레벨 순회는 그림으로 보이는 것처럼 노드를 레벨 순으로 검사할 때 큐를 사용해서 구현을 합니다. 맨 처음 루트 노드 삽입(enqueue) 상태에서 순회를 시작하며, 맨 앞의 루트 노드를 시작하여 꺼낸 후(삭제-dequeue) 꺼낸 루트 노드의 자식 노드를 삽입하면서 그림 예시로 보이는 순서대로 순회를 합니다. 큐 코드는 트리 구조에 맞게 따로 설정해줘야 합니다!!

 

 

---

이진트리 연산 

 

• 트리의 노드 개수를 계산

트리의 노드 개수를 계산

방문한 노드가 null 값이면 0으로 반환하고, 반환 값을 순환 재귀 호출로 왼쪽 서브 트리와 오른쪽 서브 트리를 더해서 반환(return) 해줍니다. 여기서 +1은 자기 자신을 의미합니다. 만약에 자식 노드가 없는 단말 노드일 경우에는 반환할 때 왼쪽 서브 트리와 오른쪽 서브 트리가 0이겠죠?? 그래서 +1을 해줍니다.

 

• 트리의 단말노드 개수를 계산

트리의 단말노드 개수를 계산

단말 노드의 개수를 구할 때는 자식 노드가 없을 때 반환 값을 1로 해주면 됩니다. 물론 자식 노드가 아닐 경우 계속 반환을 왼쪽 서브 트리와 오른쪽 서브 트리를 해야겠죠??

 

• 서브 트리들의 높이 중에서 최대값을 구하여 반환

서브 트리들의 높이 중에서 최대값을 구하여 반환

서브 트리의 높이를 구할 때에는 왼쪽 서브 트리와 오른쪽 서브 트리를 따로 순환 재귀 호출로 높이를 구해야 합니다. 단말 노드까지 내려왔을 때 반환 값을 왼쪽과 오른쪽을 비교해서 큰 쪽이 반환되게 설정하는데 여기서 +1을 각각 시켜준 이유는 자기 자신의 높이를 더해서 반환해줘야 하기 때문입니다.

 

• 수식 트리 계산

중위 순회 예 : 수식트리 그림 예시

수식 트리 c언어 코드

수식 트리는 중위 순회방식을 같은 방식의 알고리즘입니다. 왼쪽 서브 트리와 오른쪽 서브 트리 문제가 해결되고 나서 마지막 루트 노드가 해결하는 방식으로 먼저 노드의 값이 없을 경우 반환 값을 0으로 해주고, 단말 노드일 경우 자기 자신의 값(value)을 반환해줍니다. 이제 자식 노드로부터 반환된 값으로 루트 노드에서 연산이 이루어집니다.

 

• 폴더 용량 계산

후위 순회 응용 예 : 폴더 용량 계산

후위 순회 폴더 용량 계산 c언어 코드

폴더 용량 계산은 대표적인 후위 순회 예시로 노드가 존재하지 않을 경우 반환 값을 0으로 해주고, 반환 해줄 때 자신의 값(value)과 왼쪽 서브 트리 오른쪽 서브 트리의 값을 더해줘서 반환해줍니다.

 

#include<stdio.h>
#include<stdlib.h>

typedef char Telement;
typedef struct binaryTreeNode
{
    Telement data;
    struct binaryTreeNode *left;
    struct binaryTreeNode *right;
}TNode;


typedef struct LinkedNode
{
    TNode* data;
    struct LinkedNode* link;
}Node;

Node* front = NULL;
Node* rear = NULL;
TNode* root;

void error(char* str)
{
    fprintf(stderr,"%s\n",str);
    exit(1);
}

int is_empty(){ return front == NULL;}
void init_queue() { front = rear = NULL;}

int size()
{
    Node *p;
    int count = 0;
    for(p = front; p!= NULL; p=p->link) count++;
    return count;
}

void enqueue(TNode* e)
{
    Node* p = (Node*)malloc(sizeof(Node));
    p->data = e;
    p->link = NULL;

    if(is_empty()) front = rear = p;
    else
    {
        rear->link = p;
        rear = p;
    }
}

TNode* dequeue()
{
    Node* p;
    TNode* e;

    if(is_empty())
        error("큐 공백 에러");
    p = front;
    front = front->link;
    if(front == NULL) rear = NULL;
    e = p->data;
    free(p);
    return e;
}

void init_tree(){root = NULL;}
int is_empty_tree() { return root == NULL;}
TNode* get_root() { return root; }

TNode* create_tree(Telement val,TNode* left,TNode* right)
{
    TNode* n = (TNode*)malloc(sizeof(TNode));
    n->data = val;
    n->left = left;
    n->right = right;
    return n;
}

void preorder(TNode* n)
{
    if(n != NULL)
    {
        printf("[%c] ",n->data);
        preorder(n->left);
        preorder(n->right);
    }
}
void inorder(TNode *n)
{
    if(n != NULL)
    {
        inorder(n->left);
        printf("[%c] ",n->data);
        inorder(n->right);
    }
}
void postorder(TNode* n)
{
    if(n != NULL)
    {
        postorder(n->left);
        postorder(n->right);
        printf("[%c] ",n->data);
    }
}

void levelorder(TNode* root)
{
    TNode* n;
    if(root == NULL) return;
    init_queue();
    enqueue(root);
    while(!is_empty())
    {
        n = dequeue();
        if(n != NULL)
        {
            printf("[%c] ",n->data);
            enqueue(n->left);
            enqueue(n->right);
        }
    }
}

int count_node(TNode* n)
{
    if(n == NULL) return 0;
    return 1 + count_node(n->left) + count_node(n->right);
}

int count_leaf(TNode* n)
{
    if(n == NULL) return 0;
    if(n->left == NULL && n->right == NULL) return 1;
    else return count_leaf(n->left) +count_leaf(n->right);
}

int calc_height(TNode* n)
{
    int hleft,hright;
    if(n == NULL) return 0;
    hleft = calc_height(n->left);
    hright = calc_height(n->right);
    return (hleft > hright) ? hleft + 1 : hright + 1;
}
int evaluate(TNode* n)
{
    int op1, op2;
    if(n == NULL) return 0;
    if(n->left == NULL && n->right == NULL) return n->data;
    else {
        op1 = evaluate(n->left);
        op2 = evaluate(n->right);
        switch (n->data)
        {
            case '+' : return op1 + op2;
            case '-' : return op1 - op2;
            case '*' : return op1 * op2;
            case '/' : return op1 / op2;
        }
        return 0;
    }
}

int calc_size(TNode* n)
{
    if(n == NULL) return 0;
    return n->data + calc_size(n->left) + calc_size(n->right); 
}