問題描述利用二叉查找樹（BST）實現一個動態查找表基本要求使用二叉樹（BST）來實現。二叉樹使用鏈式結構（二叉鏈表）實現。實現BST的構建，查找兩個功能。一需求分析1．輸入的形式：輸入要存儲元素的個數n（正整數），n個元素的值（設為整數）和要查找元素的值；2．輸出的形式：輸出是否找到（查找成功\不成功）和查找時比較的次數（正整數）；3．程序所能達到的功能：要求輸入用戶設定個元素，再輸入要查找的元素，輸出是否找到和查找時比較的次數；4、測試數據輸入：5//BST的節點數請輸入數據：4354321257//五個數據請輸入查找數：54//查找54輸出：查找成功2//返回成功和查找時比較的次數請輸入查找數：12//查找12輸出：查找成功3//返回成功和查找時比較的次數請輸入查找的數：50//查找50輸出：查找不成功3//返回成功和查找時比較的次數二概要設計抽象數據類型的定義BST，二叉查找樹，先定義一個二叉樹節點，然后實現二叉查找樹的功能。數據對象：整數數據關系：數據元素屬于同一集合，是二叉樹，如果對其做中序遍歷呈遞增序列基本操作：遍歷，二叉樹的構建，查找，插入算法的基本思想將輸入的BST的元素用插入的方法存進BST中（由于BST中任何結點的左孩子小于該節點，右孩子大于該節點，所以用遞歸方法比較插入）。判斷輸入要查找的元素是否在BST中（遞歸比較要查找的元素與當前元素的值的大小，若小于當前值，則查找其左子樹；若大于，則查找其右子樹），若在，則輸出位置；若不在，則插入到BST中，并輸出其位置程序的流程：程序由三個模塊組成：（1）輸入模塊：輸入二叉查找樹的元素個數、元素的值，以及要查找的數（2）查找模塊：判斷該元素是否在二叉查找樹中，若未找到，則插入到二叉查找樹中。（3）輸出模塊：輸出是否找到。若找到，則輸出位置；若未找到，則輸出插入的位置。三詳細設計（1）物理數據類型因為要實現一個動態查找表，對一個數進行查找，用線性表實現所用的時間代價比較高，而用二叉查找表來實現的話時間代價顯劇較低，故可以構建一個二叉查找樹，來實現動態查找。（2）算法的具體步驟BST的構建偽代碼為：初始化BST，調用插入函數，用for循環使得輸入的元素一個一個以插入的形式存入BST中BSTreeInitBST(intn){//輸入一個結點序列，建立一棵二叉排序樹，將根結點指針返回BSTreeT=NULL；//初始時T為空樹intkey；for(inti=0;i<n;i++){cin>>key；//讀入一個關鍵字InsertBST(&T，key)；//將key插入二叉排序樹T}//存入n個元素到BST中returnT；//返回建立的二叉排序樹的根指針}//BSTree2、BST的查找設計和偽代碼為：若BST為空或者要查找的元素就是BST當前的元素值key，返回該樹，即若T為空，查找失敗；否則成功，返回找到的結點位置；若輸入的查找元素小于BST當前的元素值，則以遞歸的形式在左子樹中繼續查找；若輸入的查找元素大于BST當前的元素值，則以遞歸的形式在右子樹中繼續查找。BSTNode*SearchBST(BSTreeT，intkey){//在二叉排序樹T上查找關鍵字為key的結點，成功時返回該結點位置，否則返回NULLif(T==NULL||key==T->key)//遞歸的終結條件{returnT；//T為空，查找失敗；否則成功，返回找到的結點位置}if(key<T->key)returnSearchBST(T->lchild，key)；//在左子樹中查找elsereturnSearchBST(T->rchild，key)；//繼續在右子樹中查找}//SearchBST3、BST的插入偽代碼：定義BST臨時指針p和temp；P指向T，構建temp，使得其根節點值為要查找的元素，左右孩子為空。若要查找的BST為空，則插入元素為根節點；若要插入的元素小于當前元素，則被插結點為左孩子，返回TRUE；若要插入的元素大于當前元素，則被插結點為右孩子，返回TRUE。StatusinsertBST(BSTreeT,inte){BSTree*p=NULL,*temp=NULL;temp=(BSTree*)malloc(sizeof(BSTree));temp->key=e;temp->lchild=NULL;temp->rchild=NULL;if(temp==NULL)returnFALSE;if(T==NULL)T=temp;//被插結點為新的根節點;p=T;if(e<p->key){p->lchild=temp;//被插結點temp為左孩子returnTRUE;}if(e>p->key){p->rchild=temp;//被插結點temp為右孩子returnTRUE;}}（3）算法的時空分析由于二叉樹的查找的時間代價為，而二叉樹的插入的時間代價為，故時間代價為（4）輸入和輸出的格式輸入格式：在字符界面上輸入一個數字表示節點（數據）的個數。請輸入數據個數：輸入一個數字//回車結束請輸入查找數據：//輸入要查找的總的數據，回車表示結束輸出格式：每當輸入一個暑假，就輸出查找成功或不成功，并且后面有數字表示查找的次數，例如：34//查找34，輸出：查找成功1//表示查找時比較的次數。（5）實驗結果截圖（6）實驗代碼：#include<iostream>#include<stdlib.h>usingnamespacestd;template<classT>classBtree{private:typedefstructtree{ Tdata; tree*left,*right,*father; };boolDelete(tree*);inti;//記錄比較次數 tree*&search(tree*t,Tkey,tree*f,tree*&p){ if(!t){ p=f; cout<<"查找的次數"<<i<<endl; i=0; returnp; } else{ i++;//計數器加1 if(key==t->data){ p=t; cout<<"查找成功!"<<"查找的次數:"<<i<<endl; i=0; p=false; returnp;} else{ if(key<t->data)returnsearch(t->left,key,t,p); elsereturnsearch(t->right,key,t,p); } } }public:tree*root;Btree() { i=0;root=NULL;}voidcreate_Btree(T);voidinorder(tree*);//中序遍歷voiddisplay(){cout<<endl<<"中序遍歷序列:"<<endl;inorder(root);cout<<endl;}boolinsert(tree*&,T);/*這個函數和search（）函數一起使用，先遍歷該二叉樹，如果沒有指定的結點則插入該結點*/};template<classT>voidBtree<T>::create_Btree(Tx){tree*newnode=newtree;newnode->data=x;newnode->right=newnode->left=NULL;if(root==NULL)root=newnode;else{tree*back;tree*current=root;while(current!=NULL){back=current;if(current->data>x)current=current->left;elsecurrent=current->right;}if(back->data>x){back->left=newnode;newnode->father=back;}else{back->right=newnode;newnode->father=back;} }}template<classT>voidBtree<T>::inorder(tree*temp){//這是中序遍歷二叉樹，采用了遞歸的方法。if(temp!=NULL){inorder(temp->left);cout<<temp->data<<"";inorder(temp->right); }}template<classT>boolBtree<T>::Delete(tree*p){tree*q;if(!p->right){q=p;p=p->left;deleteq;} elseif(!p->left){q=p;p=p->right; deleteq;} else { tree*s;q=p;s=p->left;while(s->right) { q=s;s=s->right; }p->data=s->data;if(q!=p)q->right=s->left;elseq->left=s->left;deletes;} returntrue;}template<classT>boolBtree<T>::insert(tree*&t,Tkey){ tree*temp=t;tree*p;if(search(temp,key,NULL,p)) { cout<<"查找不成功!"<<endl;tree*s=(tree*)malloc(sizeof(tree));s->data=key;s->left=s->right=NULL;if(!p)temp=s;elseif(key<p->data)p->left=s;elsep->right=s;returntrue;} elsereturnfalse;}intmain(){Btree<int>T; intn=0,data=0;charkey='Y'; cout<<"請輸入BST中數的個數:"; cin>>n;if(n<=0) cout<<"輸入錯誤"<<endl;else{ cout<<"請輸入"<<n<<"個數:"<<endl;for(inti=0;i<n;i++) { cin>>data;T.create_Btree(data); }T.display(); while(key!='n'||key!