二叉搜索树

头文件代码如下：

#ifndef _Tree_H
#define _Tree_H

struct TreeNode;
typedef struct TreeNode* Position;
typedef struct TreeNode* SearchTree;
void CreateTree(SearchTree &T);
SearchTree Delete(int x, SearchTree T);
SearchTree FindMin(SearchTree T);
SearchTree Insert(int x, SearchTree T);
Position Find(int x, SearchTree T);
SearchTree MakeEmpty(SearchTree T);
void PrintTree(SearchTree T);
struct TreeNode {
    int e;
    SearchTree Left;
    SearchTree Right;
};

#endif

创建二叉搜索树：

void CreateTree(SearchTree &T) {
    int c;
    scanf("%d", &c);
    if (c == -1) {
        T = NULL;
    }
    else {
        T = (SearchTree)malloc(sizeof(TreeNode));
        T->e = c;
        CreateTree(T->Left);
        CreateTree(T->Right);
    }
}

输入-1，该指针值为NULL

打印树：

void PrintTree(SearchTree T) {
    if (T) {
        cout << T->e << " ";
        PrintTree(T->Left);
        PrintTree(T->Right);
    }
}

删除整个树：

SearchTree MakeEmpty(SearchTree T) {
    if (T != NULL) {
        MakeEmpty(T->Left);
        MakeEmpty(T->Right);
        free(T);
    }
    return NULL;
}

查找某个节点：

Position 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);
    }
    
    else {
        return T;
    }
}

查找最小值：

SearchTree FindMin(SearchTree T) {
    if (T == NULL) {
        return NULL;
    }
    else if (T->Left == NULL) {
        return T;
    }
    else {
        return FindMin(T->Left);
    }
}

插入节点：

SearchTree Insert(int x, SearchTree T) {
    if (T == NULL) {
        T = (SearchTree)malloc(sizeof(TreeNode));
        if (T == NULL) {
            return NULL;
        }
        else {
            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 TmpCall;

    if (T == NULL) {
        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) {
        TmpCall = FindMin(T->Right);
        T->e = TmpCall->e;
        T->Right = Delete(T->e, T->Right);
    }
    else {
        TmpCall = T;
        if (T->Left == NULL) {
            T = T->Right;
        }
        else if (T->Right == NULL) {
            T = T->Left;
        }
        free(TmpCall);
    }
    return T;
}