Tree (트리)

다음 그림과 같은 구조를 가지는 것이 트리(Tree)라 한다.

트리는 Root, Branch, Leaf 요소를 가진다.

Root(뿌리) : 트리 구조에서 가장 위에 있는 노드 (그림 A노드)

Leaf(잎) : 트리 구조에서 가장 끝에 있는 노드 (그림 E, F, H, K 노드)

Branch(가지) : Root와 Leaf 사이에 위치한 노드  (그림 D, G, I, C, D, J 노드)

부모(Parent) 자식(Children) 관계

노드 B, C, D에서  B는 C와 D의 부모이고 C와 D는 B의 자식이다. C와 D는 형제(Sibling)이다.

경로(Path)

A노드에서 E노드로 찾아간다고 가정했을 때, A에서 출발해 B노드 지나 D노드에 도착한 후 E노드를 찾아가게 된다.

여기서 A, B, D, E가 A노드에서 E노드 까지의 경로이다.

경로는 길이(Length) 속성을 가진다. 출발 노드에서 도착 노드까지 거쳐야 하는 노드의 수를 나타낸다.

A, B, D, E 경로의 길이는 3이 된다.

깊이(depth)

Root 노드에서 해당하는 노드까지의 경로의 길이를 말한다.

A노드의 깊이는 0

B,G,I 노드의 깊이는 1

C, D, H, J 노드의 깊이는 2

E, F, K 노드의 깊이는 3

레벨(Level)

깊이가 같은 노드의 집합을 말한다.

레벨 2는 C, D, H, J 이다.

높이(Height)

가장 깊이가 깊은 잎 노드의 깊이를 말한다.

트리의 높이는 3이다.

차수(Degree)

해당 노드의 자식 노드 개수를 말한다.

A노드의 차수는 3, B노드의 차수는 2, G노드의 차수는 1이다.

트리의 노드

typedef char ElementType;

typedef struct tagTreeNode

{

struct tagTreeSNode* LeftChild;    //자식 노드를 가리키는 포인터

struct tagTreeNode* RightSibling;    //형제 노드를 가리키는 포인터

ElementType Data;

} TreeNode;

Tree 소스코드

#ifndef TREE_H

#define TREE_H

#include <stdio.h>

#include <stdlib.h>

typedef char ElementType;

typedef struct tagTreeNode 

{

    struct tagTreeNode* LeftChild;

    struct tagTreeNode* RightSibling;

    ElementType Data;

} TreeNode;

TREENode* Tree_CreateNode( ElementType NewData );

void      Tree_DestroyNode( TreeNode* Node );

void      Tree_DestroyTree( TreeNode* Root );

void      Tree_AddChildNode( TreeNode* ParentNode, TreeNode *ChildNode);

void      Tree_PrintTree( TreeNode* Node, int Depth );

#endif TREE_H

#include "Tree.h"

TreeNode* Tree_CreateNode( ElementType NewData )

{

    TreeNode* NewNode = (TreeNode*)malloc( sizeof(TreeNode) );

    NewNode->LeftChild    = NULL;

    NewNode->RightSibling = NULL;

    NewNode->Data = NewData;

    return NewNode;

}

void Tree_DestroyNode( TreeNode* Node )

{

    free(Node);

}

void Tree_DestroyTree( TreeNode* Root )

{

    if ( Root->RightSibling != NULL )

        Tree_DestroyTree( Root->RightSibling );

    if ( Root->LeftChild != NULL )

        Tree_DestroyTree( Root->LeftChild );

    Root->LeftChild = NULL;

    Root->RightSibling = NULL;

    Tree_DestroyNode( Root );

}

void Tree_AddChildNode( TreeNode* Parent, TreeNode *Child)

{

    if ( Parent->LeftChild == NULL )

    {

        Parent->LeftChild = Child;

    }

    else 

    {

        TreeNode* TempNode = Parent->LeftChild;

        while ( TempNode->RightSibling != NULL )

            TempNode = TempNode->RightSibling;

        TempNode->RightSibling = Child;        

    }

}

void Tree_PrintTree( TreeNode* Node, int Depth )

{

    int i=0; 

    for ( i=0; i<Depth; i++ )    //깊이만큼 공백 출력

        printf(" ");

    printf("%c\n", Node->Data);    //노드의 데이터 출력

    if ( Node->LeftChild != NULL )

        Tree_PrintTree(Node->LeftChild, Depth+1);

    if ( Node->RightSibling != NULL )

        Tree_PrintTree(Node->RightSibling, Depth);

}