/***************************
   運行環(huán)境  http://www.anycodes.cn/zh/
   原文件  http://www.cnblogs.com/hanxi/archive/2012/08/18/2645929.html
   帶注釋的C++類版本 BST 二叉搜索樹
   ***************************/
  
#ifndef BTREE_H_
#define BTREE_H_
 
#include 
#include 
 #include  
using namespace std;

template 
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) {}
    };//節(jié)點聲明
    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);/*/刪除節(jié)點和所有到子節(jié)點/*/
    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; 
};/*/類模板聲明結(jié)束/*/
#endif

template 
inline void BSTree::deleteNode(BSTree::BSTNodePointer a_node)
{/*/遞歸刪除結(jié)點/*/
    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 
inline void BSTree::insertAux(BSTree::BSTNodePointer& a_subRoot, const TreeDataType& a_data)
{/*/ 遞歸 插入結(jié)點 /*/
    if (a_subRoot == NULL)
    {
        a_subRoot = new BSTree::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
    {/*/不能有相同的結(jié)點/*/
        std::cerr << "a_data already in the tree!\n";
    }
}

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


template 
inline void BSTree::graphAux(ostream& out, int a_indent, BSTree::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 
inline bool BSTree::find(const TreeDataType& a_data) const
{
    BSTree::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 
inline void BSTree::find2(const TreeDataType& a_data, bool& found, 
                                BSTree::BSTNodePointer& a_locPtr,
                                BSTree::BSTNodePointer& a_parent) const
{/*/ 這里不僅要找 還要找到p結(jié)點 已便于后期 刪除找到的結(jié)點 /*/
    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 
inline void BSTree::remove(const TreeDataType& a_data)
{
    bool found = false;
    BSTree::BSTNodePointer x; //被刪除的節(jié)點
    BSTree::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)//節(jié)點有兩個子女
    {
        //查找x的中續(xù)后繼節(jié)點及其雙親節(jié)點
        BSTree::BSTNodePointer xSucc = x->right;
        parent = x;
        while (xSucc->left != NULL)/*/ 在右中找最左的元素/*/
        {
            parent = xSucc;
            xSucc = xSucc->left;
        }
        x->data = xSucc->data; /*/  替換要刪除的結(jié)點數(shù)據(jù)/*/
        x = xSucc;             /*/    轉(zhuǎn)向這個替死鬼/*/
    }
    BSTree::BSTNodePointer subTree = x->left;
    if (subTree == NULL)       /*/    看替死鬼的情況  /*/
    {                           
        subTree = x->right;     
    }
    if (parent == NULL)
    {
        m_root = subTree;
    }
    else if (parent->left == x)
    {
        parent->left = subTree;         /*/替死鬼的右做p的左 /*/
    }
    else
    {
        parent->right = subTree;        /*/替死鬼是p的右孩子，將右孩子做p的右孩子 /*/
    }
    delete x;
}
 /*/  
 -----------文件分割線-------"BSTree.h"----------------
#include "BSTree.h"
#include 
#include 
using namespace std;
/*/ 
int test()
{
/*/ 
數(shù)據(jù)準備 int a[]
/*/	
int a[]={1,3,5,7,9,2,4,6,8,-999};
int  i=0;
    BSTree intBST;
    cout << "Constructing empty BST\n";
    cout << "BST " << (intBST.isEmpty()?"is":"is not") << "empty\n";

    int number;
    for (;;)
    {   number=a[i++];
        if (number == -999) break;
        intBST.insert(number);
    }
    intBST.inorder(cout);
    cout << endl;
    intBST.graph(cout);
    
    //測試find
    for (i=0;;i++)
    {
        cout << "Item to find (-999 to stop):";
         number=a[i];
        if (number == -999) break;
        bool found = intBST.find(number);
        cout << boolalpha << found << endl;
    }
    
    //測試remove
      for (i=0;;i++)
    {
        cout << "Item to remove (-999 to stop):"< 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):"<> 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);    
}
int main()
{
    test(); return 0;
}