7.20.2017

자료구조 BinarySearchTree

//BST.h 만들기
#pragma once
#ifndef BST_H
#define BST_H

#include <stdio.h>
#include <stdlib.h>

typedef int ElementType;

typedef struct tagBSTNode {
        struct tagBSTNode* Left;
        struct tagBSTNode* Right;

        ElementType Data;
}BSTNode;

BSTNode* CreateNode(ElementType Data);
void DestroyNode(BSTNodeNode);
void DestroyTree(BSTNodeTree);

BSTNode* SearchNode(BSTNodeTreeElementType Target);
BSTNode* SearchMinNode(BSTNodeTree);
void InsertNode(BSTNodeTreeBSTNodeChild);
BSTNode* RemoveNode(BSTNodeTreeBSTNodeParentElementType Target);
void PrintInorderTree(BSTNodeNode);

#endif

===========================================================================
//.h 만들기

//왼쪽 자식 노드는 나보다 작고, 오른쪽 자식 노드는 나보다 크다.

#include "BST.h"

BSTNode* CreateNode(ElementType NewData) {
        BSTNode* NewNode = (BSTNode*)malloc(sizeof(BSTNode));
        NewNode->Data = NewData;
        NewNode->Left = NULL;
        NewNode->Right = NULL;

        return NewNode;
}

void DestroyNode(BSTNodeNode) {
        free(Node);
}

void DestroyTree(BSTNodeTree) {
        if (Tree->Right != NULL)
                DestroyTree(Tree->Left);
        if (Tree->Left != NULL)
                DestroyTree(Tree->Right);
        Tree->Left = NULL;
        Tree->Right = NULL;

        DestroyNode(Tree);
}

BSTNode* SearchNode(BSTNodeTreeElementType Target){
if (Tree == NULL)
return NULL;
if (Tree->Data == Target) {
return Tree;
}
else if (Tree->Data > Target) {
return SearchNode(Tree->Left, Target);
}
else return SearchNode(Tree->Right, Target);
}

BSTNode* SearchMinNode(BSTNodeTree){
        if (Tree == NULL)
                return NULL;
        if (Tree->Left == NULL)
                return Tree;
        else return SearchMinNode(Tree->Left);
}

void InsertNode(BSTNodeTreeBSTNodeChild){
        if (Tree->Data < Child->Data) {
                if (Tree->Right == NULL)
                        Tree->Right = Child;
                else InsertNode(Tree->Right, Child);
        }
        else if (Tree->Data > Child->Data) {
                if (Tree->Left == NULL)
                        Tree->Left = Child;
                else InsertNode(Tree->Left, Child);
        }
}

BSTNode* RemoveNode(BSTNodeTreeBSTNodeParentElementType Target){
        BSTNode* Removed = NULL;

        if (Tree->Data > Target)
                Removed = RemoveNode(Tree->Left, TreeTarget);
        else if (Tree->Data < Target)
                Removed = RemoveNode(Tree->Right, TreeTarget);
        else {
                Removed = Tree;

                //leaf 노드인 경우
                if (Tree->Left == NULL&& Tree->Right == NULL) {
                        if (Parent->Left == Tree)
                                Parent->Left = NULL;
                        else Parent->Right = NULL;
                }
                //양쪽 모두 자식이 있는 경우
                else {
                        if (Tree->Left != NULL && Tree->Right != NULL)
                        {
                                //오른쪽 트리의 최소값 노드를 찾아 제거한 뒤 현재의 노드에 위치시킨다.
                                BSTNode* MinNode = SearchMinNode(Tree->Right);
                                MinNode = RemoveNode(TreeNULL, MinNode->Data);
                                Tree->Data = MinNode->Data;
                        }
                        else {
                                //자식이 하나인 경우
                                BSTNode* Temp = NULL;
                                if (Tree->Left != NULL)
                                        Temp = Tree->Left;
                                else
                                        Temp = Tree->Right;
                                if (Parent->Left != Tree)
                                        Parent->Left = Temp;
                                else
                                        Parent->Right= Temp;
                        }
                }
        } return Removed;
}

void InorderPrintTree(BSTNodeNode){
        if (Node == NULLreturn;
        InorderPrintTree(Node->Left);
        printf(" %d"Node->Data);
        InorderPrintTree(Node->Right);
}

void main() {
        BSTNode* Tree = CreateNode(123);
        BSTNode* Node = NULL;

        InsertNode(Tree, CreateNode(22));
        InsertNode(Tree, CreateNode(9918));
        InsertNode(Tree, CreateNode(424));
        InsertNode(Tree, CreateNode(17));
        InsertNode(Tree, CreateNode(3));

        InsertNode(Tree, CreateNode(98));
        InsertNode(Tree, CreateNode(34));

        InsertNode(Tree, CreateNode(760));
        InsertNode(Tree, CreateNode(317));
        InsertNode(Tree, CreateNode(1));

        //트리 출력
        InorderPrintTree(Tree);
        printf("\n");

        //특정 노드 삭제
        printf("Removing 98...\n");

        Node = RemoveNode(Tree, NULL, 98);
        DestroyNode(Node);

        InorderPrintTree(Tree);
        printf("\n");

        //특정 노드 삽입
        printf("Inserting 111...\n");
        InsertNode(Tree, CreateNode(111));
        InorderPrintTree(Tree);
        printf("\n");

        system("pause");
}

===========================================================================
//출력

댓글 없음:

댓글 쓰기