二叉搜索树的Insert、Find、FindMin、FindMax、Delete、MakeEmpty

数据结构

searchTree.h 功能实现

/*============================================== 
二叉查找树（BSTree）的Insert、Find、FindMin、FindMax、Delete、MakeEmpty 
编译环境：Visual Studio 2012 
Date: 2015/01/17 
==============================================*/  
#include <stdlib.h>  
#include <string>  
#include <iostream>  
using namespace std;  
typedef int elemType;  
typedef struct node BSTreeNode;  
typedef struct node BSTree;  
struct node  
{  
    elemType elem;  
    BSTreeNode* left;  
    BSTreeNode* right;  
};  
void fatalError(const std::string str)  
{  
    cout << "ERROR: "<< str <<endl;  
    system("pause");  
    exit(-1);  
}  
BSTreeNode* makeBSTreeEmpty(BSTree* bstree)  
{  
    if (bstree != NULL)  
    {  
        makeBSTreeEmpty(bstree->left);  
        makeBSTreeEmpty(bstree->right);  
        free(bstree);  
    }  
    return bstree;  
}  
BSTreeNode* insertBStree(BSTree* bstree, elemType x)  
{  
    if (bstree == NULL)  
    {  
        bstree = (BSTree *)malloc(sizeof(*bstree));  
        if(bstree == NULL)  
            fatalError("分配BSTree节点异常");  
        bstree->elem = x;  
        bstree->left = NULL;  
        bstree->right = NULL;  
    }  
    else  
    {  
        if (x < bstree->elem)  
        {  
            bstree->left = insertBStree(bstree->left, x);  
        }  
        else if (x > bstree->elem)  
        {  
            bstree->right = insertBStree(bstree->right, x);  
        }  
    }  
    return bstree;  
}  
BSTreeNode* findElem(BSTree* bstree, elemType x)  
{  
    if(bstree == NULL)  
    {  
        cout << "没有找到元素：" << x <<endl;  
        return NULL;  
    }  
    else if (x < bstree->elem)  
    {  
         findElem(bstree->left, x);  
    }  
    else if(x > bstree->elem)  
    {  
         findElem(bstree->right, x);  
    }  
    else  
    {  
        return bstree;  
    }  
}  
BSTreeNode* findMinElem(BSTree* bstree)  
{  
    if (bstree == NULL)  
    {  
        fatalError("findMinElem：树为空");  
    }  
    else if (bstree->left == NULL)  
    {  
        return bstree;  
    }  
    else  
    {  
        findMinElem(bstree->left);  
    }  
}  
BSTreeNode* findMaxElem(BSTree* bstree) //递归实现  
{  
    if (bstree == NULL)  
    {  
        fatalError("findMaxElem：树为空");  
    }  
    else if (bstree->right == NULL)  
    {  
        return bstree;  
    }  
    else  
    {  
        findMaxElem(bstree->right);  
    }  
}  
BSTreeNode* findMaxElem2(BSTree* bstree) //非递归实现  
{  
    if (bstree == NULL)  
    {  
        fatalError("findMaxElem：树为空");  
    }  
    while(bstree->right != NULL)  
    {  
        bstree = bstree->right;  
    }  
    return bstree;  
}  
BSTreeNode *deleteElem(BSTree* bstree, elemType x)  
{  
    BSTreeNode* tempNode = NULL;  
    //删除节点不能通过findElem()函数查找x 元素地址后实现，因为无法获得x 前一结点的地址（可另写一个函数findPrevElem()实现）  
    if (bstree == NULL)  
    {  
        cout << "该BSTree 不含有元素: " << x <<endl;  
    }  
    else if (x < bstree->elem) // x在左子树中，向左递归  
    {  
        bstree->left = deleteElem(bstree->left, x);  
    }  
    else if (x > bstree->elem)  
    {  
        bstree->right = deleteElem(bstree->right, x);  
    }  
    else //找到元素x的位置：x == bstree->elem,进行删除  
    {  
        //===  1或0个child  ======  
        tempNode = bstree;  
        if (bstree->left == NULL)  
        {  
            bstree = bstree->right;  
        }  
        else if (bstree->right == NULL)  
        {  
            bstree = bstree->left;  
            free(tempNode);  
        }  
        //===  2个child  ======  
        else  
        {  
            tempNode = findMinElem(bstree->right); //选右子树的最小值代替被删除节点的元素值（或者：选左子树中的最大值）  
            bstree->elem = tempNode->elem;  
            bstree->right = deleteElem(bstree->right, tempNode->elem); //删除右子树中的最小值（min没有左子树）  
        }  
        //free(tempNode);   //free()如果在此处会导致free两次  
    }  
    return bstree;  
}  

searchTree.cpp 测试函数

#include "searchTree.h"  
int main()  
{  
    BSTree* T = NULL;  
    elemType a[] = {30,50,20,40,25,70,54,23,80,92};  
    for (int i = 0; i < sizeof(a)/sizeof(a[0]); i++)  
    {  
         T = insertBStree(T, a[i]);  
    }  
    findElem(T, 10);  
    for (int i = 0; i < sizeof(a)/sizeof(a[0]); i++)  
    {  
        cout << a[i] << "  0x" << findElem(T, a[i]) << endl;   
    }  
    cout << endl;  
    cout << "Min: addr--0x" << findMinElem(T) <<endl;  
    cout << "1-Max: addr--0x" << findMaxElem(T) <<endl;  
    cout << "2-Max: addr--0x" << findMaxElem2(T) <<endl;  
    deleteElem(T, 10);  
    deleteElem(T, 50);  
    for (int i = 0; i < sizeof(a)/sizeof(a[0]); i++)  
    {  
        cout << a[i] << "  0x" << findElem(T, a[i]) << endl;   
    }  
    cout << endl;  
    makeBSTreeEmpty(T);  
    system("pause");  
    return 0;  
}  

参考资料：《数据结构与算法分析——C语言描述》 P73