[C언어] 일반 트리 구조

* 트리 표현법

1. Nested Parenthesis (중첩된 괄호로 표현)

2. Nested Set(벤 다이어그램처럼 그려서 표현)

3. Indentation(들여쓰기, 윈도우즈 파일 탐색기) <--선택 

* 노드 표현법

1. N-Link (Data와 N개의 자식포인터. 단, 노드의 각 차수가 서로 다를 경우 비효율적)

2. Left Child - Right Sibling(Data,Left Child,Right Sibling, 단 2개의 포인터만 필요. 줄여서 LCRS라 칭하겠다) <--선택 

1. LCRSTree.h

#ifndef LCRS_TREE_H
 
#define LCRS_TREE_H
 
#include <stdio.h>
#include <stdlib.h>
 
typedef char ElementType;
 
typedef struct tagLCRSNode{
    ElementType Data;
    struct tagLCRSNode* LeftChild;
    struct tagLCRSNode* RightSibling;
}LCRSNode;
 
LCRSNode* LCRS_CreateNode(ElementType NewData);
void LCRS_DestroyNode(LCRSNode* Node);
void LCRS_DestroyTree(LCRSNode* Root);
 
void LCRS_AddChildNode(LCRSNode* ParentNode,LCRSNode* ChildNode);
void LCRS_PrintTree(LCRSNode* Node,int Depth);
 
void LCRS_PrintNodesAtLevel(LCRSNode* Node,int Level); // 비타민퀴즈 
 
#endif

2. LCRSTree.c

#include "LCRSTree.h"
 
LCRSNode* LCRS_CreateNode(ElementType NewData){
    LCRSNode* NewNode=(LCRSNode*)malloc(sizeof(LCRSNode));
 
    NewNode->Data=NewData;
    NewNode->LeftChild=NULL;
    NewNode->RightSibling=NULL;
 
    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* ParentNode,LCRSNode* ChildNode){
    if(ParentNode->LeftChild==NULL){
        ParentNode->LeftChild=ChildNode;
    }
    else{
        LCRSNode* TempNode=ParentNode->LeftChild;
        while(TempNode->RightSibling!=NULL){
            TempNode=TempNode->RightSibling;
        }
        TempNode->RightSibling=ChildNode;
    }
}
 
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);
    }
}
    
void LCRS_PrintNodesAtLevel(LCRSNode* Node,int Level){
    
    if(Level>0){
        if(Node->LeftChild!=NULL){
            LCRS_PrintNodesAtLevel(Node->LeftChild,Level-1);
        }
        if(Node->RightSibling!=NULL){
            LCRS_PrintNodesAtLevel(Node->RightSibling,Level);
        }
    }
    else{
        while(Node!=NULL){
            printf("%c\t",Node->Data);
            Node=Node->RightSibling;
        }
    }
 
}
 
 
 

3. Test_LCRSTree.c

#include "LCRSTree.h"
 
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("\n\n");
    LCRS_PrintNodesAtLevel(Root,2);
 
    LCRS_DestroyTree(Root);
 
 
    return 0;
    
}

실행결과