[자료구조] 탐색(Search) 1 - 이진 탐색 트리 (11-2-2) 탐색

자 ! 이제 이어서 탐색을 담당하는 BSTSearch 함수를 보자 !
탐색의 과정은 삽입의 과정을 근거로한다 !

BTreeNode *BSTSearch(BTreeNode * bst, BSTData target)
{
    BTreeNode * cNode = bst; // current Node
    BSTData cd; // current Data
    
    while(cNode != NULL)
    {
        cd = GetData(cNode);
        
        if(target == cd)
            return cNode;
        else if(target<cd)
            cNode = GetLeftSubTree(cNode);
        else
            cNode = GetRightSubTree(cNode);
    }
    return NULL;
}

while 문에서 비교대상의 노드보다 값이 작으면 왼쪽/크면 오른쪽으로 이동 하고 있다.
이렇게 반복문안에서 계속해서 이동하다가 target==cd가 되면 return cNode를 하고 끝을 낸다!
그런데더 더 이상 이동할 자식 노드가 없다면 이는 찾는 데이터가 존재하지 않는 상황이다!
이를 바탕으로 while문의 탈출조건이 구성되어있다.

여기까지 만의 내용으로 main함수를 구성해보자.
우선
BST.c 를 보여주겠다.

//
//  BinarySearchTree.c
//  BinarySearchTree
//
//  Created by 서희찬 on 2021/04/17.
//
#include <stdio.h>
#include "BinaryTree2.h"
#include "BinarySearchTree.h"

void BSTMakeAndInit(BTreeNode ** pRoot)
{
   *pRoot = NULL;
}

BSTData BSTGetNodeData(BTreeNode * bst)
{
   return GetData(bst);
}

void BSTInsert(BTreeNode ** pRoot, BSTData data)
{
   BTreeNode * pNode = NULL; //parent Node
   BTreeNode * cNode = *pRoot; // Current Node
   BTreeNode * nNode = NULL; // New Node
   
   // 새노드 저장될 위치 찾는다.
   while(cNode != NULL)
   {
       if(data == GetData(cNode))
           return; // 데이터 중복 허용 x
       
       pNode = cNode; // 매번 while 문을 돌때마다 초기화가 된다.
       
       if(GetData(cNode)>data)
       {
           cNode = GetLeftSubTree(cNode);
       }
       else
           cNode = GetRightSubTree(cNode);
   
   }
   
   //pNode의 자식 노드로 추가할 새 노드의 생성
   nNode = MakeBTreeNode(); // 새 노드 생성
   SetData(nNode, data);
   
   // pNode 의 자식 노드로 추가할 새 노드의 생성
   if(pNode != NULL) // 새  노드가 루트노드아니라면
   {
       if(data < GetData(pNode))
           MakeLeftSubTree(pNode, nNode);
       else
           MakeRightSubTree(pNode, nNode);
   }
   else{ //새노드가 루트노라면
       *pRoot = nNode;
   }
   

}

BTreeNode *BSTSearch(BTreeNode * bst, BSTData target)
{
   BTreeNode * cNode = bst; // current Node
   BSTData cd; // current Data
   
   while(cNode != NULL)
   {
       cd = GetData(cNode);
       
       if(target == cd)
           return cNode;
       else if(target<cd)
           cNode = GetLeftSubTree(cNode);
       else
           cNode = GetRightSubTree(cNode);
   }
   return NULL;
}

이를 기반으로 BSTmain.c를 보여주겠다.

#include <stdio.h>
#include "BinarySearchTree.h"

int main(void)
{
    BTreeNode * bstRoot;
    BTreeNode * sNode; // search Node
    
    BSTMakeAndInit(&bstRoot);
    
    BSTInsert(&bstRoot, 9);
    BSTInsert(&bstRoot, 1);
    BSTInsert(&bstRoot, 6);
    BSTInsert(&bstRoot, 2);
    BSTInsert(&bstRoot, 8);
    BSTInsert(&bstRoot, 3);
    BSTInsert(&bstRoot, 5);
    
    sNode = BSTSearch(bstRoot, 1);
    if(sNode == NULL)
        printf("탐색 실패 ! \n");
    else
        printf("탐색에 성공한 키의 값 : %d \n", BSTGetNodeData(sNode));

    sNode = BSTSearch(bstRoot, 4);
    if(sNode == NULL)
        printf("탐색 실패 ! \n");
    else
        printf("탐색에 성공한 키의 값 : %d \n", BSTGetNodeData(sNode));
    
    sNode = BSTSearch(bstRoot, 6);
    if(sNode == NULL)
        printf("탐색 실패 ! \n");
    else
        printf("탐색에 성공한 키의 값 : %d \n", BSTGetNodeData(sNode));
    
    sNode = BSTSearch(bstRoot, 7);
    if(sNode == NULL)
        printf("탐색 실패 ! \n");
    else
        printf("탐색에 성공한 키의 값 : %d \n", BSTGetNodeData(sNode));
    
    return 0;
}

성공적으로 트리 안에 키 값이 있다면 출력이 된다!

위의 main함수에서는 이진 탐색트리에 값을 저장한 후 저장유무를 확인하는 수준에서 마무리하고 있지만 !
다음포스트에서
트리의 "순회"를 통해서 트리에 저장된 값을 전반적으로 확인해보자