二叉搜索树的基本操作二.实验内容设在一棵二叉搜索树的每个结点的data域中,含有关键字key域和统计相同关键字元素个数的

二叉搜索树的基本操作
二.实验内容
设在一棵二叉搜索树的每个结点的data域中,含有关键字key域和统计相同关键字元素个数的count域.当向该树插入一个元素时,若树中已有相同关键字值的结点,则使该结点的count域值增1,否则由该元素值生成一个新结点插入到该树中,并使其count域置为1.当向该树删除一个元素时,若树中该元素结点的count域值大于1,则使该结点的count域值减1,否则（count域值等于1）删除该结点.请编写程序实现该二叉搜索树的下述基本操作：
初始化该二叉搜索树void InitBSTree(BTreeNode *&bst);
以广义表形式输出该二叉搜索树（每个结点输出内容包括关键字值与相同元素个数值）void PrintBSTree(BTreeNode *bst);
插入一个元素到该二叉搜索树（用非递归算法实现） void Insert (BTreeNode *&bst,ElemType item);
从二叉搜索树中删除某个元素（用非递归算法实现） int Delete (BTreeNode *&bst ,ElemType item).
求该二叉搜索树的最大关键字值（用非递归算法实现）ElemType MaxBSTree(BTreeNode *bst).
把二叉搜索树的结构定义及基本操作实现函数存放在文件BSTree.h中.
建立主程序文件test5.cpp,在主函数main()中通过调用BSTree.h中的函数进行测试.提示：可以在主函数中首先初始化二叉搜索树；然后从键盘输入数据,通过循环调用插入算法建立二叉搜索树；再以广义表形式输出该二叉搜索树；输出二叉搜索树中的最大结点值；最后调用删除算法删除某元素,并输出删除后的二叉搜索树.

哈哈,居然有人来提问了,城院的 我刚奋斗了2小时做了下,你看看对不?Test5.cpp:#include <iostream.h>#include <stdlib.h>typedef double ElemType;#define Maxsize 100#include "BSTree.h"void main(){ int i,n; ElemType x; ElemType a[Maxsize]; BTreeNode *bst;    InitBSTree(bst);    cout<<"请输入你所要测试的二叉搜索树的结点的个数:";    cin>>n;    cout<<"请输入你要测试的二叉搜索树:"<<endl;    for(i=0;i<n;i++){  cin>>a[i];   } CreateBSTree(bst,a,n);    cout<<"你输入的二叉搜索树的广义表形式为:";    PrintBSTree(bst);    cout<<endl; cout<<"输入一个待插入结点的整数值:"; cin>>x; Insert(bst,x); cout<<"插入结点后的二叉搜索树的广义表形式为:"; PrintBSTree(bst); cout<<endl; cout<<"输入一个待删除结点的值:"; cin>>x;    if(Delete(bst,x)) cout<<"删除元素"<<x<<"成功!"<<endl; else cout<<"删除元素"<<x<<"失败!"<<endl; PrintBSTree(bst); cout<<endl; cout<<"该二叉搜索树中的最大值为:"<<MaxBSTree(bst)<<endl;}BSTree.h:struct BTreeNode{ ElemType data; ElemType count;    BTreeNode *left;    BTreeNode *right;};void InitBSTree(BTreeNode *&bst)           //初始化二叉搜索树{ bst=NULL; }void PrintBSTree(BTreeNode *bst)           //以广义表形式输出二叉搜索树{ if(bst!=NULL){  cout<<bst->data;  cout<<'['<<bst->count<<']';  if(bst->left!=NULL||bst->right!=NULL){   cout<<'(';   PrintBSTree(bst->left);      if(bst->right!=NULL)    cout<<',';   PrintBSTree(bst->right);   cout<<')';  } }}void Insert (BTreeNode *&bst, ElemType item){ BTreeNode*t=bst,*parent=NULL; while(t!=NULL){  parent=t;  if(item<t->data) t=t->left;    else if(item>t->data) t=t->right;  else{   t->count++;   break;  } } if((t==NULL)||item!=parent->data){  BTreeNode*p=new BTreeNode;     p->data=item;     p->count=1;     p->left=p->right=NULL;     if(parent==NULL) bst=p;     else if(item<parent->data) parent->left=p;     else parent->right=p; }}void CreateBSTree(BTreeNode *&bst, ElemType a[], int n)       //建立二叉搜索树（用非递归算法实现){ bst=NULL;  for(int i=0;i<n;i++)    Insert(bst,a[i]); }bool Delete (BTreeNode *&bst , ElemType item){ BTreeNode *t=bst,*parent=NULL,*m,*n;  while((t!=NULL)&&(t->data!=item)){  if(item==t->data) break;        else{   if(item<t->data){    parent=t;    t=t->left;   }   else{    parent=t;    t=t->right;   }  } } if(t->count>1){  t->count--;  return true;   } else if(t==NULL){  cout<<"没有找到待删除结点!"<<endl;  return false; }    else{  if((t->left==NULL)&&(t->right==NULL)){   if(t==bst)    bst=NULL;   else{    if(t==parent->left)     parent->left=NULL;    else     parent->right=NULL;   }  }  else if((t->left==NULL)||(t->right==NULL)){   if(t==bst){    if(t->left==NULL)                                                    bst=t->right;                                                    else                   bst=t->left;   }   else{    if((t==parent->left)&&(t->left!=NULL))     parent->left=t->left;                                        else if((t==parent->left)&&(t->right!=NULL))                           parent->left=t->right;    else if((t==parent->right)&&(t->left!=NULL))                           parent->right=t->left;                                    else if((t==parent->right)&&(t->right!=NULL))                          parent->right=t->right;   }  }  else{   if((t->left!=NULL)&&(t->right!=NULL)){    m=t;                n=t->left;                                                 while(n->right!=NULL){     m=n;                    n=n->right;                }                t->data=n->data;                                            if(m==t)     t->left=n->left;                else                    m->right=n->left;                t=n;   }  }    free(t); return true; }}ElemType MaxBSTree(BTreeNode *bst)           //求二叉搜索树的最大结点值（用非递归算法实现）{ ElemType max;    if(bst==NULL){  cout<<"该二叉搜索树为空!"<<endl;        exit(1); } max=bst->data;    while(bst!=NULL){  if(max<bst->data)   max=bst->data;  bst=bst->right; } return max;}你试试吧,应该对的,选我做答案哈~