二叉查找树

#ifndef _TREE_H

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

SearchTree MakeEmpty(SearchTree T);
Position Find(int X, SearchTree T);
Position FindMin(SearchTree T);
Position FindMax(SearchTree T);
SearchTree Insert(int X, SearchTree T);
SearchTree Delete(int X, SearchTree T);

#endif

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

struct TreeNode{
    int E;
    SearchTree Left, Right;
};

//前序遍历
void PrintTree(SearchTree T){
    if(T == NULL){
        return;
    }
    printf("%d ", T->E);
    if(T->Left != NULL){
        PrintTree(T->Left);
    }
    if(T->Right != NULL){
        PrintTree(T->Right);
    }
}


int main(int argc, char *argv[]){
    int i, arr[5] = {2, 1, 4, 3, 8};
    SearchTree Root, T;
    Root = Insert(6, NULL);
    T = Root;
    for(i = 0; i < 5; i++){
        T = Insert(arr[i], T);
    }
    PrintTree(Root);
    Delete(2, Root);
    printf("\n");
    PrintTree(Root);    
    return 0;
}
//清空树
SearchTree MakeEmpty(SearchTree T){
    if(T != NULL){
        MakeEmpty(T->Left);
        MakeEmpty(T->Right);
        free(T);
    }
    return NULL;
}
//查找节点
SearchTree Find(int X, SearchTree T){
    if(T == NULL){
        return NULL;
    }
    if(X < T->E){
        return Find(X, T->Left);
    }else if(X > T->E){
        return Find(X, T->Right);
    }
    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){
        return NULL;
    }
    while(T->Right != NULL){
        T = T->Right;
    }
    return T;
}

//插入节点
SearchTree Insert(int X, SearchTree T){
    if(T == NULL){
        T = malloc(sizeof(struct TreeNode));
        if(T == NULL){
            printf("out of space");
            exit(0);
        }
        T->E = X;
        T->Left = NULL;
        T->Right = NULL;
    }else if(X < T->E){
        T->Left = Insert(X, T->Left);
    }else if(X > T->E){
        T->Right = Insert(X, T->Right);
    }
    return T;
}


//删除节点
SearchTree Delete(int X, SearchTree T){
    Position TmpCell;
    if(T == NULL){
        //printf("Element not found");
        //return NULL;
    }else if(X < T->E){
        T->Left = Delete(X, T->Left);
    }else if(X > T->E){
        T->Right = Delete(X, T->Right);
    }else if(T->Left && T->Right){//有2个儿子节点
        TmpCell = FindMin(T->Right);
        T->E = TmpCell->E;
        T->Right = Delete(T->E, T->Right);
    }else{//有一个儿子节点,没有儿子节点
        TmpCell = T;
        if(T->Left == NULL){
            T = T->Right;
        }else if(T->Right == NULL){
            T = T->Left;
        }
        free(TmpCell);
    }
    return T;
}