/***************************运行环境http://www.anycodes.cn/zh/原文件http://www.cnblogs.com/hanxi/archive/2012/08/18/2645929.html带注释的C++类版本BST二叉搜索树***************************/#ifndefBTREE_H_#defineBTREE_H_#include<cstdlib>#include<iostream>#include<iomanip>usingnamespacestd;template<classTreeDataType>classBSTree{private:classBSTNode{public:BSTNode*left;BSTNode*right;TreeDataTypedata;BSTNode():left(NULL),right(NULL){}BSTNode(TreeDataTypea_data):data(a_data),left(NULL),right(NULL){}};//节点声明typedefBSTNode*BSTNodePointer;BSTNodePointerm_root;public:BSTree():m_root(NULL){}~BSTree(){deleteNode(m_root);}boolisEmpty()const{returnm_root==NULL;}boolfind(constTreeDataType&a_data)const;voidinsert(constTreeDataType&a_data){insertAux(m_root,a_data);}voidremove(constTreeDataType&a_data);voidinorder(ostream&out)const{inorderAux(out,m_root);}voidgraph(ostream&out)const{graphAux(out,0,m_root);}protected:voiddeleteNode(BSTNodePointera_node);/*/删除节点和所有到子节点/*/voidinsertAux(BSTNodePointer&a_subRoot,constTreeDataType&a_data);voidinorderAux(ostream&out,BSTNodePointera_subRoot)const;voidgraphAux(ostream&out,inta_indent,BSTNodePointera_subRoot)const;voidfind2(constTreeDataType&a_data,bool&found,BSTNodePointer&a_locPtr,BSTNodePointer&a_parent)const;};/*/类模板声明结束/*/#endiftemplate<classTreeDataType>inlinevoidBSTree<TreeDataType>::deleteNode(BSTree<TreeDataType>::BSTNodePointera_node){/*/递归删除结点/*/if(a_node->left!=NULL){deleteNode(a_node->left);}elseif(a_node->right!=NULL){deleteNode(a_node->right);}elseif(a_node!=NULL){deletea_node;a_node=NULL;}}template<classTreeDataType>inlinevoidBSTree<TreeDataType>::insertAux(BSTree<TreeDataType>::BSTNodePointer&a_subRoot,constTreeDataType&a_data){/*/递归插入结点/*/if(a_subRoot==NULL){a_subRoot=newBSTree<TreeDataType>::BSTNode(a_data);}elseif(a_data<a_subRoot->data){insertAux(a_subRoot->left,a_data);}elseif(a_subRoot->data<a_data){insertAux(a_subRoot->right,a_data);}else{/*/不能有相同的结点/*/std::cerr<<"a_dataalreadyinthetree!\n";}}template<classTreeDataType>inlinevoidBSTree<TreeDataType>::inorderAux(ostream&out,BSTree<TreeDataType>::BSTNodePointera_subRoot)const{/*/LDR中序遍历/*/if(a_subRoot!=NULL){inorderAux(out,a_subRoot->left);//Lout<<a_subRoot->data<<"";//VinorderAux(out,a_subRoot->right);//R}}template<classTreeDataType>inlinevoidBSTree<TreeDataType>::graphAux(ostream&out,inta_indent,BSTree<TreeDataType>::BSTNodePointera_subRoot)const{/*/图表式打印树/*/if(a_subRoot!=NULL){graphAux(out,a_indent+8,a_subRoot->right);//Rout<<setw(a_indent)<<""<<a_subRoot->data<<endl;//VgraphAux(out,a_indent+8,a_subRoot->left);//L}}template<classTreeDataType>inlineboolBSTree<TreeDataType>::find(constTreeDataType&a_data)const{BSTree<TreeDataType>::BSTNodePointerlocPtr=m_root;boolfound=false;while(!found&&locPtr!=NULL){if(a_data<locPtr->data){locPtr=locPtr->left;}elseif(locPtr->data<a_data){locPtr=locPtr->right;}else{found=true;}}returnfound;}template<classTreeDataType>inlinevoidBSTree<TreeDataType>::find2(constTreeDataType&a_data,bool&found,BSTree<TreeDataType>::BSTNodePointer&a_locPtr,BSTree<TreeDataType>::BSTNodePointer&a_parent)const{/*/这里不仅要找还要找到p结点已便于后期删除找到的结点/*/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;}elseif(a_locPtr->data<a_data){a_parent=a_locPtr;a_locPtr=a_locPtr->right;}else{found=true;}}}template<classTreeDataType>inlinevoidBSTree<TreeDataType>::remove(constTreeDataType&a_data){boolfound=false;BSTree<TreeDataType>::BSTNodePointerx;//被删除的节点BSTree<TreeDataType>::BSTNodePointerparent;find2(a_data,found,x,parent);if(!found){std::cerr<<"a_dataisnotinthetree!\n";return;}if(x->left!=NULL&&x->right!=NULL)//节点有两个子女{//查找x的中续后继节点及其双亲节点BSTree<TreeDataType>::BSTNodePointerxSucc=x->right;parent=x;while(xSucc->left!=NULL)/*/在右中找最左的元素/*/{parent=xSucc;xSucc=xSucc->left;}x->data=xSucc->data;/*/替换要删除的结点数据/*/x=xSucc;/*/转向这个替死鬼/*/}BSTree<TreeDataType>::BSTNodePointersubTree=x->left;if(subTree==NULL)/*/看替死鬼的情况/*/{subTree=x->right;}if(parent==NULL){m_root=subTree;}elseif(parent->left==x){parent->left=subTree;/*/替死鬼的右做p的左/*/}else{parent->right=subTree;/*/替死鬼是p的右孩子，将右孩子做p的右孩子/*/}deletex;}/*/-----------文件分割线-------"BSTree.h"----------------#include"BSTree.h"#include<cstdlib>#include<iostream>usingnamespacestd;/*/inttest(){/*/数据准备inta[]/*/inta[]={1,3,5,7,9,2,4,6,8,-999};inti=0;BSTree<int>intBST;cout<<"ConstructingemptyBST\n";cout<<"BST"<<(intBST.isEmpty()?"is":"isnot")<<"empty\n";intnumber;for(;;){number=a[i++];if(number==-999)break;intBST.insert(number);}intBST.inorder(cout);cout<<endl;intBST.graph(cout);//测试findfor(i=0;;i++){cout<<"Itemtofind(-999tostop):";number=a[i];if(number==-999)break;boolfound=intBST.find(number);cout<<boolalpha<<found<<endl;}//测试removefor(i=0;;i++){cout<<"Itemtoremove(-999tostop):"<<endl;number=a[i];if(number==-999)break;intBST.remove(a[i]);intBST.graph(cout);cout<<endl;}intBST.inorder(cout);}voiduse(){BSTree<int>intBST;cout<<"ConstructingemptyBST\n";cout<<"BST"<<(intBST.isEmpty()?"is":"isnot")<<"empty\n";intnumber;for(;;){cout<<"Itemtoinsert(-999tostop):"<<endl;cin>>number;if(number==-999)break;intBST.insert(number);}intBST.inorder(cout);cout<<endl;intBST.graph(cout);//测试findfor(;;){cout<<"Itemtofind(-999tostop):";cin>>number;if(number==-999)break;boolfound=intBST.find(number);cout<<boolalpha<<found<<endl;}//测试removefor(;;){cout<<"Itemtoremove(-999tostop):";cin>>number;if(number==-999)break;intBST.remove(number);cout<<endl;intBST.graph(cout);cout<<endl;}intBST.inorder(cout);}intmain(){test();return0;}