可以解决的问题
(1) 以回车(‘\n')为输入结束标志,输入数列L,生成一棵二叉排序树T;
(2) 对二叉排序树T作中序遍历,输出结果;
(3) 计算二叉排序树T查找成功的平均查找长度,输出结果;
(4) 输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历(执行操作2);否则输出信息“无x” 。
以下是主函数,其他内容见附件
//这是二叉排序树类BiSearchTree<T>的测试程序
#include "BiSearchTree.h"
#include "BiTreeLib.h"
template<class T>
void Visit(T item)
{
cout<<item<<" ";
}
void main(void)
{
BiSearchTree<int> searchTree;
int a[150];
int n ,c; //变量n 用于控制输入元素个数,c用于查找或删除操作时
float searchLen=0;
cout << "二叉排序树实现程序" << endl;
cout << " \n请输入二叉排序树数据元素的个数 "<< endl;
cin >>n;
cout << " 请输入数据元素 <注意!!:: 数据元素的个数> " << endl;
for(int b=0;b<n;b++)
{
cin >>a[b];
}
for(int i=0; i<n; i++)
searchTree.Insert(a[i]);
cout<<"初始建立的二叉排序树:"<<endl;
PrintVTree(searchTree.GetRoot());
char k='y';
while(k=='y'||k=='Y')
{
cout << "\n对二叉排序树执行的操作 || <1、插入一个数据,2、查找并删除一个数据> " << endl;
cin>>i;
switch(i)
{
case 1:i=1;
cout << "输入你想插入的数据元素 " << endl;
cin >>c;
searchTree.Insert(c);
cout<<endl<<"插入一个数据元素之后的二叉排序树:"<<endl;
PrintVTree(searchTree.GetRoot());
break;
case 2:i=2;
cout << "输入你想查找并删除的一个数据元素" << endl;
cin >>c;
searchTree.Delete(c);
cout<<endl<<"二叉排序树为:"<<endl;
PrintVTree(searchTree.GetRoot());
break;
}
cout<<endl;
cout << "\n 中序遍历的结果为:" << endl;
searchTree.InOrder(Visit);
for(i = 0; i < n ; i++)
{
searchLen = searchLen + searchTree.searchLen(a[i]);
}
cout << "\n平均查找长度searchLen=" << searchLen/n << endl ;
cout<<"please input Y or N to continue"<<endl;
cin>>k;
}
}
[此贴子已经被作者于2007-6-24 16:00:02编辑过]