[자료구조] 트리 - 01 . 트리 기초 다지기

[트리 기초 다지기]

[트리]

트리는 나무를 닮은 자료구조 .회사의 조직체계 : 사장 (뿌리) - 부장 (가지) - 사원 (잎) 를 예로 들 수 있다 .

활용도가 높은 트리는 아래의 다양한 분야에 이용 되고 있다 .

• 운영체제의 파일 시스템 
• HTML,XML 문서를 다룰 때 사용하는 DOM(Document Object Mode)
• 검색 엔진
• 데이터 베이스

[트리의 구조]

트리는 뿌리(Root) / 가지(Branch) / 잎(Leaf) 세가지 요소로 이루어져 있다.

모두 같은 노드이지만 트리 내의 위치에 따라 명칭이 달라진다 .

• 뿌리(Root) - 트리 자료구조의 가장 위에 있는 노드
• 가지 (Branch) - 뿌리와 잎 사이에 있는 모든 노드
• 잎 (Reaf) - 끝에 있어 단말 노드 (Terminal)라고 부르기도 한다 .

노드간 관계

=>B는 C와D의 부모이고 , C와 D는 B의 자식 , C와 D는 형제이다. C와K는 아무 사이가 아니다 .

 

노드의 경로

=> "B - D  - F"를 B에서 F까지 가는 경로라고 칭한다 .

=>경로는 길이 (Length)라는 속성을 가진다 . 출발 노드에서 목적지 노드까지 거쳐야 하는 노드의 수로,위의 경우 2이다.

 

노드의 깊이

=>깊이는 루트노드에서 해당 노드까자지의 경로의 길이를 뜻한다 . 루트의 깊이는 0이다 .

=>레벨 (Level)은 깊이가 같은 노드의 집앞을 일컫는다 . 레벨 1은 B,G,I를 말한다 .

=>높이는 가장 깊은 곳에 있는 잎 노드까지의 깊이를 일컫는다 . 현재 깊이는 3이다 .

 

차수

=>노드의 차수는 해당 노드의 자식 개수를 말한다 .

=>트리의 차수는 자식이 가장 많은 노드의 차수를 말한다 .

=>위의 경우 A의 차수는 3 , B의 차수는 2 , I의 차수는 1이다 . 트리의 차수는 A의 차수가 가장 많으므로 3이다 .

 

[트리 표현하기]

[트리의 표현]

트리는 여러가지 방법으로 표현이 가능하다 . 앞에서 본 거꾸로 세운 나무그림은 가장 일반적인 트리의 표현 방식이다 .

여러가지 노드의 표현법은 트리구조의 데이터를 소프트웨어의 GUI로 표현할 때 자주 채택된다 .

 

[중첩된 괄호 표현법]

같은 레벨의 노드들을 괄호로 묶어 표현한다 .

읽기는 다소 오렵지만 트리를 하나의 공식처럼 표현 할 수 있는 장점이 있다.

[중첩된 집합 표현법]

트리가 하위 트리의 집합이라는 관계를 잘 표현한다 .

[들여쓰기]

자료의 계층적인 특징을 잘 나타낸다 . 윈도우 탐색기의 폴더트리가 좋은 예이다.

[노드 표현하기]

[노드의 표현]

트리를 이루는 노드의 표현법이라면 부모와 자식 형제노드를 서로 연결짓는 방법이다 . 

표현 방식은 N-Link 표현법 / 왼쪽 자식 - 오른쪽 형제 표현법 2가지가 있다 .

 

[ N - 링크 표현법 ]

노드의 차수가 N이라면 , N개의 링크를 가지고 있어 , 해당 링크들이 각각 자식 노드를 가리키도록 노드를 구성한다 .

=>차수의 수가 노드마다 달라지는 트리에는 적용이 어렵다는 단점이 있다 .

=>폴더 트리 같은 경우 폴더의 차수가 0 혹은 수백이 될 수도 있다 .

=>동적 메모리 할당으로 가변 배열으 만들거나 링크드 리스트를 사용 할 수있지만 ,

복잡한 트리를 더 복잡하게 만들 뿐이다 .

 

[ 왼쪽 자식 - 오른쪽 형제 표현법 ]

왼쪽자식에 대한 포인터와 오른쪽 자식에 대한 포인터를 갖고 있는 노드의 구조이다 .

=>해당 방식으로 N개의 차수를 가진 노드의 표현이 두개의 포인터 (자식,형제)로 가능하다 .

=>어느 한 노드의 자식 노드를 얻으려면 왼쪽 자식의 노드에 대한 포인터만 있으면 된다 .

(자식노드의 형제를 계속 찾다보면 모든 자식노드를 얻을 수 있다)

 

[LCRS트리의 주요 연산]

[노드의 선언]

typedef char ElementType;

typefed struct tagLCRSNode
{
	struct tagLCRSNode* LeftChild;
    struct tagLCRSNode* RightSibling;
    ElementType Data;
}LCPSNode;

[노드의 생성]

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

[노드의 소멸]

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

[자식 노드 연결하기]

부모노드에 자식이 있다면 , 자식의 마지막 형제를 찾아 연결. 자식이 없다면 자식으로 바로 연결 .

void LCRS_AddChildNode(LCRSNode* Parent , LCRSNode* Child)
{
    if(Parent->LeftChild==NULL)
    {
    	Parent->LeftChild=Child;
    }
    else
    {
    	LCRSNode* Current=Parent->LeftChild;
    	while(Current->RightSibling!=NULL)
        {
        	Current=Current->RightSibling;
        }
        Current->RightSibling=Child;
    }
}

[트리 출력하기]

트리를 출력할때 들여쓰기로 표현한다 . 깊이만큼 공백을 먼저 출력할것이다 .

void LCRS_PrintTree(LCRS* Node,int Depth)
{
    int i=0;

    for(int i=0;i<Depth;i++)
    printf("");
    
    printf("%c\n",Node->Data;
    
    if(Node->LeftChild!=NULL)
    LCRS_PrintNode(Node->LeftChild,Depth+1);
    
    if(Node->RightSibling!=NULL)
    LCRS_PrintNode(Node->RightSibling,Depth);
}

[트리 구현하기]

[LCRS.h]

#ifndef LCRS
#define LCRS

#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 Data);

//노드 삭제
void LCRS_DestroyNode(LCRSNode* Destroy);

//노드 삽입
void LCRS_AddChildNode(LCRSNode* ParentNode, LCRSNode* ChlidNode);

//트리 삭제
void LCRS_DestroyTree(LCRSNode* Root);


//노드 출력
void LCRS_PrintTree(LCRSNode* Node, int Depth);



#endif // !LCRS

[LCRS.cpp]

#include"LCRS.h"
//노드 생성
LCRSNode* LCRS_CreateNode(ElementType Data)
{
	LCRSNode* NewNode = (LCRSNode*)malloc(sizeof(LCRSNode));
	NewNode->LeftChild = NULL;
	NewNode->RightSibling = NULL;
	NewNode->Data = Data;
	return NewNode;
}
//노드 삭제
void LCRS_DestroyNode(LCRSNode* Destroy)
{
	free(Destroy);
}
//노드 삽입
void LCRS_AddChildNode(LCRSNode* ParentNode, LCRSNode* ChlidNode)
{
	if (ParentNode->LeftChild == NULL)
	{
		ParentNode->LeftChild = ChlidNode;
	}
	else
	{
		LCRSNode* CurrentNode = ParentNode->LeftChild;
		while (CurrentNode->RightSibling != NULL)
		{
			CurrentNode = CurrentNode->RightSibling;
		}
		CurrentNode->RightSibling = ChlidNode;
	}
}
//트리 삭제
void LCRS_DestroyTree(LCRSNode* Root)
{
	if (Root->RightSibling != NULL)
	{
		LCRS_DestroyNode(Root->RightSibling);
	}

	if (Root->RightSibling != NULL)
	{
		LCRS_DestroyNode(Root->RightSibling);
	}

	Root->LeftChild = NULL;
	Root->RightSibling = NULL;
	LCRS_DestroyNode(Root);
}

//노드 출력
void LCRS_PrintTree(LCRSNode* Node, int Depth)
{
	for (int 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);
	}
}

[Test.cpp]

#include"LCRS.h"

int main(void)
{
	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);

	LCRS_DestroyTree(Root);
	return 0;



}