数据结构－二分查找树（C描述）

数据结构－二分查找树（C描述）2010-05-06 本站整理
tree.h
typedef int ElementType;
#ifndef TREE_H_INCLUDED
#define TREE_H_INCLUDED
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_INCLUDED

fatal.h
#ifndef FATAL_H_INCLUDED
#define FATAL_H_INCLUDED
#include <stdio.h>
#include <stdlib.h>
#define Error（Str）  FatalError（Str）
#define FatalError（Str）  fprintf（stderr, "%s
", Str）, exit（1）
#endif // FATAL_H_INCLUDED

tree.c
#include "tree.h"
#include "fatal.h"
struct TreeNode
{
    ElementType Element;
    SearchTree  Left;
    SearchTree  Right;
};
/* 相当于disponse */
SearchTree MakeEmpty（SearchTree T）
{
    if（T ！= NULL）
    {
        MakeEmpty（T->Left）;
        MakeEmpty（T->Right）;
        free（T）;
    }
    return NULL;
}
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;
}
/* 递归实现 */
Position FindMin（SearchTree T）
{
    if（T == NULL）
        return NULL;
    else if（T->Left == NULL）
        return T;
    else
        return FindMin（T->Left）;
}
/* 非递归实现 */
Position FindMax（SearchTree T）
{
    if（T ！= NULL）
        while（T->Right ！= NULL）
            T = T->Right;
    return T;
}
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;
}
/* 删除节点时须注意:始终保持节点在水平线上投影的有序性 */
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 */
        {
            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 Retrieve（Position P）
{
    return P->Element;
}