二叉ツリーデータ構造


/*
WRITE BY 1XIU 
20111103
*/
typedef int ElementType;

#ifndef _TREE_H
#define _TREE_H
struct TreeNode;
typedef struct TreeNode *Position;
typedef struct TreeNode *SearchTree;

SearchTree MakeEmpty(SeatchTree T);
Poisition Find(ElementType X,SearchTree T);
Poisition FindMin(SearchTree T);
Poisition FindMax(SearchTree T);
SearchTree Insert(ElementType X,SearchTree T);
SeatchTree Delete(ElementType X,SearchTree T);
ElementType Retrieve(PoisiTION p);

#endif


     :
#include "TreeHead.h"
#include<stdlib.h>

struct TreeNode
{
    ElementType Element;
    SearchTree Left;
    SeatchTree Right;
};
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)
    {
        T = malloc(sizeof(strutc 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);
    //if X is in the tree ,do nothing
    return T;
}
SearchTree Delete(ElementType X ,SearchTree T)
{
    Position tmpCell;
    if(T == NULL)
        Error("Element not found!");
    else if( X<T->Eelement)
        T-Left = Delete(X,T-Left);
    else if(X>T->Right)
        T->Right = Delete(X,T->Right);
    else if(T->Left && T->Right)
    {
        //find the smallest if right subtree
        tmpCell = FindMin(T->Right);
        T->Element = tmpCell->Element;
        T->Right = Delete(T->Element,T->Rigjt);
    }else
    {
        tmpCell = T;
        if(T->Left == NULL)
            T = T->Right;
        else if(T->Right = NULL)
            T = T->Left;
        free(tmpCell);
    }
    return T;
}