BST数据结构

2022-08-01 04:35:32 第一文档网 [ 字体：小中大 ] [

阅读： ] [

说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。下载word有问题请添加QQ：admin处理，感谢您的支持与谅解。

【#第一文档网# 导语】以下是®第一文档网的小编为您整理的《BST数据结构》，欢迎阅读！
数据结构,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.dywdw.cn/d9e658fd1a5f312b3169a45177232f60dccce777.html