데이터 구조 - 이 진 트 리 찾기 (C 언어)

이 진 트 리 는 이 진 트 리 라 고도 부 릅 니 다. 질서 있 는 이 진 트 리 로 이 진 트 리 를 정렬 합 니 다. 빈 트 리 나 다음 과 같은 성질 을 가 진 이 진 트 리 는 이 진 트 리 로 정의 할 수 있 습 니 다.

임의의 노드 의 왼쪽 트 리 가 비어 있 지 않 으 면 왼쪽 트 리 의 모든 노드 의 값 은 뿌리 노드 의 값 보다 작 습 니 다.

만약 에 임의의 노드 의 오른쪽 서브 트 리 가 비어 있 지 않 으 면 오른쪽 서브 트 리 의 모든 노드 의 값 은 그의 뿌리 노드 의 값 보다 크다.

임의의 노드 의 왼쪽, 오른쪽 나무 도 각각 두 갈래 로 나 무 를 찾는다.

키 가 같은 노드 가 없습니다.

이 진 트 리 는 다른 데이터 구조의 장점 에 비해 찾 고 삽입 하 는 시간 복잡 도가 낮 으 며 O (log n) 입 니 다.이 진 트 리 는 기본 적 인 데이터 구조 로 더욱 추상 적 인 데이터 구 조 를 구축 하 는 데 사용 된다. 예 를 들 어 집합, multiset, 관련 배열 등 이다.대량의 입력 데이터 에 대해 링크 의 선형 접근 시간 이 너무 느 려 서 사용 하기에 적합 하지 않다.
다음은 두 갈래 로 트 리 를 정의 하 는 추상 적 인 행동 을 찾 습 니 다.

#ifndef _Tree_H

struct TreeNode;
typedef struct TreeNode *Position;
typedef struct TreeNode *SearchTree;
typedef int ElementType;

SearchTree MakeEmpty( SearchTree T );
Position Find( ElementType X, SearchTree T );
Position FindMin( SearchTree T );
Position FindMax( SearchTree T );
SearchTree Insert( ElementType X, SearchTree T );
SearchTree Delete( ElementType X, SearchTree T );
ElementType Retrieve( Position P );

#endif

상기 추상 적 인 행위 의 실현 에 대해 우 리 는 먼저 실현 코드 를 제시한다.

#include 
#include 
#include 
#include "Tree.h"

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef int Status;

struct TreeNode
{
    ElementType Element;
    SearchTree Left;
    SearchTree Right;
};

SearchTree MakeEmpty(SearchTree T)
{
    if (T != NULL)
    {
        MakeEmpty(T->Left);
        MakeEmpty(T->Right);
        free(T);
    }
    return NULL;
}

Position Find(ElementType X, SearchTree T)
{
    if( T == NULL )
        return NULL;
    if (X < T->Element )
        return Find(X, T->Left);
    else
    if (X > T->Element)
        return Find(X, T->Right);
    else
        return T;
}

Position FindMin(SearchTree T)
{
    if ( T == NULL )
        return NULL;
    else
    if ( T-> Left == NULL )
        return T;
    else
        return FindMin( T->Left );
}

Position FindMax(SearchTree T)
{
    if ( T != NULL )
        while(T->Right != NULL)
            T = T->Right;
    return T;
}

SearchTree Insert(ElementType X, SearchTree T)
{
    if (T == NULL)
    {

        /* Create and return a one-node tree */
        T = malloc(sizeof( struct TreeNode ));
        if ( T == NULL )
            printf("Out of space!!!
");
        else
        {
            T->Element = X;
            T->Left = T->Right = NULL;
        }
    }
    else if (X < T->Element)
        T->Left = Insert(X, T->Left);
    else if (X > T->Element)
        T->Right = Insert(X, T->Right);
    /* Else X is in the tree already; we'll do nothing */

    return T;
}

SearchTree Delete(ElementType X, SearchTree T)
{
    Position TmpCell;
    if (T == NULL)
        printf("Element not found
");
    else if (X < T->Element) /* Go left */
        T->Right = Delete(X, T->Left);
    else if (X > T->Element) /* Go Right */
        T->Right = Delete(X, T->Left);
    else if (T->Left && T->Right) /* Two Children */
    {
        /* Replace with smallest in right subtree */
        TmpCell = FindMin(T->Right);
        T->Element = TmpCell->Element;
        T->Right = Delete(T->Element, T->Right);
    }
    else /* One or zero children */
    {
        TmpCell = T;
        if (T->Left == NULL) /* Also handles 0 children */
            T = T->Right;
        else if (T->Right == NULL)
            T = T->Left;
        free( TmpCell );
    }

    return T;
}

ElementType Retrieve(Position P)
{
    return P->Element;
}

/**
 *     "   "
 * @param T Tree
 */
void PreorderTravel(SearchTree T)
{
    if (T != NULL)
    {
        printf("%d
", T->Element);
        PreorderTravel(T->Left);
        PreorderTravel(T->Right);
    }
}

/**
 *     "   "
 * @param T Tree
 */
void InorderTravel(SearchTree T)
{
    if (T != NULL)
    {
        InorderTravel(T->Left);
        printf("%d
", T->Element);
        InorderTravel(T->Right);
    }
}

/**
 *        
 * @param T Tree
 */
void PostorderTravel(SearchTree T)
{
    if (T != NULL)
    {
        PostorderTravel(T->Left);
        PostorderTravel(T->Right);
        printf("%d
", T->Element);
    }
}

void PrintTree(SearchTree T, ElementType Element, int direction)
{
    if (T != NULL)
    {
        if (direction == 0)
            printf("%2d is root
", T->Element);
        else
            printf("%2d is %2d's %6s child
", T->Element, Element, direction == 1 ? "right" : "left");

        PrintTree(T->Left, T->Element, -1);
        PrintTree(T->Right, T->Element, 1);
    }
}

마지막 으로 우 리 는 우리 의 실현 코드 에 대해 main 함수 에서 테스트 를 한다.

int main(int argc, char const *argv[])
{
    printf("Hello Leon
");
    SearchTree T;
    MakeEmpty(T);

    T = Insert(21, T);
    T = Insert(2150, T);
    T = Insert(127, T);
    T = Insert(121, T);

    printf("      : 
");
    PrintTree(T, T->Element, 0);

    printf("       : 
");
    PreorderTravel(T);

    printf("       : 
");
    InorderTravel(T);

    printf("       : 
");
    PostorderTravel(T);

    printf("   : %d
", FindMax(T)->Element);
    printf("   : %d
", FindMin(T)->Element);

    return 0;
}

이 C 파일 을 컴 파일 하여 실행 합 니 다. 콘 솔 에서 인쇄 한 정 보 는 다음 과 같 습 니 다.

Hello wsx
      :
21 is root
2150 is 21's  right child
127 is 2150's   left child
121 is 127's   left child
       :
21
2150
127
121
       :
21
121
127
2150
       :
121
127
2150
21
   : 2150
   : 21

테스트 성공.