스택과 큐는 데이터의 삽입과 삭제를 한 쪽에서만 한다는 단점을 가지고 있습니다.
양쪽 방향에서 하면 더 효율적이지 않을까요
스택과 큐에서 정했던 Front와 Rear에 모두 데이터의 삽입과 삭제를 해주는 자료 구조가 바로 덱입니다.
LCRS 트리 구조체
만들었던 자료 구조들은 모두 노드를 통해 데이터를 처리했습니다.
트리도 마찬가지로 노드와 간선으로 구성되므로 노드 구조체를 만들어 줍니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
// 트리 데이터 타입 정의
typedef char ElementType;
// 트리 노드 구조체
typedef struct LCRSNode
{
// 왼쪽 자식 노드를 가리키는 포인터
struct LCRSNode* LeftChild;
// 오른쪽 형제 노드를 가리키는 포인터
struct LCRSNode* RightSibling;
// 노드의 데이터를 저장하는 멤버
ElementType Data;
} LCRSNode;
|
LCRS 특성에 따라 이전노드와, 다음 노드를 가리키는 포인터를 변형합니다.
왼쪽 자식 노드를 가리키는 LeftChild 포인터와, 오른쪽은 형제 노드를 가리키는 RightSibling을 만듭니다.
물론, 노드에 데이터를 저장하는 Data도 넣어줍니다.
LCRS 트리의 연산
노들 사용한 LCRS 트리를 만들고, 사용하기 위해 구현하는 간단한 연산들입니다.
- LCRS 트리 - 노드 생성
- LCRS 트리 - 노드 소멸
- LCRS 트리 - 트리 소멸
- LCRS 트리 - Child 노드 추가
- LCRS 트리 - 트리 출력
1. LCRS 트리 - 노드 생성
동적으로 사용하기 위해 자유 저장소에 트리의 노드를 생성하는 함수입니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
// 트리 노드 생성
LCRSNode* LCRS_CreateNode(ElementType NewData)
{
// 노드를 자유 저장소에 할당
LCRSNode* NewNode = (LCRSNode*)malloc(sizeof(LCRSNode));
// 노드의 멤버를 초기화
NewNode->LeftChild = NULL;
NewNode->RightSibling = NULL;
NewNode->Data = NewData;
// 생성된 노드의 주소값을 반환
return NewNode;
}
|
노드를 malloc() 함수를 사용해서 동적으로 할당합니다.
생성된 노드의 멤버의 LeftChild와 RightSibling 포인터를 NULL로 초기화하고 전달받은 데이터를 넣어줍니다.
2. LCRS 트리 - 노드 소멸
자유저장소에 동적으로 할당했던 트리의 노드를 소멸시키는 연산입니다.
|
1
2
3
4
5
|
// 트리 노드 소멸
void LCRS_DestroyNode(LCRSNode* Node)
{
free(Node);
}
|
free() 함수를 사용해서 할당된 메모리를 해제합니다.
3. LCRS - 트리 소멸
자유 저장소에 동적으로 생성된 트리를 소멸시키는 연산입니다.
트리를 전체를 소멸하는 연산으로 메모리가 누수되지 않도록 먼저 형제 노드와 자식 노드를 해제합니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
// 트리 소멸
void LCRS_DestroyTree(LCRSNode* Root)
{
// 현재 노드의 형제 노드를 소멸
if (Root->RightSibling != NULL)
LCRS_DestroyTree(Root->RightSibling);
// 현재 노드의 자식 노드를 소멸
if (Root->LeftChild != NULL)
LCRS_DestroyTree(Root->LeftChild);
// 현재 노드를 소멸
Root->LeftChild = NULL;
Root->RightSibling = NULL;
// 루트 노드를 소멸
LCRS_DestroyNode(Root);
}
|
트리의 소멸함수는 재귀 함수 형태로 구현되어 있습니다. 현재 노드의 다음 노드를 타고 들어가는 방식입니다.
형제 노드와 자식 노드를 소멸시키는 부분을 보면 LCRS_DestroyTree 함수를 호출하고 인자로 형제 노드와 자식 노드를 넘겨주는 것을 확인하라 수 있습니다.
형제 노드와 자식 노드를 모두 소멸한 뒤에 마지막에 남은 루트 노드를 LCRS_DestroyNode 함수를 호출해서 자유 저장소에서 소멸합니다.
4. LCRS 트리 - 자식 노드 추가
동적으로 생성했던 노를 트리에 추가하는 연산입니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
// 트리에 자식 노드 추가
void LCRS_AddChildNode(LCRSNode* Parent, LCRSNode* Child)
{
// 부모 노드의 자식 노드가 없는 경우
if (Parent->LeftChild == NULL)
Parent->LeftChild = Child;
// 부모 노드의 자식 노드가 있는 경우
else
{
// 부모 노드의 마지막 자식 노드를 탐색
LCRSNode* TempNode = Parent->LeftChild;
// 부모 노드의 마지막 자식 노드를 탐색
while (TempNode->RightSibling != NULL)
{
TempNode = TempNode->RightSibling;
}
// 부모 노드의 마지막 자식 노드에 자식 노드를 추가
TempNode->RightSibling = Child;
}
}
|
5. LCRS 트리 - 출력
루트 노드부터 순차적으로 노드들을 출력하는 연산입니다.
왼쪽 노드를 먼저 출력하고 오르노쪽 형제도 노드들을 출력합니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
// 트리 출력
void LCRS_PrintTree(LCRSNode* Node, int Depth)
{
int i = 0;
for (i = 0; i < Depth; i++)
printf(" ");
printf("%c\n", Node->Data);
// 왼쪽 자식 노드가 있는 경우
if (Node->LeftChild != NULL)
LCRS_PrintTree(Node->LeftChild, Depth + 1);
// 오른쪽 형제 노드가 있는 경우
if (Node->RightSibling != NULL)
LCRS_PrintTree(Node->RightSibling, Depth);
}
|
깊이만큼 출력창에서 공백을 출력합니다.
댓글