BST数据结构
说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。
#include #include using namespace std; //BST结点类 class Node{ private: int data; Node* left; Node* right; public: Node(int data,Node* left=NULL,Node* right=NULL){ this->data=data; this->left=left; this->right=right; } void setValue(int elem){ data=elem; } int value(){ return data; } void setLeft(Node* p){ left=p; } Node*& leftchild(){ return left; } void setRight(Node* p){ right=p; } Node*& rightchild(){ return right; } bool isLeaf(){ if(left==NULL&&right==NULL) return true; return false; } }; //BST插入函数 void insert(Node* subroot,int elem){ if(elemvalue()){ if(subroot->leftchild()==NULL){ Node* temp=new Node(elem); subroot->setLeft(temp); return; } insert(subroot->leftchild(),elem); } else if(elem>subroot->value()){ if(subroot->rightchild()==NULL){ Node* temp=new Node(elem); subroot->setRight(temp); return; } insert(subroot->rightchild(),elem); } } //BST构建函数 void creatBST(Node*& subroot,int data[],int n){ for(int i=0;i insert(subroot,data[i]); }
bool find(Node* subroot,int elem){ if(subroot==NULL) return false; if(elem==subroot->value()) return true; if(elemvalue()) return find(subroot->leftchild(),elem); if(elem>subroot->value()) return find(subroot->rightchild(),elem); }
//BST查找函数，查找特定结点是否存在并保存比较次数 bool find(Node* subroot,int elem,int& count){ if(subroot==NULL) return false; if(elem==subroot->value()){ count++; return true; } if(elemvalue()){ count++;
return find(subroot->leftchild(),elem,count); } if(elem>subroot->value()){ count++; return find(subroot->rightchild(),elem,count); } }
//重载的BST查找函数，查找特定结点是否存在并保存指向该结点的指针 bool find(Node* subroot,int elem,Node*& temp){ if(subroot==NULL) return false; if(elem==subroot->value()){ temp=subroot; return true; } if(elemvalue()){ return find(subroot->leftchild(),elem,temp); } if(elem>subroot->value()){ return find(subroot->rightchild(),elem,temp); } }
//BST查找函数，查找特定结点是否存在 Node* findfather(Node* subroot,Node* son){ if(son==subroot) return NULL; if(subroot->leftchild()==son||subroot->rightchild()==son) return subroot; if(find(subroot->leftchild(),son->value())) return findfather(subroot->leftchild(),son); if(find(subroot->rightchild(),son->value())) return findfather(subroot->rightchild(),son); }
//查找并删除BST中值最小的结点，返回其值 int deletemin(Node*& subroot){ if(subroot->leftchild()==NULL){ Node* temp=subroot; int data=subroot->value(); subroot=subroot->rightchild(); delete temp; return data;
} Node* father=subroot; Node* min=father->leftchild(); while((min->leftchild())!=NULL){ father=min; min=min->leftchild(); } int data=min->value(); father->setLeft(min->rightchild()); delete min; return data; }
//从BST中删除一个结点
Node* remove(Node* subroot,int elem){ Node* temp; if(!find(subroot,elem,temp)){ cout<<"不存在该结点！"< return subroot; } if(temp->leftchild()==NULL){ if(temp==subroot){ subroot=subroot->rightchild(); delete temp; return subroot; } Node* father=findfather(subroot,temp); if(father->rightchild()==temp) father->setRight(temp->rightchild()); else father->setLeft(temp->rightchild()); delete temp; return subroot; } if(temp->rightchild()==NULL){ if(temp==subroot){ subroot=subroot->leftchild(); delete temp; return subroot; } Node* father=findfather(subroot,temp); if(father->rightchild()==temp) father->setRight(temp->leftchild()); else
father->setLeft(temp->leftchild()); delete temp; return subroot; } temp->setValue(deletemin(temp->rightchild())); return subroot; }
//中序遍历BST，升序输出结点值 void print(Node* subroot){ if(subroot==NULL) return; print(subroot->leftchild()); cout<value()<<" "; print(subroot->rightchild()); return; }
//内存释放函数
void clear(Node* subroot){ if(subroot==NULL) return; clear(subroot->leftchild()); clear(subroot->rightchild()); delete subroot; return; }
int main(){ int sel;//对所有的操作进行选择 int data[100]; //保存输入的数据 int temp; int n; //数据的个数 int k=0; int count=0; bool flag=true; while(flag){ //循环实现多组测试数据的输入 cout<<"现在进行第"<<++k<<"组测试..."< //1、输入数据 cout<<"建立BST"< cout<<"请输入BST的结点个数："; cin>>n; cout<<"请输入"<个整数：";
for(int i=0;i cin>>data[i]; //2、建立一颗BST（二叉查找树） Node* root=new Node(data[0]); creatBST(root,&data[1],n-1); //中序遍历BST cout<<"中序遍历该BST的结果为："; print(root); cout<
loop:cout<<"请按照下面进行功能选择:"< cout<<"1--查找。。2--插入。。3--删除。。4--返回。。"< //3、实现BST的查找功能 cin>>sel; switch(sel){//"----------------------------------------------------" case 1: cout<<"实现BST的查找功能"< cout<<"请输入要查找的数："; cin>>temp; // int count=0; if(find(root,temp,count)){ cout<<"查找比较次数为："< cout<<"查找结果："; cout<<"查找成功！ "< } else{ cout<<"查找比较次数为："< cout<<"查找结果："; cout<<"查找失败！ "< } break; //4、实现插入功能 case 2: cout<<"实现BST的插入功能"< cout<<"输入要插入结点的值："< cin>>temp; insert(root,temp); cout<<"插入后的结果为："; print(root); cout< break;
//5、实现BST的删除功能 case 3: cout<<"实现BST的删除功能"< cout<<"输入要删除结点的值："; cin>>temp; root=remove(root,temp); cout<<"删除后的结果为："; print(root); cout< break; default: goto loop; } //6、让用户选择是否继续测试 char ch[5]; cout<<"是否继续下一组测试："; cin>>ch; if(!strcmp(ch,"yes")) flag=true; else flag=false; if(flag) cout< //7、释放内存 clear(root); } return 0; }
本文来源：https://www.wddqw.com/doc/d9e658fd1a5f312b3169a45177232f60dccce777.html