头文件

// BinarySearchTree.h 
//普通二叉搜索树的实现
#include 
using namespace std;

typedef int ElemType;
struct TreeNode
{
        ElemType elem;
        TreeNode *LChildNode;
        TreeNode *RChildNode;
        TreeNode(ElemType &e, TreeNode *lchild, TreeNode *rchild)
                :elem(e), LChildNode(lchild), RChildNode(rchild){}
};

class BinaryTree
{
public:
        BinaryTree();
        virtual ~BinaryTree();

public:
        void insert(ElemType e);
        void remove(ElemType e);
        int find(const ElemType &e);
        void printTree();
        void emptyTree();
private:
        void printTree(TreeNode* &node);
        void GetNodes(stack &st, TreeNode* &node);
private:
        TreeNode *m_root;
};

实现文件

///////////////////BinarySearchTree.cpp
#include 
#include "BinarySearchTree.h"
#include 

/////
BinaryTree::BinaryTree()
{
        m_root = NULL;
}

BinaryTree::~BinaryTree()
{
        emptyTree();  //释放结点
}

//插入结点 (非递归方式)
void BinaryTree::insert( ElemType e )
{
        if (!m_root)
        {
                m_root = new TreeNode(e, NULL, NULL);
                return;
        }
        TreeNode *pNode = m_root;
        while(pNode)
        {
                if (e > pNode->elem)
                {
                        if (pNode->RChildNode == NULL)
                        {
                                pNode->RChildNode = new TreeNode(e, NULL, NULL);
                                cout << "insert tree node: " << e << " succeed!" <<endl;
                                break;
                        }
                        pNode = pNode->RChildNode;
                }
                else if (e < pNode->elem)
                {
                        if (pNode->LChildNode == NULL)
                        {
                                        pNode->LChildNode = new TreeNode(e, NULL, NULL);
                                        cout << "insert tree node: " << e << " succeed!" <<endl;
                                        break;
                        }
                        pNode = pNode->LChildNode;
                }
                else break;
        }
        Sleep(500);
}

//删除指定的结点
void BinaryTree::remove( ElemType e )
{
        TreeNode *pNode = m_root;
        TreeNode *preNode;
        while(pNode)
        {
                if (e < pNode->elem)
                {
                        preNode = pNode;
                        pNode = pNode->LChildNode;
                }
                else if (e > pNode->elem)
                {
                        preNode = pNode;
                        pNode = pNode->RChildNode;
                }
                else break;
        }
        if (pNode)
        {
                TreeNode *pTemp = pNode;
                while(pTemp->RChildNode)
                {
                        preNode = pTemp;
                        pTemp = pTemp->RChildNode;
                }
                if (pTemp && pTemp != pNode)
                {
                        ElemType data = pTemp->elem;
                        pTemp->elem = pNode->elem;
                        pNode->elem = data;
                }
                if (pTemp != pNode && preNode->RChildNode->elem == e)
                {
                        if (pTemp->LChildNode)
                        {
                                preNode->RChildNode = pTemp->LChildNode;
                        }
                        else
                                preNode->RChildNode = NULL;
                        delete pTemp;   
                }
                else
                {
                        if (pTemp->LChildNode)//移动该结点下的左子树
                        {
                                preNode->LChildNode = pTemp->LChildNode;
                        }
                        else
                                preNode->LChildNode = NULL;
                        delete pTemp;
                }
                cout << "remove  tree node: " << e << " succeed!" <<endl;
        }
        Sleep(500);
}

// 查找树中的某一结点
int BinaryTree::find( const ElemType &e )
{
        TreeNode *pNode = m_root;
        while(pNode)
        {
                if (e < pNode->elem)
                {
                        pNode = pNode->LChildNode;
                }
                else if (e > pNode->elem)
                {
                        pNode = pNode->RChildNode;
                }
                else break;
        }
        if(pNode) 
        {
                cout << "The elem: " << e
                        << " had find in tree."<< endl;
                Sleep(500);
                return 1;
        }
        else 
                return 0;
}

// 用遍历方式打印树的结点
void BinaryTree::printTree()
{
        cout << "print the tree nodes: ";
        if (m_root)
                printTree(m_root);
        else 
                cout << "The Tree is empty !\n";
        cout << endl;
        Sleep(500);
}

void BinaryTree::printTree(TreeNode* &node)
{  //默认为前序遍历
        if (node)
        {
                cout << node->elem << "  ";
                printTree(node->LChildNode);
                printTree(node->RChildNode);
        }
}

// 清空树的结点，释放内存
void BinaryTree::emptyTree()
{
        stack stackTree;  //用临时的栈类对象遍历存储整个树的结点
        if (m_root == NULL)
        {
                return;
        }
        GetNodes(stackTree, m_root);//遍历存储整个树的结点
        TreeNode *tempNode = stackTree.top();
        stackTree.pop();
        while(tempNode)
        {
                delete tempNode;
                if (stackTree.size()>0)
                {
                        tempNode = stackTree.top();
                        stackTree.pop();
                }
                else break;
        }
        m_root = NULL;
        cout << "Emptied The Tree Nodes.\n";
}

void BinaryTree::GetNodes( stack &st, TreeNode* &node )
{// 用递归的方法遍历所有结点，存储在栈对象中
        if (node)
        {
                st.push(node);
        }
        else return;
        TreeNode *pLeft = node->LChildNode;
        if (pLeft)
        {
                GetNodes(st, pLeft );
        }
        TreeNode *pRight = node->RChildNode;
        if (pRight)
        {
                GetNodes(st, pRight );
        }
}

测试文件

//////Test.cpp for class BinaryTree

#include 
#include "BinarySearchTree.h"
using namespace std;

int main()
{
        BinaryTree Bitree;
        Bitree.insert(5);
        Bitree.insert(3);
        Bitree.insert(4);
        Bitree.insert(2);
        Bitree.insert(8);
        Bitree.insert(7);
        Bitree.insert(1);
        ElemType elem = 1;
        Bitree.find(elem);

        Bitree.printTree();
        Bitree.remove(2);
        Bitree.insert(6);
        Bitree.printTree();
        Bitree.insert(2);
        Bitree.remove(6);
        Bitree.insert(9);
        Bitree.insert(6);
        Bitree.printTree();
        Bitree.emptyTree();
        Bitree.printTree();
        return 0;
}