用二叉链表实现二叉查找树(二)
</pre><pre code_snippet_id="367806" snippet_file_name="blog_20140528_2_6875764" name="code" class="cpp">/* 二叉查找树的链表实现: 以及三种遍历方式,删除节点; 查找节点; author:天下无双 Date:2014-5-28 Version:3.0 */ #include <iostream> #include <string> typedef int T;//树内节点的数据类型 using namespace std; class BiTree { private: struct BiNode{ T data; BiNode *lchild,*rchild; BiNode(T d){ data=d; lchild=nullptr; rchild=nullptr; } }; BiNode *root; public: BiTree(){ //root=root->rchild=root->rchild=nullptr; root=nullptr; } ~BiTree(){ } //使用递归创建二叉树 //以二叉排序树的规则建立 //指针的引用写法(推荐使用) bool addBiNode(BiNode *&nodeRoot,T d){ if(nodeRoot==nullptr){ BiNode *p=new BiNode(d); nodeRoot=p; cout<<p->data<<" insert success!"<<endl; return true; }else if(nodeRoot!=nullptr&&d<nodeRoot->data){ //往左子树递归 addBiNode(nodeRoot->lchild,d); }else if(nodeRoot!=nullptr&&d>(nodeRoot)->data){ //往右子树递归 addBiNode(nodeRoot->rchild,d); }else{ cout<<"树中已有该数据"<<endl; return false; } } BiNode *&getRoot(){//返回根指针的引用 return root; } BiNode *getPtrToRoot()const{ return root; } bool Traverse(const BiNode *b,string type)const{ if(type=="PreOrderTraverse"){ cout<<"\n先序遍历的结果为:"<<endl; PreOrderTraverse(b); return true; }else if(type=="InOrderTraverse"){ cout<<"\n中序遍历的结果为:"<<endl; InOrderTraverse(b); return true; }else if(type=="PostOrderTraverse"){ cout<<"\n后序遍历的结果为:"<<endl; PostOrderTraverse(b); return true; }else{ cout<<"遍历类型无效!"<<endl; return false; } } //查找二叉树中是否存在该值 bool Search(BiNode *&nodeRoot,T d){ if(nodeRoot==nullptr) return false; else{ if(nodeRoot->data==d){ return true; }else if(nodeRoot->data<d){ return Search(nodeRoot->rchild,d); }else return Search(nodeRoot->lchild,d); } } //递归查找确定该节点所在位置 bool DeleteBST(BiNode *&nodeRoot,T d){ if(nullptr==nodeRoot)//当该节点为空 return false; else{ if(nodeRoot->data==d){// return Delete(nodeRoot); //Delete(nodeRoot); }else if(nodeRoot->data<d){ return DeleteBST(nodeRoot->rchild,d); //DeleteBST(nodeRoot->rchild,d); }else return DeleteBST(nodeRoot->lchild,d); //DeleteBST(nodeRoot->lchild,d); } } protected: //删除操作 //删除相应节点 //如果该节点是叶子节点,即该节点左右孩子均为空,则只需将父节点指向该节点 //指针置空即可 //如果仅有左孩子或者仅有右孩子,则将对应节点上移 //nodeRoot为要删除的节点 //若既有左孩子,又有右孩子,看下面的注释 bool Delete(BiNode *&nodeRoot){ //如果要删除的节点右子树为空,则只需移动左子树 if(nullptr==nodeRoot->rchild){ BiNode *temp=nodeRoot; nodeRoot=nodeRoot->lchild; delete temp; return true; }else if(nullptr==nodeRoot->lchild){//若左子树空则移动右子树 BiNode *temp=nodeRoot; nodeRoot=nodeRoot->rchild; delete temp; return true; }else{//左右子树均非空 //将该节点的左子树的最右边的右节点数据和该节点互换 //或者是将该节点右子树最左端的左节点和该节点数据互换 //我这里是选择左子树的最右节点 BiNode *temp=nodeRoot->lchild;//temp为该节点左子树的根节点 BiNode *preTemp=nodeRoot->lchild; while(nullptr!=temp->rchild){ preTemp=temp;//令preTemp指向最右节点的前驱 temp=temp->rchild;//一直寻找最右的右节点 //temp指向待删除的节点 } //这时候temp指向最右的一个节点 nodeRoot->data=temp->data;//交换数据,由于二叉查找树的特性,交换后依旧保持该特性。 /* 50 30 70 20 倘若删除的是50,则preTemp=temp=&30 */ if(temp!=preTemp) preTemp->rchild=temp->lchild;//令前驱节点的右孩子变成被删除节点的左孩子 else nodeRoot->lchild=temp->lchild; delete temp;//删除右节点 return true; } return false; } //T如果是结构或者类类型,需重载<<运算符 void Visit(const BiNode *r)const{ cout<<r->data<<" "; } //利用递归遍历,三种遍历原理都是一样的 //前序遍历,先根遍历 void PreOrderTraverse(const BiNode *nodeRoot)const{ if(nodeRoot!=nullptr) Visit(nodeRoot); if(nodeRoot->lchild!=nullptr) PreOrderTraverse(nodeRoot->lchild); if(nodeRoot->rchild!=nullptr) PreOrderTraverse(nodeRoot->rchild); } //中根遍历 void InOrderTraverse(const BiNode *nodeRoot)const{ if(nodeRoot->lchild!=nullptr) InOrderTraverse(nodeRoot->lchild); if(nodeRoot!=nullptr)//当该点左子树空时 Visit(nodeRoot); if(nodeRoot->rchild!=nullptr) InOrderTraverse(nodeRoot->rchild); } //后序遍历 void PostOrderTraverse(const BiNode *nodeRoot)const{ if(nodeRoot->lchild!=nullptr) PostOrderTraverse(nodeRoot->lchild); if(nodeRoot->rchild!=nullptr) PostOrderTraverse(nodeRoot->rchild); if(nodeRoot!=nullptr) Visit(nodeRoot); } };
感觉对于递归中的return还是有点不太清晰。
什么时候该用,什么时候不该用也不太清晰。
测试代码
<pre name="code" class="cpp">#include "bit4.cpp" int main() { BiTree b; //b.addBiNode(&b.root,50);//设立根节点值//二级指针写法 b.addBiNode(b.getRoot(),50);//指针的引用写法 int i; int arr[9]={30,40,35,27,100,90,110,95,-999}; for(int j=0;j<9;j++) { i=arr[j]; if(i==-999) break; b.addBiNode(b.getRoot(),i); } b.Traverse(b.getPtrToRoot(),"PreOrderTraverse"); b.Traverse(b.getPtrToRoot(),"InOrderTraverse"); b.Traverse(b.getPtrToRoot(),"PostOrderTraverse"); while(true) { int k; cout<<"\n输入要查找的值:"<<endl; cin>>k; if(b.Search(b.getRoot(),k)) cout<<"OK"<<endl; else cout<<"NO"<<endl; } cin.get(); system("pause"); return 0; }