트리자료구조_on c[2]

본 포스트는 c언어를 중심으로 작성되었습니다.

 

트리자료구조_on c[2]

 

저번 포스트에 이어 트리자료구조에 대해서 포스팅 해나가도록 하겠습니다. 순차리스트를 이용하여 이진트리에 대해서 이해해 보도록 하겠습니다.

 

트리자료 구조

위와 같은 이진자료구조가 있습니다. 그렇다면 논리적 구조에서 어떻게 표현될지 확인해 보겠습니다.

[0]

[1] A

[2] B

[3] C

---

---

[n] O

위 와 같이 표현됨을 알 수 있습니다. 즉 루트를 인덱스[1]으로 보았을 때 좌측으로 부터 우측의 방향대로 인덱스가 매겨져가며 아래로 순차적으로 내려갑니다.

 

정리하자면, J와 K의 부모노드는 E가 맞습니다. 인덱스 번호로 보았을 때, [10][11]은 [5]부모노드를 담고 있는것이죠

 

그렇다면 연결리스트를 이용하여 이진트리를 구현해보도록 하겠습니다.

 

연결리스트는 아시다시피 데이터필드와 노드를 연결하는 링크필드가 존재합니다. 그렇다면 오히려 더 표현하기 쉬울 수 있습니다. 

 

왼쪽 링크필드

데이터필드

오른쪽 링크필드

 

당연히 자식노드가 존재하지 않는다면 링크필드에는 null값이 삽입됩니다.,

 

이렇게만 알고 있다면 어떻게 이진트리를 활용하는지 감이 잘 안옵니다. 그 중 저에게 제일 쉬웠던 개념을 코드로 짜보았습니다. 트리순회입니다. 우선 순회에는,

 

순회의개념	모든 데이터를 누락시키지 않고 처리하는 연산을 일컫습니다. 선형자료구조 (리스트, 스택 등)에서는 선형자료구조로서, 일대일 대응 관계를 맺기에 필요가 없지만, 비선형자료구조에서는 현재 노드연산 후 그 다음 노드를 결정해야 하므로 절대적으로 순회연산이 필요합니다
전위 순회	루트로 부터, 왼쪽 서브 트리를 우선으로 하여 순회합니다. 모든 과정은 재귀함수가 사용됩니다.
후위 순회	트리의 같은 레벨의 노드를 순회하고, 서브트리에 대해서도 동일하게 순회합니다.
중위 순회	왼쪽의 서브트리로 부터, 루트, 오른쪽의 서브트리로 순회하며 동일하게 재귀함수가 사용됩니다.

 

코드를 확인해 보겠습니다.

 

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
 
typedef struct treeNode
{
    char data;
    struct treeNode *left;
    struct treeNode *right;
} treeNode;
//트리노드를 구조체로 선언해 줍니다. 순회를 하기 위해서 양노드를 포인터변수로 선언
 
treeNode* makeRootNode(char data, treeNode* leftNode, treeNode* rightNode)
{
    treeNode* root = (treeNode*)malloc(sizeof(treeNode));
    root->data = data;
    root->left = leftNode;
    root->right = rightNode;
    return root;
}
//각 노드마다 데이터,링크 필드를 노드와 연결해줍니다.
 
void Vanguard(treeNode* root)
{
    if (root)
    {
        printf("%c", root->data);
 
        Vanguard(root->left);
        Vanguard(root->right);
    }
}
//재귀함수를 사용하여 계속해서 링크필드를 통해 데이터필드를 순회하여 출력합니다. 더 출력할 결과 물이 없을때 연산을 중지
 
void Lieutenant(treeNode* root)
{
    if (root)
    {
        Lieutenant(root->left);
 
        printf("%c", root->data);
 
        Lieutenant(root->right);
    }
}
 
void Back(treeNode* root)
{
    if (root)
    {
        Back(root->left);
        Back(root->right);
        printf("%c", root->data);
    }
}
 
void main()
{
    char cexit;
 
    treeNode* t7 = makeRootNode('10', NULL, NULL);
    treeNode* t6 = makeRootNode('20', NULL, NULL);
    treeNode* t5 = makeRootNode('3', NULL, NULL);
    treeNode* t4 = makeRootNode('4', NULL, NULL);
    treeNode* t3 = makeRootNode('/', t6, t7);
    treeNode* t2 = makeRootNode('*', t4, t5);
    treeNode* t1 = makeRootNode('-', t2, t3);
 
    printf("\n preorder : ");
   Vanguard(t1);
 
    printf("\n inorder : ");
   Lieutenant(t1);
 
    printf("\n postorder : ");
   Back(t1);
 
    printf("= 10");
    
 
    exit(1);
}

 

65행 부터 67행까지의 연산을 보게되면 t6과 t7사이에 /을 삽입함을 확인 할 수 있습니다.

 

어렵지 않습니다 

 

결과물 출력에는

-*43/2010

4*3-20/10

43*2010/-

 

입니다.

 

이해하시기 어려운 부분은 없으셨을거라 생각합니다!

 

피드백환영하며 댓글 달아주시면 감사하겠습니다.