Data Structure - Search Tree (C)-蒲公英云

Data Structure - Search Tree (C)

矫情吗；* 2023-01-19 03:11 137阅读 0赞

分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请点击http://www.captainbed.net

/*
 * Fatal.h - by FreeMan
 */
#include <stdio.h>
#include <stdlib.h>
#define Error( Str )        FatalError( Str )
#define FatalError( Str )   fprintf( stderr, "%s\n", Str ), exit( 1 )
/*
 * SearchTree.h - by FreeMan
 */
typedef int ElementType;
#ifndef _SearchTree_H_
#define _SearchTree_H_
struct TreeNode;
typedef struct TreeNode *Position;
typedef struct TreeNode *SearchTree;
SearchTree MakeSearchTreeEmpty(SearchTree T);
Position FindInSearchTree(ElementType X, SearchTree T);
Position FindMinInSearchTree(SearchTree T);
Position FindMaxInSearchTree(SearchTree T);
SearchTree InsertInSearchTree(ElementType X, SearchTree T);
SearchTree DeleteInSearchTree(ElementType X, SearchTree T);
ElementType RetrieveInSearchTree(Position P);
#endif
/*
 * SearchTree.c - by FreeMan
 */
#include "SearchTree.h"
#include "..\Fatal.h"
#include <stdlib.h>
struct TreeNode
{
    ElementType Element;
    SearchTree  Left;
    SearchTree  Right;
};
SearchTree MakeSearchTreeEmpty(SearchTree T)
{
    if (T != NULL)
    {
        MakeSearchTreeEmpty(T->Left);
        MakeSearchTreeEmpty(T->Right);
        free(T);
    }
    return NULL;
}
Position FindInSearchTree(ElementType X, SearchTree T)
{
    if (T == NULL)
    {
        return NULL;
    }
    if (X < T->Element)
    {
        return FindInSearchTree(X, T->Left);
    }
    else if (X > T->Element)
    {
        return FindInSearchTree(X, T->Right);
    }
    else
    {
        return T;
    }
}
Position FindMinInSearchTree(SearchTree T)
{
    if (T == NULL)
    {
        return NULL;
    }
    else if (T->Left == NULL)
    {
        return T;
    }
    else
    {
        return FindMinInSearchTree(T->Left);
    }
}
Position FindMaxInSearchTree(SearchTree T)
{
    if (T != NULL)
    {
        while (T->Right != NULL)
        {
            T = T->Right;
        }
    }
    return T;
}
SearchTree InsertInSearchTree(ElementType X, SearchTree T)
{
    if (T == NULL)
    {
        /* Create and return a one-node tree */
        T = malloc(sizeof(struct TreeNode));
        if (T == NULL)
        {
            FatalError("Out of memory!!");
        }
        else
        {
            T->Element = X;
            T->Left = T->Right = NULL;
        }
    }
    else if (X < T->Element)
    {
        T->Left = InsertInSearchTree(X, T->Left);
    }
    else if (X > T->Element)
    {
        T->Right = InsertInSearchTree(X, T->Right);
    }
    /* Else X is in the tree already; we'll do nothing */
    return T;
}
SearchTree DeleteInSearchTree(ElementType X, SearchTree T)
{
    Position TmpCell;
    if (T == NULL)
    {
        Error("Element not found!");
    }
    else if (X < T->Element)  /* Go left */
    {
        T->Left = DeleteInSearchTree(X, T->Left);
    }
    else if (X > T->Element)  /* Go right */
    {
        T->Right = DeleteInSearchTree(X, T->Right);
    }
    else  /* Found element to be deleted */
    {
        if (T->Left && T->Right)  /* Two children */
        {
            /* Replace with smallest in right subtree */
            TmpCell = FindMinInSearchTree(T->Right);
            T->Element = TmpCell->Element;
            T->Right = DeleteInSearchTree(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 RetrieveInSearchTree(Position P)
{
    return P->Element;
}
/*
 * SearchTreeTest.c - by FreeMan
 */
#include "SearchTree.h"
#include <stdio.h>
main()
{
    SearchTree T;
    Position P;
    int i;
    int j = 0;
    T = MakeSearchTreeEmpty(NULL);
    for (i = 0; i < 50; i++, j = (j + 7) % 50)
    {
        T = InsertInSearchTree(j, T);
    }
    for (i = 0; i < 50; i++)
    {
        if ((P = FindInSearchTree(i, T)) == NULL || RetrieveInSearchTree(P) != i)
        {
            printf("Error at %d\n", i);
        }
    }
    for (i = 0; i < 50; i += 2)
    {
        T = DeleteInSearchTree(i, T);
    }
    for (i = 1; i < 50; i += 2)
    {
        if ((P = FindInSearchTree(i, T)) == NULL || RetrieveInSearchTree(P) != i)
        {
            printf("Error at %d\n", i);
        }
    }
    for (i = 0; i < 50; i += 2)
    {
        if ((P = FindInSearchTree(i, T)) != NULL)
        {
            printf("Error at %d\n", i);
        }
    }
    printf("Min is %d, Max is %d\n",
        RetrieveInSearchTree(FindMinInSearchTree(T)),
        RetrieveInSearchTree(FindMaxInSearchTree(T)));
    return 0;
}
// Output:
/*
Min is 1, Max is 49
*/