algorithm & data structure/자료구조

트리

로봇0301 2022. 11. 24. 17:13

생각해보니 이진트리를 공부했는데 정작 일반 트리에 대해서는 제대로 공부한 게 없는 것 같았다.

오늘 새로 안 내용은 트리의 표현법과 노드의 표현법

저런 게 있다는 것도 처음 알았고, 여태까지 n-link 표현법, 왼쪽 자식- 오른쪽 형제 표현법에 대해서도 처음 알았다.

 

 

원인 모를 예외가 발생해서 애 좀 먹었는데 함수 선언을 안해준 거였다.

앞으로 간단한 소스라도 .h 파일과 .cpp파일로 나눠 써야 할 것 같다.

 

LCRSTree.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#pragma once
typedef int ElementType;
typedef struct tagLCRSNode
{
    struct tagLCRSNode* Child;
    struct tagLCRSNode* Sibling;
 
    ElementType Data;
}LCRSNode;
 
LCRSNode* LCRS_CreateNode(ElementType NewData);
void LCRS_DestroyNode(LCRSNode* Node);
void LCRS_DestroyTree(LCRSNode* Root);
 
void LCRS_AddChildNode(LCRSNode* Parent, LCRSNode* Child);
void LCRS_PrintTree(LCRSNode* Node, int Depth);
cs

LCRSTree.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<iostream>
#include<stdlib.h>
#include "LCRSTree.h"
 
LCRSNode* LCRS_CreateNode(ElementType NewData)
{
    LCRSNode* NewNode = (LCRSNode*)malloc(sizeof(LCRSNode));
    NewNode->Child = NULL;
    NewNode->Sibling = NULL;
    NewNode->Data = NewData;
 
    return NewNode;
}
void LCRS_DestroyNode(LCRSNode* Node)
{
    free(Node);
}
 
void LCRS_DestroyTree(LCRSNode* Root)
{
    if (Root->Sibling != NULL)
    {
        LCRS_DestroyTree(Root->Sibling);
    }
 
    if (Root->Child != NULL)
    {
        LCRS_DestroyTree(Root->Child);
    }
 
    Root->Child = NULL;
    Root->Sibling = NULL;
 
    LCRS_DestroyNode(Root);
}
 
void LCRS_AddChildNode(LCRSNode* Parent, LCRSNode* Child)
{
    if (Parent->Child == NULL)
    {
        Parent->Child = Child;
    }
    else
    {
        LCRSNode* Temp = Parent->Child;
        while (Temp->Sibling != NULL)
        {
            Temp = Temp->Sibling;
        }
        Temp->Sibling = Child;
    }
}
 
void LCRS_PrintTree(LCRSNode* Node, int Depth)
{
    for (int i = 0; i < Depth; i++)
    {
        printf(" ");
    }
 
    printf("%d\n", Node->Data);
    if (Node->Child != NULL)
    {
        LCRS_PrintTree(Node->Child, Depth + 1);
    }
 
    if (Node->Sibling != NULL)
    {
        LCRS_PrintTree(Node->Sibling, Depth);
    }
}
cs

test.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include "LCRSTree.h"
 
int main()
{
    LCRSNode* Root = LCRS_CreateNode(1);
 
    LCRSNode* _2 = LCRS_CreateNode(2);
    LCRSNode* _3 = LCRS_CreateNode(3);
    LCRSNode* _4 = LCRS_CreateNode(4);
    LCRSNode* _5 = LCRS_CreateNode(5);
    LCRSNode* _6 = LCRS_CreateNode(6);
    LCRSNode* _7 = LCRS_CreateNode(7);
    LCRSNode* _8 = LCRS_CreateNode(8);
    LCRSNode* _9 = LCRS_CreateNode(9);
    LCRSNode* _10 = LCRS_CreateNode(10);
 
    LCRS_AddChildNode(Root, _2);
    LCRS_AddChildNode(_2, _3);
    LCRS_AddChildNode(_2, _4);
    LCRS_AddChildNode(_4, _5);
    LCRS_AddChildNode(_4, _6);
    LCRS_AddChildNode(Root, _7);
    LCRS_AddChildNode(_7, _8);
    LCRS_AddChildNode(_7, _9);
    LCRS_AddChildNode(_9, _10);
    
    LCRS_PrintTree(Root, 0);
 
    LCRS_DestroyTree(Root);
 
    return 0;
 
}
cs