(2)[Chapter4]N-way-Tree와 LCRS_코드구현(노트)

Chapter4_1_N-way-Tree와 LCRS_코드구현(노트).pdf

3.62MB

 

#include <stdio.h>
#include <stdlib.h>
#pragma warning (disable : 4996)
 
//1_ 이진트리 구조체 선언
typedef char element;
 
typedef struct _LCRSNode {
    struct _LCRSNode* left;
    struct _LCRSNode* right;
    element data;
}treeNode;
 
//2_ 노드 생성 메소드(!=트리 구조체 선언 메소드)
treeNode* CreateLCRS(element data) {
    
    //2_1_ newNode 할당, 생성, 멤버변수 초기화 
    treeNode* newNode= (treeNode*)malloc(sizeof(treeNode));
     newNode->left = NULL;
     newNode->right = NULL;
     newNode->data = data;
     
     //2_2_생성된 newNode의 주소 반환
 
     return newNode;
}
 
//3_ 노드 해제 메소드(1개의 메소드)
void FreeNode(treeNode* node) {
    free(node);
 
    return;
}
 
//4_ 특정 2개의 노드를 1개 부모, 1개 자손지정 메소드 (n-way Tree 메소드)
void AddChild(treeNode* parent, treeNode* child) {
    
    if (parent->left == NULL) {
        parent->left = child;
    }
    else {
        treeNode* tmp = parent->left;
        while (tmp->right != NULL) tmp = tmp->right;
 
        tmp->right = child;
    }
}
 
//5_ N-way Tree 들여쓰기 출력 메소드 ★재귀
void PrintTree(treeNode* root, int depth) {
    //5_0 종료조건 (void반환형이라 필요가 없었다는데 시발 처음 들어봄)
    if (root == NULL) return;
    
    //5_1 구현부
        //a. depth만큼 띄어쓰기 출력
    for (int i = 0; i < depth; i++) {
        printf("   ");
    }
        //b. 자식여부 출력
    if (depth > 0)printf("+--");
        //c. 데이터 출력
    printf("%c\n", root->data);
    //5_2 Left 재귀호출 : Left 호출시 => depth++ (LCRS 규칙)
    if (root->left != NULL) PrintTree(root->left, depth + 1);
 
    //5_3 Right 재귀호출 : Depth 증감 x
    if(root->right !=NULL) PrintTree(root->right, depth);
}
 
void FreeTree(treeNode* Root) {
    //1_ R 재귀호출
    if (Root->right != NULL) FreeTree(Root->right);
    //2_ L 재귀호출
    if (Root->left != NULL) FreeTree(Root->left);
 
    //3_ 구현부
    //3_1 : 멤버변수 NULL 처리(부모관계 끊기)
    Root->left = NULL;
    Root->right = NULL;
    //3_2 : 노드 메모리 해제 메소드
    FreeNode(Root);
}
 
int main() {
 
    //노드 생성
    treeNode* Root = CreateLCRS('A');
    treeNode* B = CreateLCRS('B');
    treeNode* C = CreateLCRS('C');
    treeNode* D = CreateLCRS('D');
    treeNode* E = CreateLCRS('E');
    treeNode* F = CreateLCRS('F');
    treeNode* G = CreateLCRS('G');
    treeNode* H = CreateLCRS('H');
    treeNode* I = CreateLCRS('I');
    treeNode* J = CreateLCRS('J');
    treeNode* K = CreateLCRS('K');
 
    //노드 부모 자식 연결 (n-way tree 조립)
 
    AddChild(Root, B);
    AddChild(Root, G);
    AddChild(Root, I);
 
        AddChild(B, C);
        AddChild(B, D);
 
            AddChild(D, E);
            AddChild(D, F);
 
        AddChild(G, H);
 
        AddChild(I, J);
            AddChild(J, K);
 
 
    PrintTree(Root, 0);
 
    FreeTree(Root);
 
 
    return 0;
}