C++ 二叉搜索树（Binary Search Tree）

//  二叉搜索树：
//  A.每个结点都有一个关键码，每个关键码互不相同；
//  B.左子树（若存在）上所有结点的关键码都小于根结点的关键码；
//  C.右子树（若存在）上所有结点的关键码都大于根结点的关键码；
//  D.左子树和右子树也是二叉搜索树
//
//  建立：采取插入建立
//  遍历：采取中序遍历
//
//  测试数据：53 78 65 17 87 09 81 15 -1(结束标志)
#include <iostream>
#include <stack>

template <class T>
struct BSTNode // 二叉搜索树结点的结构定义
{
    T data;
    BSTNode *lChild, *rChild; // 左右孩子指针
};

template <class T>
class BinarySearchTree
{
public:
    BinarySearchTree(BSTNode<T> *p = NULL) {root = p;} // 构造函数
    void createBST(); // 建立二叉搜索树
    bool Insert(T x); // 递归插入
    bool Insert1(T x); // 非递归插入
    bool Pop(T x); // 删除：查找到x，删除x
    void inOrder(); // 中序遍历
    bool seachBST(T x); // 查找函数：递归查找
    bool seachBST1(T x); // 查找函数：非递归查找
    T getMin(); // 获取最小值
    T getMax(); // 获取最大值
private:
    bool seachBST(T x, BSTNode<T> *p); // 递归搜索
    bool Insert(T x, BSTNode<T> *&p); // 递归插入
    bool deleteNode(T x, BSTNode<T> *&p); // 删除结点
    BSTNode<T> *root;
};

// 建立二叉搜索树
template <class T>
void BinarySearchTree<T>::createBST()
{
    int x;
    
    std::cout << "请输入数据建立二叉搜索树:\n";
    std::cin >> x;
    while(x != -1)
    {
        Insert(x);
        std::cin >> x;
    }
}

// 递归插入
template <class T>
bool BinarySearchTree<T>::Insert(T x)
{
    return Insert(x, root);
}

// 递归插入：注意要使用引用符号&,否则每次插入被忽略，root永远为NULL
template <class T>
bool BinarySearchTree<T>::Insert(T x, BSTNode<T> *&p)
{
    BSTNode<T> *newNode;
    
    if(p == NULL) {
        newNode = new BSTNode<T>(); // 新结点
        if(newNode == NULL)
        {
            std::cerr << "申请空间失败!\n";
            exit(1);
        }
        newNode->data = x;
        newNode->lChild = newNode->rChild = NULL;
        p = newNode;
        return true; // 插入成功
    }
    if(x < p->data)
        return Insert(x, p->lChild); // 在左子树中插入
    else if(x > p->data)
        return Insert(x, p->rChild); // 在右子树中插入
    else
        return false; // 重复值，插入不成功
}

// 非递归插入
template <class T>
bool BinarySearchTree<T>::Insert1(T x)
{
    BSTNode<T> *current, *prev, *newNode;
    
    current = root;
    prev = NULL; // 跟踪指针
    while(current != NULL)
    {
        if(x == current->data)
            return false; // 重复值，插入不成功
        else if(x < current->data)
        {
            prev = current;
            current = current->lChild; // 在左子树中找
        }
        else
        {
            prev = current;
            current = current->rChild; // 在右子树中找
        }
    }
    // 插入
    newNode = new BSTNode<T>(); // 新结点
    newNode->data = x;
    newNode->lChild = newNode->rChild = NULL;
    if(prev == NULL) // 插入到根结点
        root = newNode;
    else if(x < prev->data)
        prev->lChild = newNode; // 作为左子树
    else
        prev->rChild = newNode; // 作为右子树
    return true; // 插入成功
}

// 删除：查找到x，删除x
template <class T>
bool BinarySearchTree<T>::Pop(T x)
{
    return deleteNode(x, root);
}

// 删除结点
template <class T>
bool BinarySearchTree<T>::deleteNode(T x, BSTNode<T> *&p) {
    if(p == NULL)
        return false;
    if(x > p->data) {
        return deleteNode(x, p->rChild);
    } else if(x < p->data) {
        return deleteNode(x, p->lChild);
    } else { // 查找到了删除结点
        if(p->lChild == NULL) { // 左子树为空
            BSTNode<T> *current = p;
            p = p->rChild;
            delete current;
        } else if(p->rChild == NULL) { // 右子树为空
            BSTNode<T> *current = p;
            p = p->lChild;
            delete current;
        } else { // 左、右子树都不为空
            // 找前驱：即左子树中的最大数据
            // 或者找后驱：即右子树中的最小数据
            BSTNode<T> *current = p->lChild;
            while(current->rChild != NULL) // 找左子树中最大的元素
                current = current->rChild;
            p->data = current->data; // 用直接前驱的值填到要删除的结点
            // deleteNode(current->data, p->lChild); // p->lChild相当于新的一棵树的根结点，查找current->data并删除
            deleteNode(current->data, current); // 这个是直接跳到该删除的点，对找到的前驱进行同样的删除
        }
        return true;
    }
}

// 查找函数：递归查找
template <class T>
bool BinarySearchTree<T>::seachBST(T x)
{
    return seachBST(x, root);
}

// 查找函数：递归查找
template <class T>
bool BinarySearchTree<T>::seachBST(T x, BSTNode<T> *p)
{
    if(p != NULL)
    {
        if(x == p->data)
            return true;
        else if(x < p->data)
            return seachBST(x, p->lChild); // 在左子树继续查找
        else
            return seachBST(x, p->rChild); // 在右子树继续查找
    }
    return NULL; // 没找到
}

// 查找函数：非递归查找
template <class T>
bool BinarySearchTree<T>::seachBST1(T x)
{
    BSTNode<T> *current = root;
    
    while(current != NULL)
    {
        if(x == current->data)
            return current;
        else if(x < current->data)
            current = current->lChild; // 在左子树中找
        else
           current = current->rChild; // 在右子树中找
    }
    return NULL;
}

// 中序遍历
template <class T>
void BinarySearchTree<T>::inOrder()
{
    std::stack<BSTNode<T> *> s;
    BSTNode<T> *current; // 当前结点
    BSTNode<T> *sTop; // 找顶结点
    
    if(root == NULL)
        std::cout << "空二叉搜索树\n";
    else
    {
        current = root;
        while(current != NULL || !s.empty())
        {
            while(current != NULL) // 往左孩子结点往下走
            {
                s.push(current);
                current = current->lChild;
            }
            if(!s.empty())
            {
                sTop = s.top(); // 取栈顶结点
                s.pop();
                std::cout << sTop->data << " ";
                current = sTop->rChild; // 遍历右孩子树
            }
        }
    }
    std::cout << "\n";
}

// 获取最小值
template <class T>
T BinarySearchTree<T>::getMin()
{
    BSTNode<T> *current;
    
    if(root == NULL)
    {
        std::cout << "空二叉搜索树!\n";
        return -1;
    }
    current = root;
    while(current->lChild != NULL)
        current = current->lChild;
    return current->data;
}

// 获取最大值
template <class T>
T BinarySearchTree<T>::getMax()
{
    BSTNode<T> *current;
    
    if(root == NULL)
    {
        std::cout << "空二叉搜索树!\n";
        return -1;
    }
    current = root;
    while(current->rChild != NULL)
        current = current->rChild;
    return current->data;
}

int main(int argc, const char * argv[]) {
    int choose, finished, x;
    int min, max; // 最小值、最大值
    BinarySearchTree<int> BST; // 声明二叉搜索树对象
    
    finished = 0;
    while(!finished)
    {
        std::cout << "\n***********菜单***************\n";
        std::cout << "1:创建二叉搜索树\n";
        std::cout << "2:递归插入\n";
        std::cout << "3:非递归插入\n";
        std::cout << "4:中序遍历\n";
        std::cout << "5:递归查找\n";
        std::cout << "6:非递归查找\n";
        std::cout << "7:获取最小值\n";
        std::cout << "8:获取最大值\n";
        std::cout << "9:删除某值\n";
        std::cout << "10:退出\n";
        std::cout << "请输入选择[1-10]:";
        std::cin >> choose;
        switch(choose)
        {
            case 1:
                BST.createBST(); // 创建二叉搜索树
                break;
            case 2:
                std::cout << "请输入插入的值：";
                std::cin >> x;
                if(BST.Insert(x)) // 插入成功
                    std::cout << "插入成功！\n";
                else
                    std::cout << "插入失败!\n";
                break;
            case 3:
                std::cout << "请输入插入的值：";
                std::cin >> x;
                if(BST.Insert1(x)) // 插入成功
                    std::cout << "插入成功！\n";
                else
                    std::cout << "插入失败!\n";
                break;
            case 4:
                std::cout << "中序遍历二叉搜索树:\n";
                BST.inOrder(); // 中序遍历
                break;
            case 5:
                std::cout << "请输入要查找的值：";
                std::cin >> x;
                if(BST.seachBST(x)) // 递归查找
                    std::cout << "查找成功！\n";
                else
                    std::cout << "查找失败!\n";
                break;
            case 6:
                std::cout << "请输入要查找的值：";
                std::cin >> x;
                if(BST.seachBST1(x)) // 非递归查找
                    std::cout << "查找成功！\n";
                else
                    std::cout << "查找失败!\n";
                break;
            case 7:
                min = BST.getMin(); // 获取最小值
                if(min != -1)
                    std::cout << "最小值：" << min << "\n";
                break;
            case 8:
                max = BST.getMax(); // 获取最大值
                if(max != -1)
                    std::cout << "最大值：" << max << "\n";
                break;
            case 9:
                std::cout << "请输入要删除的值：";
                std::cin >> x;
                if(BST.Pop(x))
                    std::cout << "删除成功！\n";
                else
                    std::cout << "删除失败！\n";
                break;
            case 10:
                finished = 1;
                break;
            default:
                std::cout << "输入错误，请重新输入!\n";
        }
    }
    return 0;
}