BiSortTree.h
#pragma once
#include<iostream>
using namespace std;
struct Binode
{
int key;
Binode* lchild, * rchild;
};
class BiSortTree
{
Binode* root;
void Insert(Binode*& ptr, int k);
Binode* Search(Binode* ptr, int k);
void Free(Binode* ptr);
public:
BiSortTree(int a[], int n);
~BiSortTree();
void Insert(int k);
void Search(int k);
};
BiSortTree::~BiSortTree()
{
Free(root);
}
void BiSortTree::Free(Binode* ptr)
{
if (ptr == NULL)
return;
Free(ptr->lchild);
Free(ptr->rchild);
}
BiSortTree::BiSortTree(int a[], int n)
{
root = NULL;
for (int i = 0; i < n; i++)
Insert(root, a[i]);
}
void BiSortTree::Insert(Binode*& ptr, int k)
{
if (ptr == NULL)
{
ptr = new Binode;
ptr->key = k;
ptr->lchild = ptr->rchild = NULL;
}
else
{
if (k < ptr->key)
Insert(ptr->lchild, k);
else if (k > ptr->key)
Insert(ptr->rchild, k);
}
}
void BiSortTree::Insert(int k)
{
Insert(root, k);
}
Binode* BiSortTree::Search(Binode* ptr, int k)
{
if (ptr == NULL)
return NULL;
else
if (ptr->key == k)
return ptr;
else if (k < ptr->key)
return Search(ptr->lchild, k);
else
return Search(ptr->rchild, k);
}
void BiSortTree::Search(int k)
{
Binode* re = Search(root, k);
if (re != NULL)
cout << "查找成功" << endl;
else
cout << "查找失败" << endl;
}
main.cpp
#include<iostream>
#include"BiSortTree.h"
using namespace std;
int Bisearch(int r[], int low, int high, int k)//二分查找
{
if (low > high)
return -1;
else
{
int mid = (high + low) / 2;
if (r[mid] == k)
return mid;
else
if (r[mid] < k)
return Bisearch(r, mid + 1, high, k);
else
return Bisearch(r, low, mid - 1, k);
}
}
void main()
{
cout << "请输入数组元素个数" << endl;
int n;
cin >> n;
int a[100];
cout << "输入数组元素" << endl;
for (int i = 0; i < n; i++)
cin >> a[i];
BiSortTree tree(a, n);
cout << "请选择查找方式" << endl;
cout << "1.二分查找" << endl;
cout << "2.二叉排序树查找" << endl;
cout << "3.退出系统" << endl;
int ab = 0, k = 0, low = 0, high = 0, j = 0;
high = n - 1;
while (1)
{
cout << "请选择查找方式或退出" << endl;
cin >> ab;
switch (ab) {
case 1:
cout << "请输入要二分查找的数据" << endl;
cin >> k;
j = Bisearch(a, low, high, k);
if (j == -1)
cout << "查找失败" << endl;
else
{
cout << "查找成功" << endl;
cout << "该数据是第" << j + 1 << "个数" << endl;
}
break;
case 2:
cout << "请输入要通过二叉排序树查找的数据" << endl;
cin >> k;
tree.Search(k);
break;
case 3:
cout << "已退出" << endl;
exit(0);
}
}
}