4. 트리

LCRS(Left Child Right Sibling) 트리

#pragma once
#ifndef LCRSTREE_H
#define LCRSTREE_H

#include <stdio.h>
#include <stdlib.h>
	
typedef char ElementType;
typedef struct tagLCRSNode {
	struct tagLCRSNode* LeftChild;
	struct tagLCRSNode* RightSibling;

	ElementType Data;
}LCRSNode;

LCRSNode* LCRS_CreateNode(ElementType NewData);
void LCRS_DestroyNode(LCRSNode* Node);
void LCRS_AddChildNode(LCRSNode* Parent, LCRSNode* Child);
void LCRS_PrintTree(LCRSNode* Node, int Depth);
void LCRS_DestroyTree(LCRSNode* Root);

#endif

#include "LCRSTree.h"

LCRSNode* LCRS_CreateNode(ElementType NewData) {
	LCRSNode* NewNode = (LCRSNode*)malloc(sizeof(LCRSNode));
	
	NewNode->LeftChild = NULL;
	NewNode->RightSibling = NULL;
	NewNode->Data = NewData;

	return NewNode;
}

void LCRS_DestroyNode(LCRSNode* Node) {
	free(Node);
}

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);
}

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;
	}

}

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);
}

int main() {
	/* 노드 생성 */
	LCRSNode* Root = LCRS_CreateNode('A');

	LCRSNode* B = LCRS_CreateNode('B');
	LCRSNode* C = LCRS_CreateNode('C');
	LCRSNode* D = LCRS_CreateNode('D');
	LCRSNode* E = LCRS_CreateNode('E');
	LCRSNode* F = LCRS_CreateNode('F');
	LCRSNode* G = LCRS_CreateNode('G');
	LCRSNode* H = LCRS_CreateNode('H');
	LCRSNode* I = LCRS_CreateNode('I');
	LCRSNode* J = LCRS_CreateNode('J');
	LCRSNode* K = LCRS_CreateNode('K');

	/* 트리에 노드 추가 */
	LCRS_AddChildNode(Root, B);
	LCRS_AddChildNode(B, C);
	LCRS_AddChildNode(B, D);
	LCRS_AddChildNode(D, E);
	LCRS_AddChildNode(D, F);
	LCRS_AddChildNode(Root, G);
	LCRS_AddChildNode(G, H);

	LCRS_AddChildNode(Root, I);
	LCRS_AddChildNode(I, J);
	LCRS_AddChildNode(J, K);

	/* 트리 출력 */
	LCRS_PrintTree(Root, 0);

	/*printf("Root's Data : %c\n", Root->Data);
	printf("Root's LeftChild : %c\n", Root->LeftChild->Data);
	printf("Root's RightSibling : %c\n", Root->RightSibling->Data);*/

	/* 트리 소멸 */
	LCRS_DestroyTree(Root);

	return 0;
}

 

이진트리

#pragma once
#ifndef BINARY_TREE_H
#define BINARY_TREE_H

#include <stdio.h>
#include <stdlib.h>

typedef char ElementType;

typedef struct tagSBTNode {
	struct tagSBTNode* Left;
	struct tagSBTNode* Right;

	ElementType Data;
}SBTNode;

SBTNode* SBT_CreateNode(ElementType NewData);
void SBT_PreorderPrintTree(SBTNode* Node);
void SBT_InorderPrintTree(SBTNode* Node);
void SBT_PostorderPrintTree(SBTNode* Node);
void SBT_DestroyTree(SBTNode* Root);

#endif

#include "BinaryTree.h"

SBTNode* SBT_CreateNode(ElementType NewData) {
	SBTNode* NewNode = (SBTNode*)malloc(sizeof(SBTNode));

	NewNode->Data = NewData;
	NewNode->Left = NULL;
	NewNode->Right = NULL;

	return NewNode;
}

void SBT_DestroyNode(SBTNode* Node) {
	free(Node);
}

void SBT_DestroyTree(SBTNode* Root) {
	if (Root == NULL)
		return;

	/* 왼쪽 하위 트리 소멸 */
	SBT_DestroyTree(Root->Left);

	/* 오른쪽 하위 트리 소멸 */
	SBT_DestroyTree(Root->Right);

	/* 루트 노드 소멸 */
	SBT_DestroyNode(Root);
}

void SBT_PreorderPrintTree(SBTNode* Node) {
	if (Node == NULL)
		return;

	/* 루트 노드 출력 */
	printf(" %c", Node->Data);

	/* 왼쪽 하위 트리 출력 */
	SBT_PreorderPrintTree(Node->Left);
	
	/* 오른쪽 하위 트리 출력 */
	SBT_PreorderPrintTree(Node->Right);
}

void SBT_InorderPrintTree(SBTNode* Node) {
	if (Node == NULL)
		return;

	/* 왼쪽 하위 트리 출력 */
	SBT_InorderPrintTree(Node->Left);

	/* 루트 노드 출력 */
	printf(" %c", Node->Data);

	/* 오른쪽 하위 트리 출력 */
	SBT_InorderPrintTree(Node->Right);
}

void SBT_PostorderPrintTree(SBTNode* Node) {
	if (Node == NULL)
		return;

	/* 왼쪽 하위 트리 출력 */
	SBT_PostorderPrintTree(Node->Left);

	/* 오른쪽 하위 트리 출력 */
	SBT_PostorderPrintTree(Node->Right);

	/* 루트 노드 출력 */
	printf(" %c", Node->Data);
}


int main() {
	/* 노드 생성 */
	SBTNode* A = SBT_CreateNode('A');
	SBTNode* B = SBT_CreateNode('B');
	SBTNode* C = SBT_CreateNode('C');
	SBTNode* D = SBT_CreateNode('D');
	SBTNode* E = SBT_CreateNode('E');
	SBTNode* F = SBT_CreateNode('F');
	SBTNode* G = SBT_CreateNode('G');

	/* 트리에 노드 추가 */
	A->Left = B;
	B->Left = C;
	B->Right = D;

	A->Right = E;
	E->Left = F;
	E->Right = G;

	/* 트리 출력 */
	printf("Preorder...\n");
	SBT_PreorderPrintTree(A);
	printf("\n\n");

	printf("Inorder...\n");
	SBT_InorderPrintTree(A);
	printf("\n\n");

	printf("Postorder...\n");
	SBT_PostorderPrintTree(A);
	printf("\n");

	/* 트리 소멸 시키기 */
	SBT_DestroyTree(A);

	return 0;
}