树——二叉查找树BST（未完）

学习资料

推荐Mark Allen Weiss著作的《Data Structures and Algorithm Analysis in C》，讲解详细，重要的是书中的sample代码精巧。

代码

代码来自上书，也可以从网上下载，添加了少量个人理解的注释。

1. 在工程中，一般将结构体和函数的定义放在.c文件里，而将声明放在.h头文件里。
2. 利用typedef定义同一个变量类型的不同名称。

fatal.h

#include <stdio.h>
#include <stdlib.h>

#define Error( Str )        FatalError( Str )
#define FatalError( Str )   fprintf( stderr, "%s\n", Str ), exit( 1 )

tree.h

typedef int ElementType;

/* START: fig4_16.txt */
#ifndef _Tree_H
#define _Tree_H

struct TreeNode;
typedef struct TreeNode *Position;
typedef struct TreeNode *SearchTree;

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  /* _Tree_H */

/* END */

tree.c

#include "tree.h"
#include <stdlib.h>
#include "fatal.h"

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

/* START: fig4_17.txt */
SearchTree MakeEmpty( SearchTree T ) {
    if( T != NULL ) {
        MakeEmpty( T->Left );
        MakeEmpty( T->Right );
        free( T );
    }
    return NULL;
}
/* END */

/* START: fig4_18.txt */
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;
}
/* END */

/* START: fig4_19.txt */
Position FindMin( SearchTree T ) {
    if( T == NULL )
        return NULL;
    else if( T->Left == NULL )  //  T是最左子节点，符合return的条件。
        return T;
    else
        return FindMin( T->Left );
}
/* END */

/* START: fig4_20.txt */
Position FindMax( SearchTree T ) {
    if( T != NULL )
        while( T->Right != NULL )   //  T不是最右节点。
            T = T->Right;           //  T指向右子节点。

    return T;
}
/* END */

/* START: fig4_22.txt */
SearchTree Insert( 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 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;  /* Do not forget this line!! */
}
/* END */

/* START: fig4_25.txt */
/* 删除子树T中的元素，并返回子树T的新的根节点。  */
SearchTree Delete( ElementType X, SearchTree T ) {
    Position TmpCell;

    if( T == NULL )
        Error( "Element not found" );
    else if( X < T->Element ) /* Go left */
        T->Left = Delete( X, T->Left );
    else if( X > T->Element ) /* Go right */
        T->Right = Delete( X, T->Right );
    else  /* Found element to be deleted */
        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 */ //  删除之后，子树T新的根节点为左/右子树。
            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;
}
/* END */

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

testtree.c

#include "tree.h"
#include <stdio.h>

main( ) {
    SearchTree T;
    Position P;
    int i;
    int j = 0;

    T = MakeEmpty( NULL );
    for( i = 0; i < 50; i++, j = ( j + 7 ) % 50 )
        T = Insert( j, T );
    for( i = 0; i < 50; i++ )
        if( ( P = Find( i, T ) ) == NULL || Retrieve( P ) != i )
            printf( "Error at %d\n", i );

    for( i = 0; i < 50; i += 2 )
        T = Delete( i, T );

    for( i = 1; i < 50; i += 2 )
        if( ( P = Find( i, T ) ) == NULL || Retrieve( P ) != i )
            printf( "Error at %d\n", i );
    for( i = 0; i < 50; i += 2 )
        if( ( P = Find( i, T ) ) != NULL )
            printf( "Error at %d\n", i );

    printf( "Min is %d, Max is %d\n", Retrieve( FindMin( T ) ),
            Retrieve( FindMax( T ) ) );

    return 0;
}

未完