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

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