자료구조와 알고리즘/자료구조
[C언어] Tree (트리) - 1편
jaewpark
2021. 9. 9. 18:31
계층적인 관계를 나타내는 데 편리한 것이 트리로써,
트리의 구성 요소에 해당 하는 것을 노드라 칭한다
트리의 개념
Root Node : 부모가 없는 노드 (원조격인 노드)
leaf or Terminal Node (단일 노드) : 자식이 없는 노드
Internal Node : 리프 노드를 제외한 모든 노드
부모 노드 : B, G 노드의 부모 노드는 F이다.
자식 노드 : F 노드의 자식 노드는 B, G이다.
선조 노드 : 주어진 노드의 상위에 있는 노드들, B, F는 D의 선조 노드이다.
후손 노드 : 역으로 어떤 노드의 하위에 있는 노드들, F의 후손은 그 아래 모든 노드들이다.
형제 노드 : 같은 부모를 두고 있는 노드들, B, G 노드는 형제 노드이다.
트리의 차수 : 자식 노드의 개수
트리의 레벨 : 루트노드를 레벨 0으로 하고 아래로 내려오면서 증가, E 는 레벨 3이다.
트리의 높이 : 트리내의 최대 레벨과 일치
|
1
|
트리의 높이 = 1 + Max(왼쪽 하위트리의 높이, 오른쪽 하위트리의 높이)
|
cs |
이진 트리
최대 차수가 2개인 트리
아무런 노드가 없거나 가운데 노드를 중심으로 좌우로 나누어지되, 좌우 하위트리 모두 이진트리
포화 이진트리
- 높이 h인 이진트리에서 모든 리프노드가 레벨 h에 있는 트리
완전 이진트리
- 높이 h인 완전 이진트리는 레벨 (h-1)까지는 포화 이진트리이고, 마지막 레벨 h에서 왼쪽부터 차례대로 리프노드를 채운 트리
배열을 이용한 이진트리 구현
더보기
|
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
|
#ifndef _BIN_TREE_AL_
#define _BIN_TREE_AL_
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 16
typedef struct TreeNodeAL
{
char data;
} TreeNodeAL;
typedef struct TreeAL
{
int count;
TreeNodeAL TreeArray[MAXSIZE];
} TreeAL;
void makeRoot(TreeAL *Lptr, char data);
void InsertLeftChildAL(TreeAL *Lptr, int position, char data);
void InsertRightChildAL(TreeAL *Lptr, int position, char data);
char getLeftChildAL(TreeAL *Lptr, int position);
char getRightChildAL(TreeAL *Lptr, int position);
void display(TreeAL *Tree);
void deleteTreeAL(TreeAL *Tree);
#endif
#ifndef _COMMON_TREE_DEF_
#define _COMMON_TREE_DEF_
#define TRUE 1
#define FALSE 0
#endif
|
cs |
|
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
|
#include "BinTree_AL.h"
void makeRoot(TreeAL *Lptr, char data){
Lptr->TreeArray[1].data = data;
Lptr->count++;
}
void InsertLeftChildAL(TreeAL *Lptr, int position, char data){
if (position < 1 || position * 2 >= MAXSIZE)
{
printf("Error : Out of the range");
return ;
}
else if (Lptr->TreeArray[position * 2].data != 0)
{
printf("Error : LeftChild is FULL");
return ;
}
Lptr->TreeArray[position * 2].data = data;
Lptr->count++;
}
void InsertRightChildAL(TreeAL *Lptr, int position, char data){
if (position < 1 || (position * 2) + 1 >= MAXSIZE)
{
printf("Error : Out of the range");
return ;
}
else if (Lptr->TreeArray[(position * 2) + 1].data != 0)
{
printf("Error : RightChild is FULL");
return ;
}
Lptr->TreeArray[(position * 2) + 1].data = data;
Lptr->count++;
}
char getLeftChildAL(TreeAL *Lptr, int position)
{
char ret = Lptr->TreeArray[position * 2].data;
if (ret == 0)
{
printf("Error : LeftChild is Empty");
return 0;
}
return ret;
}
char getRightChildAL(TreeAL *Lptr, int position)
{
char ret = Lptr->TreeArray[(position * 2) + 1].data;
if (ret == 0)
{
printf("Error : RightChild is Empty");
return 0;
}
return ret;
}
void display(TreeAL *Tree) {
for (int i = 1; i <= Tree->count; i++)
printf("%c ", Tree->TreeArray[i].data);
printf("\n");
}
void deleteTreeAL(TreeAL *Tree){
for (int i = Tree->count; i > 0; i--)
Tree->TreeArray[i].data = 0;
}
|
cs |
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
#include "BinTree_AL.h"
int main(){
TreeAL *L = (TreeAL*)malloc(sizeof(TreeAL));
makeRoot(L, 'A');
InsertLeftChildAL(L, 1, 'B');
InsertRightChildAL(L, 1, 'C');
InsertLeftChildAL(L, 2, 'D');
InsertRightChildAL(L, 2, 'E');
InsertLeftChildAL(L, 4, 'H');
InsertRightChildAL(L, 4, 'I');
InsertLeftChildAL(L, 5, 'J');
InsertRightChildAL(L, 5, 'K');
InsertLeftChildAL(L, 3, 'F');
InsertRightChildAL(L, 3, 'G');
InsertLeftChildAL(L, 6, 'L');
InsertRightChildAL(L, 6, 'M');
display(L);
}
|
cs |
포인터를 이용한 이진 트리 구현
더보기
BinTree.h
|
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
|
#ifndef _BIN_TREE_
#define _BIN_TREE_
#include <stdio.h>
#include <stdlib.h>
typedef struct BinTreeNodeType
{
char data;
int visited;
struct BinTreeNodeType* pLeftChild;
struct BinTreeNodeType* pRightChild;
} BinTreeNode;
typedef struct BinTreeType
{
struct BinTreeNodeType* pRootNode;
} BinTree;
BinTree* makeBinTree(BinTreeNode rootNode);
BinTreeNode* getRootNodeBT(BinTree* pBinTree);
BinTreeNode* insertLeftChildNodeBT(BinTreeNode* pParentNode, BinTreeNode element);
BinTreeNode* insertRightChildNodeBT(BinTreeNode* pParentNode, BinTreeNode element);
BinTreeNode* getLeftChildNodeBT(BinTreeNode* pNode);
BinTreeNode* getRightChildNodeBT(BinTreeNode* pNode);
void deleteBinTree(BinTree* pBinTree);
void deleteBinTreeNode(BinTreeNode* pNode);
#endif
#ifndef _COMMON_TREE_DEF_
#define _COMMON_TREE_DEF_
#define TRUE 1
#define FALSE 0
#endif
|
cs |
BinTree.c
|
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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
|
#include "BinTree.h"
BinTree* makeBinTree(BinTreeNode rootNode)
{
BinTree* pReturn = NULL;
pReturn = (BinTree*)malloc(sizeof(BinTree));
if (pReturn != NULL)
{
pReturn->pRootNode = (BinTreeNode*)malloc(sizeof(BinTreeNode));
if (pReturn->pRootNode != NULL)
{
*pReturn->pRootNode = rootNode;
pReturn->pRootNode->pLeftChild = NULL;
pReturn->pRootNode->pRightChild = NULL;
}
else
printf("Memory Allocation Failure\n");
}
else
printf("Memory Allocation Failure\n");
return (pReturn);
}
BinTreeNode* getRootNodeBT(BinTree* pBinTree)
{
BinTreeNode* pReturn = NULL;
if (pBinTree != NULL)
{
pReturn = pBinTree->pRootNode;
}
return (pReturn);
}
BinTreeNode* insertLeftChildNodeBT(BinTreeNode* pParentNode, BinTreeNode element)
{
BinTreeNode* pReturn = NULL;
if (pParentNode != NULL)
{
if (pParentNode->pLeftChild == NULL)
{
pParentNode->pLeftChild = (BinTreeNode*)malloc(sizeof(BinTreeNode));
*pParentNode->pLeftChild = element;
pParentNode->pLeftChild->pLeftChild = NULL;
pParentNode->pLeftChild->pRightChild = NULL;
pReturn = pParentNode->pLeftChild;
}
else
printf("Already Node is Existing\n");
}
return (pReturn);
}
BinTreeNode* insertRightChildNodeBT(BinTreeNode* pParentNode, BinTreeNode element)
{
BinTreeNode* pReturn = NULL;
if (pParentNode != NULL)
{
if (pParentNode->pRightChild == NULL)
{
pParentNode->pRightChild = (BinTreeNode*)malloc(sizeof(BinTreeNode));
*pParentNode->pRightChild = element;
pParentNode->pRightChild->pLeftChild = NULL;
pParentNode->pRightChild->pRightChild = NULL;
pReturn = pParentNode->pRightChild;
}
else
printf("Already Node is Existing\n");
}
return (pReturn);
}
BinTreeNode* getLeftChildNodeBT(BinTreeNode* pNode)
{
BinTreeNode* pReturn = NULL;
if (pNode != NULL)
{
pReturn = pNode->pLeftChild;
}
return (pReturn);
}
BinTreeNode* getRightChildNodeBT(BinTreeNode* pNode)
{
BinTreeNode* pReturn = NULL;
if (pNode != NULL)
{
pReturn = pNode->pRightChild;
}
return (pReturn);
}
void deleteBinTree(BinTree* pBinTree)
{
deleteBinTreeNode(pBinTree->pRootNode);
free(pBinTree);
}
void deleteBinTreeNode(BinTreeNode* pNode)
{
if (pNode != NULL)
{
deleteBinTreeNode(pNode->pLeftChild);
deleteBinTreeNode(pNode->pRightChild);
free(pNode);
}
}
|
cs |
BinTreeTraversal.h
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
#include "BinTree.h"
void PreOrderBinTree(BinTree *pBinTree);
void PreOrderBinTreeNode(BinTreeNode* pRootNode);
void InOrderBinTree(BinTree *pBinTree);
void InOrderBinTreeNode(BinTreeNode* pRootNode);
void PostOrderBinTree(BinTree *pBinTree);
void PostOrderBinTreeNode(BinTreeNode* pRootNode);
void displayVisited(BinTree *pBinTree);
void displayVisitedNode(BinTreeNode* pRootNode);
void clearVisited(BinTree* pBinTree);
void clearVisitedNode(BinTreeNode* pRootNode);
|
cs |
BinTreeTraversal.c
|
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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
|
#include "BinTree.h"
#include "BinTreeTraversal.h"
void PreOrderBinTree(BinTree *pBinTree)
{
if (pBinTree != NULL)
{
PreOrderBinTreeNode(pBinTree->pRootNode);
}
}
void PreOrderBinTreeNode(BinTreeNode* pRootNode)
{
if (pRootNode != NULL)
{
pRootNode->visited = TRUE;
printf("%c -> ", pRootNode->data);
PreOrderBinTreeNode(pRootNode->pLeftChild);
PreOrderBinTreeNode(pRootNode->pRightChild);
}
}
void InOrderBinTree(BinTree *pBinTree)
{
if (pBinTree != NULL)
{
InOrderBinTreeNode(pBinTree->pRootNode);
}
}
void InOrderBinTreeNode(BinTreeNode* pRootNode)
{
if (pRootNode == NULL)
return ;
InOrderBinTreeNode(pRootNode->pLeftChild);
pRootNode->visited = TRUE;
printf("%c -> ", pRootNode->data);
InOrderBinTreeNode(pRootNode->pRightChild);
}
void PostOrderBinTree(BinTree *pBinTree)
{
if (pBinTree != NULL)
PostOrderBinTreeNode(pBinTree->pRootNode);
}
void PostOrderBinTreeNode(BinTreeNode* pRootNode)
{
if (pRootNode == NULL)
return ;
PostOrderBinTreeNode(pRootNode->pLeftChild);
PostOrderBinTreeNode(pRootNode->pRightChild);
pRootNode->visited = TRUE;
printf("%c -> ", pRootNode->data);
}
void displayVisited(BinTree *pBinTree)
{
if (pBinTree != NULL)
displayVisitedNode(pBinTree->pRootNode);
}
void displayVisitedNode(BinTreeNode* pRootNode)
{
if (pRootNode != NULL)
{
printf("%c Node Visited : %d\n", pRootNode->data, pRootNode->visited);
displayVisitedNode(pRootNode->pLeftChild);
displayVisitedNode(pRootNode->pRightChild);
}
}
void clearVisited(BinTree *pBinTree)
{
if (pBinTree != NULL)
clearVisitedNode(pBinTree->pRootNode);
}
void clearVisitedNode(BinTreeNode* pRootNode)
{
if (pRootNode != NULL)
{
pRootNode->visited = FALSE;
clearVisitedNode(pRootNode->pLeftChild);
clearVisitedNode(pRootNode->pRightChild);
}
}
|
cs |
main.c
|
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
|
#include "BinTree.h"
#include "BinTreeTraversal.h"
int main()
{
BinTree* pBinTree = NULL;
BinTreeNode* pNode1 = NULL;
BinTreeNode* pNode2 = NULL;
BinTreeNode* pNode3 = NULL;
BinTreeNode* pNode4 = NULL;
BinTreeNode* pNode5 = NULL;
BinTreeNode* pNode6 = NULL;
BinTreeNode* pNode7 = NULL;
BinTreeNode node = { 0, };
node.data = 'A';
pBinTree = makeBinTree(node);
if (pBinTree != NULL)
{
pNode1 = getRootNodeBT(pBinTree);
node.data = 'B';
pNode2 = insertLeftChildNodeBT(pNode1, node);
node.data = 'C';
pNode3 = insertRightChildNodeBT(pNode1, node);
node.data = 'D';
pNode4 = insertLeftChildNodeBT(pNode2, node);
node.data = 'E';
pNode5 = insertRightChildNodeBT(pNode2, node);
node.data = 'F';
pNode6 = insertLeftChildNodeBT(pNode3, node);
node.data ='G';
pNode7 = insertRightChildNodeBT(pNode3, node);
}
if (pBinTree != NULL)
{
printf("PreOrder Traversal\n");
PreOrderBinTree(pBinTree);
printf("\n");
displayVisited(pBinTree);
printf("\n\n");
clearVisited(pBinTree);
printf("InOrder Traversal\n");
InOrderBinTree(pBinTree);
printf("\n\n");
clearVisited(pBinTree);
printf("PostOrder Traversal\n");
PostOrderBinTree(pBinTree);
printf("\n");
deleteBinTree(pBinTree);
}
return (0);
}
|
cs |
이진 트리의 순회
V : 부모 노드 L : 왼쪽 자식 노드 R : 오른쪽 자식 노드
Preorder Travelsal(전위 순회)
- 방문 순서 : V - L - R
Inoreder Travelsal(중위 순회)
- 방문 순서 : L - V - R
Postorder Travelsal(후위 순회)
- 방문 순서 : L - R - V
Level-order Travelsal(레벨 순서 순회)
- 모든 노드를 낮은 레벨부터 차례대로 순회, 너비 우선 순회라고도 칭한다
- 위의 그림의 트리라면,
- 레벨 순서 순회: F, B, G, A, D, I, C, E, H