(4)[Chapter4]이진트리(삽입,삭제 전)(코드구현)

Chapter4_2_이진트리_코드구현(노트).pdf

1.26MB

#이진트리 조립, 순회 코드 구현(삽입 삭제 전) 

※알게 된 개념 :

    이진트리의 메모리 해제는 후위 순회로 진행한다.

#include <stdio.h>
#include <stdlib.h>
#pragma warning (disable : 4996)
 
//1_ 이진트리 구조체 선언
typedef char element;
 
typedef struct _BTNode {
    struct _BTNode* left;
    struct _BTNode* right;
    element data;
}BTNode;
 
//2_ 노드 생성 메소드
BTNode* CreateNode(element data) {
    //(1). newNode 선언, 할당 , 멤버변수 초기화
    BTNode* newNode = (BTNode*)malloc(sizeof(BTNode));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
 
    //(2). newNode 주소 반환
    return newNode;
}
 
//3_ 노드 1개 메모리 해제 메소드
void FreeBTNode(BTNode* node) {
    free(node);
    return;
}
 
//4_ 순회 : 전위순회 , 중위순회, 후위순회 (재귀)
//4_1) 전위 순회 :
void PreOrder(BTNode* root) {
    
    //(1). 예외 조건
    if (root == NULL) return;
 
    //(2). D : 구현부
    printf(" %c", root->data);
 
    //(3). L : 재귀호출(left)
    if (root->left != NULL) PreOrder(root->left);
 
    //(4). R : 재귀호출(right)
    if (root->right != NULL) PreOrder(root->right);
 
}
//4_2) 중위 순회 : L D R
void InOrder(BTNode* root) {
 
    if (root == NULL) return;
 
    if (root->left != NULL) InOrder(root->left);
 
    printf(" %c", root->data);
 
    if (root->right != NULL) InOrder(root->right);
}
//4_3) 후위 순회 :
void PostOrder(BTNode* root) {
 
    if (root == NULL) return;
 
    if (root->left != NULL) PostOrder(root->left);
 
    if (root->right != NULL) PostOrder(root->right);
    
    printf(" %c", root->data);
}
 
//5_ 이진트리 메모리 해제 메소드 : ★후위순회로 구현
void FreeBTree(BTNode* root) {
    //예외 조건 
    if (root == NULL) return;
 
    //후위 순회 : LRD
    if (root->left != NULL) FreeBTree(root->left);
    if (root->right != NULL) FreeBTree(root->left);
    FreeBTNode(root);
}
 
 
int main() {
 
    //노드 생성
    BTNode* A = CreateNode('A');
    BTNode* B = CreateNode('B');
    BTNode* C = CreateNode('C');
    BTNode* D = CreateNode('D');
    BTNode* E = CreateNode('E');
    BTNode* F = CreateNode('F');
    BTNode* G = CreateNode('G');
 
    //자손 잇기 (여기서는 그냥 직접 잇는다.)
        //레벨 0 - 1
    A->left = B;
    A->right = E;
 
        //레벨 1 - 2
    B->left = C;
    B->right = D;
 
    E->left = F;
    E->right = G;
 
    //순회 출력
        //전위 순회 출력
        printf("PreOrder Print :");
        PreOrder(A);
        printf("\n");
 
        //중위 순회 출력
        printf("InOrder Print :");
        InOrder(A);
        printf("\n");
 
        //후위 순회 출력
        printf("PostOrder Print :");
        PostOrder(A);
        printf("\n");
 
    //트리 메모리 해제
        FreeBTree(A);
 
    return 0;
}