学步园

捣鼓了一个晚上，最后还是照着书本把这BST弄出来了。悲催的娃娃啊，不动手写这个还真的很难啊！

#ifndef BTREE_H_
#define BTREE_H_

#include <iostream>
using std::ostream;

template <class TreeDataType>
class BSTree
{
private:
    class BSTNode
    {
    public:
        BSTNode* left;
        BSTNode* right;
        TreeDataType data; BSTNode():left(NULL),right(NULL) {}
        BSTNode(TreeDataType a_data):data(a_data),left(NULL),right(NULL) {}
    };//节点声明
    typedef BSTNode* BSTNodePointer;
    BSTNodePointer m_root;

public:
    BSTree():m_root(NULL) {}
    ~BSTree() {deleteNode(m_root);}
    bool isEmpty() const {return m_root == NULL;}
    bool find(const TreeDataType& a_data) const;
    void insert(const TreeDataType& a_data) {insertAux(m_root,a_data);}
    void remove(const TreeDataType& a_data);
    void inorder(ostream& out) const {inorderAux(out, m_root);}
    void graph(ostream& out) const {graphAux(out, 0, m_root);}

protected:
    void deleteNode(BSTNodePointer a_node);//删除节点和所有到子节点
    void insertAux(BSTNodePointer& a_subRoot, const TreeDataType& a_data);
    void inorderAux(ostream& out, BSTNodePointer a_subRoot) const;
    void graphAux(ostream& out, int a_indent, BSTNodePointer a_subRoot) const;
    void find2(const TreeDataType& a_data, bool& found, BSTNodePointer& a_locPtr, BSTNodePointer& a_parent) const; 
};//类模板声明结束
#endif

template <class TreeDataType>
inline void BSTree<TreeDataType>::deleteNode(BSTree<TreeDataType>::BSTNodePointer a_node)
{
    if (a_node->left != NULL)
    {
        deleteNode(a_node->left);
    }
    else if (a_node->right != NULL)
    {
        deleteNode(a_node->right);
    }
    else if (a_node != NULL)
    {
        delete a_node;
        a_node = NULL;
    }
}

template <class TreeDataType>
inline void BSTree<TreeDataType>::insertAux(BSTree<TreeDataType>::BSTNodePointer& a_subRoot, const TreeDataType& a_data)
{
    if (a_subRoot == NULL)
    {
        a_subRoot = new BSTree<TreeDataType>::BSTNode(a_data);
    }
    else if (a_data < a_subRoot->data)
    {
        insertAux(a_subRoot->left,a_data);
    }
    else if (a_subRoot->data < a_data)
    {
        insertAux(a_subRoot->right,a_data);
    }
    else
    {
        std::cerr << "a_data already in the tree!\n";
    }
}

template <class TreeDataType>
inline void BSTree<TreeDataType>::inorderAux(ostream& out, BSTree<TreeDataType>::BSTNodePointer a_subRoot) const
{
    if (a_subRoot != NULL)
    {
        inorderAux(out, a_subRoot->left);//L
        out << a_subRoot->data << " ";//V
        inorderAux(out, a_subRoot->right);//R
    }
}

#include <iomanip>
using std::setw;
using std::endl;
template <class TreeDataType>
inline void BSTree<TreeDataType>::graphAux(ostream& out, int a_indent, BSTree<TreeDataType>::BSTNodePointer a_subRoot) const
{
    if (a_subRoot != NULL)
    {
        graphAux(out, a_indent+8, a_subRoot->right);                //R
        out << setw(a_indent) << " " << a_subRoot->data << endl;    //V
        graphAux(out, a_indent+8, a_subRoot->left);                    //L
    }
}

template <class TreeDataType>
inline bool BSTree<TreeDataType>::find(const TreeDataType& a_data) const
{
    BSTree<TreeDataType>::BSTNodePointer locPtr = m_root;
    bool found = false;
    while (!found && locPtr != NULL)
    {
        if (a_data < locPtr->data)
        {
            locPtr = locPtr->left;
        }
        else if (locPtr->data < a_data)
        {
            locPtr = locPtr->right;
        }
        else
        {
            found = true;
        }
    }
    return found;
}

template <class TreeDataType>
inline void BSTree<TreeDataType>::find2(const TreeDataType& a_data, bool& found, 
                                BSTree<TreeDataType>::BSTNodePointer& a_locPtr,
                                BSTree<TreeDataType>::BSTNodePointer& a_parent) const
{
    a_locPtr = m_root;
    a_parent = NULL;
    found = false;
    while (!found && a_locPtr != NULL)
    {
        if (a_data < a_locPtr->data)
        {
            a_parent = a_locPtr; 
            a_locPtr = a_locPtr->left;
        }
        else if (a_locPtr->data < a_data)
        {
            a_parent = a_locPtr; 
            a_locPtr = a_locPtr->right;
        }
        else
        {
            found = true;
        }
    }
}

template <class TreeDataType>
inline void BSTree<TreeDataType>::remove(const TreeDataType& a_data)
{
    bool found = false;
    BSTree<TreeDataType>::BSTNodePointer x; //被删除的节点
    BSTree<TreeDataType>::BSTNodePointer parent;
    find2(a_data,found,x,parent);
    if (!found)
    {
        std::cerr << "a_data is not in the tree!\n";
        return;
    }
    
    if (x->left != NULL && x->right != NULL)//节点有两个子女
    {
        //查找x的中续后继节点及其双亲节点
        BSTree<TreeDataType>::BSTNodePointer xSucc = x->right;
        parent = x;
        while (xSucc->left != NULL)
        {
            parent = xSucc;
            xSucc = xSucc->left;
        }
        x->data = xSucc->data;
        x = xSucc;
    }
    BSTree<TreeDataType>::BSTNodePointer subTree = x->left;
    if (subTree == NULL)
    {
        subTree = x->right;
    }
    if (parent == NULL)
    {
        m_root = subTree;
    }
    else if (parent->left == x)
    {
        parent->left = subTree;
    }
    else
    {
        parent->right = subTree;
    }
    delete x;
}

测试下结果

#include "BSTree.h"
#include <cstdlib>
#include <iostream>
using namespace std;

int main()
{
    BSTree<int> intBST;
    cout << "Constructing empty BST\n";
    cout << "BST " << (intBST.isEmpty()?"is":"is not") << "empty\n";

    int number;
    for (;;)
    {
        cout << "Item to insert (-999 to stop):";
        cin >> number;
        if (number == -999) break;
        intBST.insert(number);
    }
    intBST.inorder(cout);
    cout << endl;
    intBST.graph(cout);
    
    //测试find
    for (;;)
    {
        cout << "Item to find (-999 to stop):";
        cin >> number;
        if (number == -999) break;
        bool found = intBST.find(number);
        cout << boolalpha << found << endl;
    }
    
    //测试remove
    for (;;)
    {
        cout << "Item to remove (-999 to stop):";
        cin >> number;
        if (number == -999) break;
        intBST.remove(number);
        cout << endl;
        intBST.graph(cout);
        cout << endl;
    }
    intBST.inorder(cout);
    return 0;
}