Data Structure - Binary Tree (C)

向右看齐 2023-01-22 15:59 189阅读 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 )

/*
     * BinaryTree.h - by FreeMan
     */
    
    typedef int ElementType;
    
    #ifndef _BinaryTree_H_
    #define _BinaryTree_H_
    
    struct BinaryTreeNode;
    typedef struct BinaryTreeNode *Position;
    typedef struct BinaryTreeNode *BinaryTree;
    
    BinaryTree MakeBinaryTree(BinaryTree T, ElementType X, BinaryTree Left, BinaryTree Right);
    ElementType RetrieveInBinaryTree(Position P);
    void PreOrderTraverseBinaryTree(BinaryTree T);
    void InOrderTraverseBinaryTree(BinaryTree T);
    void PostOrderTraverseBinaryTree(BinaryTree T);
    int NodeCountOfBinaryTree(BinaryTree T);
    int HeightOfBinaryTree(BinaryTree T);
    int MaxLengthOfBinaryTree(BinaryTree T);
    BinaryTree MakeBinaryTreeEmpty(BinaryTree T);
    
    #endif

/*
     * BinaryTree.c - by FreeMan
     */
    
    #include "BinaryTree.h"
    #include "..\Fatal.h"
    #include <stdlib.h>
    
    struct BinaryTreeNode
    {
        ElementType Element;
        BinaryTree  Left;
        BinaryTree  Right;
    };
    
    BinaryTree MakeBinaryTree(BinaryTree T, ElementType X, BinaryTree Left, BinaryTree Right)
    {
        if (T == NULL)
        {
            T = malloc(sizeof(struct BinaryTreeNode));
            if (T == NULL)
            {
                FatalError("Out of memory!!");
            }
        }
        T->Element = X;
        T->Left = Left;
        T->Right = Right;
        return T;
    }
    
    ElementType RetrieveInBinaryTree(Position P)
    {
        return P->Element;
    }
    
    void PreOrderTraverseBinaryTree(BinaryTree T)
    {
        if (T != NULL)
        {
            printf("%d ", RetrieveInBinaryTree(T));
            PreOrderTraverseBinaryTree(T->Left);
            PreOrderTraverseBinaryTree(T->Right);
        }
    }
    
    void InOrderTraverseBinaryTree(BinaryTree T)
    {
        if (T != NULL)
        {
            InOrderTraverseBinaryTree(T->Left);
            printf("%d ", RetrieveInBinaryTree(T));
            InOrderTraverseBinaryTree(T->Right);
        }
    }
    
    void PostOrderTraverseBinaryTree(BinaryTree T)
    {
        if (T != NULL)
        {
            PostOrderTraverseBinaryTree(T->Left);
            PostOrderTraverseBinaryTree(T->Right);
            printf("%d ", RetrieveInBinaryTree(T));
        }
    }
    
    int NodeCountOfBinaryTree(BinaryTree T)
    {
        if (T == NULL)
        {
            return 0;
        }
        else
        {
            return 1 + NodeCountOfBinaryTree(T->Left) + NodeCountOfBinaryTree(T->Right);
        }
    }
    
    int HeightOfBinaryTree(BinaryTree T)
    {
        if (T == NULL)
        {
            return 0;
        }
        else
        {
            int LeftHeight = HeightOfBinaryTree(T->Left);
            int RightHeight = HeightOfBinaryTree(T->Right);
            return 1 + (Max(LeftHeight, RightHeight));
        }
    }
    
    int MaxLengthOfBinaryTree(BinaryTree T)
    {
        static int maxLength = 0;
        if (T != NULL)
        {
            maxLength = Max(MaxLengthOfNode(T), maxLength);
            MaxLengthOfBinaryTree(T->Left);
            MaxLengthOfBinaryTree(T->Right);
        }
        return maxLength;
    }
    
    static int Max(int Lhs, int Rhs)
    {
        return Lhs > Rhs ? Lhs : Rhs;
    }
    
    static int MaxLengthOfNode(Position P)
    {
        if (P == NULL)
        {
            return 0;
        }
        int leftHeight = HeightOfBinaryTree(P->Left);
        int rightHeight = HeightOfBinaryTree(P->Right);
        int maxLength = leftHeight + rightHeight;
        return maxLength;
    }
    
    BinaryTree MakeBinaryTreeEmpty(BinaryTree T)
    {
        if (T != NULL)
        {
            MakeBinaryTreeEmpty(T->Left);
            MakeBinaryTreeEmpty(T->Right);
            free(T);
        }
        return NULL;
    }

/*
     * BinaryTreeTest.c - by FreeMan
     */
    
    #include "BinaryTree.h"
    #include <stdio.h>
    
    main()
    {
        printf("Testing Binary Tree...\n");
    
        BinaryTree A;
        Position A1 = NULL, A2 = NULL, A3 = NULL, A4 = NULL, A5 = NULL,
            A6 = NULL, A7 = NULL;
        A7 = MakeBinaryTree(A7, 7, NULL, NULL);
        A6 = MakeBinaryTree(A6, 6, NULL, NULL);
        A5 = MakeBinaryTree(A5, 5, NULL, NULL);
        A4 = MakeBinaryTree(A4, 4, NULL, NULL);
        A3 = MakeBinaryTree(A3, 3, A6, A7);
        A2 = MakeBinaryTree(A2, 2, A4, A5);
        A1 = MakeBinaryTree(A1, 1, A2, A3);
        A = A1;
        printf("\nTree A:\n");
        printf("Pre Order Traverse: ");
        PreOrderTraverseBinaryTree(A);
        printf("\nIn Order Traverse: ");
        InOrderTraverseBinaryTree(A);
        printf("\nPost Order Traverse: ");
        PostOrderTraverseBinaryTree(A);
        printf("\nNode Count: %d", NodeCountOfBinaryTree(A));
        printf("\nHeight: %d", HeightOfBinaryTree(A));
        printf("\nMax Length: %d", MaxLengthOfBinaryTree(A));
        MakeBinaryTreeEmpty(A);
    
        printf("\n\nTree B:\n");
        BinaryTree B;
        Position B1 = NULL, B2 = NULL, B3 = NULL, B4 = NULL, B5 = NULL,
            B6 = NULL, B7 = NULL, B8 = NULL, B9 = NULL, B10 = NULL,
            B11 = NULL, B12 = NULL;
        B12 = MakeBinaryTree(B12, 12, NULL, NULL);
        B11 = MakeBinaryTree(B11, 11, NULL, B12);
        B10 = MakeBinaryTree(B10, 10, NULL, B11);
        B9 = MakeBinaryTree(B9, 9, NULL, NULL);
        B8 = MakeBinaryTree(B8, 8, B9, NULL);
        B7 = MakeBinaryTree(B7, 7, NULL, B10);
        B6 = MakeBinaryTree(B6, 6, B8, NULL);
        B5 = MakeBinaryTree(B5, 5, NULL, NULL);
        B4 = MakeBinaryTree(B4, 4, NULL, NULL);
        B3 = MakeBinaryTree(B3, 3, B6, B7);
        B2 = MakeBinaryTree(B2, 2, B4, B5);
        B1 = MakeBinaryTree(B1, 1, B2, B3);
        B = B1;
        printf("Pre Order Traverse: ");
        PreOrderTraverseBinaryTree(B);
        printf("\nIn Order Traverse: ");
        InOrderTraverseBinaryTree(B);
        printf("\nPost Order Traverse: ");
        PostOrderTraverseBinaryTree(B);
        printf("\nNode Count: %d", NodeCountOfBinaryTree(B));
        printf("\nHeight: %d", HeightOfBinaryTree(B));
        printf("\nMax Length: %d", MaxLengthOfBinaryTree(B));
        MakeBinaryTreeEmpty(B);
    
        return 0;
    }
    
    // Output:
    /*
    Testing Binary Tree...
    
    Tree A:
    Pre Order Traverse: 1 2 4 5 3 6 7
    In Order Traverse: 4 2 5 1 6 3 7
    Post Order Traverse: 4 5 2 6 7 3 1
    Node Count: 7
    Height: 3
    Max Length: 4
    
    Tree B:
    Pre Order Traverse: 1 2 4 5 3 6 8 9 7 10 11 12
    In Order Traverse: 4 2 5 1 9 8 6 3 7 10 11 12
    Post Order Traverse: 4 5 2 9 8 6 12 11 10 7 3 1
    Node Count: 12
    Height: 6
    Max Length: 7
    */

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