C 트리 순회(Tree traversal) 구현

  ※ 이 글은 코드 위주이니 설명은 아래 링크로 확인 !

  ※ C 트리(Tree) 설명

C 트리(Tree) 설명

---

코드 설명에 들어가기에 앞서, 다시한번 강조하자면 자식 노드에 대한 순회 순서는 무조건 왼쪽에서 오른쪽으로 간다고 생각하면 되고, 전위냐 중위냐 후위냐에 따라 부모 노드가 앞, 중간, 뒤에 붙는다고 생각하면 된다.

 

순회에 사용할 구조체

typedef struct Node
{
    int data;
    struct Node* Left, * Right;
}Node;

  ※ 앞서 봐왔던 구조체들과 다르지 않다.

 

 

 

전위순회(Preorder)

void Preorder(Node* node)
{
    if (node == NULL) return;
	
    printf("%d ", node->data);
    Preorder(node->Left);
    Preorder(node->Right);
}

  ※ 부모 노드가 처음에 위치하면 되므로 출력 순서는 부모 노드 ▶ 왼쪽 자식 노드 ▶ 오른쪽 자식 노드 순이다.

 

 

 

중위순회(Inorder)

void Inorder(Node* node)
{
    if (node == NULL) return;
	
    Inorder(node->Left);
    printf("%d ", node->data);
    Inorder(node->Right);
}

  ※ 부모 노드가 중간에 위치하면 되므로 출력 순서는 왼쪽 자식 노드 ▶ 부모 노드 ▶ 오른쪽 자식 노드 순이다.

 

 

 

후위순회(Postorder)

void Postorder(Node* node)
{
    if (node == NULL) return;
	
    Postorder(node->Left);
    Postorder(node->Right);
    printf("%d ", node->data);
}

  ※ 부모 노드가 마지막에 위치하면 되므로 출력 순서는 왼쪽 자식 노드 ▶ 오른쪽 자식 노드 ▶ 부모 노드 순이다.

 

 

 

풀 소스 코드와 예제 트리는 다음과 같다.

#include <stdio.h>

typedef struct Node
{
    int data;
    struct Node* Left, * Right;
}Node;

Node* Insert(Node* node, int data)
{
    if (node == NULL)
    {
        Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->data = data;
        newNode->Left = NULL;
        newNode->Right = NULL;
		
        return newNode;
    }
    else
    {
        if (node->data > data)
        {
            node->Left = Insert(node->Left, data);
        }
        else if (node->data < data)
        {
            node->Right = Insert(node->Right, data);
        }
        else
        {
            //중복 된 데이터이므로 추가하지 않는다.
        }

        return node;
    }
}

void Preorder(Node* node)
{
    if (node == NULL) return;
	
    printf("%d ", node->data);
    Preorder(node->Left);
    Preorder(node->Right);
}

void Inorder(Node* node)
{
    if (node == NULL) return;
	
    Inorder(node->Left);
    printf("%d ", node->data);
    Inorder(node->Right);
}

void Postorder(Node* node)
{
    if (node == NULL) return;
	
    Postorder(node->Left);
    Postorder(node->Right);
    printf("%d ", node->data);
}

void main()
{
    Node* root = NULL;

    //INSERT
    root = Insert(root, 20);
    root = Insert(root, 10);
    root = Insert(root, 32);
    root = Insert(root, 4);
    root = Insert(root, 13);
    root = Insert(root, 25);
    root = Insert(root, 55);
    
    //PREORDER
    Preorder(root);
    
    //결과 : 20 10 4 13 32 25 55
    
    //INORDER
    Inorder(root);
    
    //결과 : 4 10 13 20 25 32 55
    
    //POSTORDER
    Postorder(root);
    
    //결과 : 4 13 10 25 55 32 20
}

  ※ Insert 함수는 트리에 데이터를 넣기위한 함수이다.