Data Structure - Search Tree (C)

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

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

[http_www.captainbed.net]: http://www.captainbed.net/troubleshooter