[알고리즘/자료구조] 트리 구조 (Tree)

트리 구조

트리 구조(tree)란 그래프의 일종으로, 여러 노드가 한 노드를 가리킬 수 없는 구조이다. 간단하게는 회로가 없고, 서로 다른 두 노드를 잇는 길이 하나뿐인 그래프를 트리라고 부른다.

트리에서 최상위 노드를 루트 노드(root node 뿌리 노드[*])라고 한다. 또한 노드 A가 노드 B를 가리킬 때 A를 B의 부모 노드(parent node), B를 A의 자식 노드(child node)라고 한다. 자식 노드가 없는 노드를 잎 노드(leaf node 리프 노드[*])라고 한다. 잎 노드가 아닌 노드를 내부 노드(internal node)라고 한다.

소스

/*
/*
/*    khsh5592@naver.com
/*    has3ong.tistory.com
/*
/*    2018 - 11 - 22
/*
*/
#include <iostream>
#include <stdio.h>
#include <conio.h>
using namespace std;
class TreeNode
{
public:
    struct TreeNode* Left_Child;
    struct TreeNode* Right_Child;
    int Data;
    TreeNode* create_Node(int newData);
    void destroy_Node(TreeNode* Node);
    void destroy_Tree(TreeNode* Root);
    void add_Child_Node(TreeNode* Parent, TreeNode *Child);
    void Print(TreeNode* Node, int Depth);
};
TreeNode* Create_Node(int newData)
{
    TreeNode* NewNode = (TreeNode*)malloc( sizeof(TreeNode) );
    NewNode->Left_Child    = NULL;
    NewNode->Right_Child = NULL;
    NewNode->Data = newData;
    return NewNode;
}
void destroy_Node( TreeNode* Node )
{
    free(Node);
}
void destroy_Tree( TreeNode* Root )
{
    if ( Root->Right_Child != NULL )
        destroy_Tree( Root->Right_Child );
    if ( Root->Left_Child != NULL )
        destroy_Tree( Root->Left_Child );
    Root->Left_Child = NULL;
    Root->Right_Child = NULL;
    destroy_Node( Root );
}
void add_Child_Node( TreeNode* Parent, TreeNode *Child)
{
    if ( Parent->Left_Child == NULL )
    {
        Parent->Left_Child = Child;
    }
    else 
    {
        TreeNode* TempNode = Parent->Left_Child;
        while ( TempNode->Right_Child != NULL )
            TempNode = TempNode->Right_Child;
        TempNode->Right_Child = Child;        
    }
}
void Print( TreeNode* Node, int Depth )
{
    cout << Node->Data << " ";
    if ( Node->Left_Child != NULL )
        Print(Node->Left_Child, Depth+1);
    if ( Node->Right_Child != NULL )
        Print(Node->Right_Child, Depth+1);
}
void main()
{
    TreeNode* root = Create_Node(1);
    
    TreeNode* a2 = Create_Node(2);
    TreeNode* a3 = Create_Node(3);
    TreeNode* a4 = Create_Node(4);
    TreeNode* a5 = Create_Node(5);
    TreeNode* a6 = Create_Node(6);
    TreeNode* a7 = Create_Node(7);
    TreeNode* a8 = Create_Node(8);
    TreeNode* a9 = Create_Node(9);
    TreeNode* a10 = Create_Node(10);
    /*  트리에 노드 추가 */
    add_Child_Node( root, a2 );
    add_Child_Node( root, a3 );
    add_Child_Node( root, a4 );
    add_Child_Node( a2, a5 );
    add_Child_Node( a2, a6 );
    add_Child_Node( a2, a7 );
    add_Child_Node( a4, a8 );
    add_Child_Node( a8, a9 );
    add_Child_Node( a9, a10 );
    
    /*  트리 출력 */
    Print( root, 0 );
    getch();
}

구조도





출력화면







출처

위키피디아
https://en.wikipedia.org/wiki/Tree_structure