#include
int data[Max];
ifstream infile;
infile.open( "data.txt");
for( int i = 0; i < n; i++){
infile>>data[i]; infile.seekg(1);
}
infile.close();
二分查找代码和索引查找都十分简单，自己写吧。
稍困难的二叉排序树实现代码如下，在VC6.0环境下编译通过：
#include
using namespace std;
typedef struct node{
int key;
int data;
struct node * lchild, * rchild;
}BSTNode;
class BST{
private:
void del( BSTNode * &);
void del2( BSTNode *, BSTNode * &);
public:
BSTNode * iroot;
BST();
bool Add( BSTNode * &, int);
bool Del( BSTNode * &, int);
bool Destroy();
bool Find( BSTNode *, int);
}bst;;
BST::BST(){
iroot = NULL;
}
bool BST::Del( BSTNode * &_root, int _key){
if( ! _root){
cout << "Del Fail" << endl;
return false;
}else{
if( _key == _root->data){
cout << "Found, Start del" << endl;
del( _root); //here!
return true;
}else if( _key < _root->data){
cout << "Turn left when del" << endl;
return Del( _root->lchild, _key);
}else{
cout << "Turn right when del" << endl;
return Del( _root->rchild, _key);
}
}
}
void BST::del( BSTNode * &_del){
BSTNode * q;
if( ! _del->lchild){
cout << "no lchild, del " << _del->data << endl;
q = _del;
cout << "地址是:" << bst.iroot->lchild << endl;
_del = _del->rchild;//没有对bst.iroot->lchild赋值，但是它真的变了。
//写代码的一个技巧：这里的_del实际上相当于_root->lchild(就是这样传值过来的)
//也就是说，_del里面实际上包含了要删除的节点的双亲结点！
//实际上是像 root->lchild->rchild->lchild....->lchild这样的一长串。
//我们这里是 root->lchild
//如果删除85，则为 root->lchild->rchild。
//So, amazing......
cout << "地址是:" << bst.iroot->lchild << endl;
free( q);
}else if( ! _del->rchild){
cout << "no rchild, del " << _del->data << endl;
q = _del;
_del = _del->lchild;
free( q);
}else{
cout << "both children exist, del " << _del->data << endl;
del2( _del, _del->lchild);
}
}
void BST::del2( BSTNode * p, BSTNode * &r){
BSTNode * q;
if( r->rchild){
cout << "bad" << endl;
del2( p, r->rchild);
}else{
cout << "bad2" << endl;
p->key = r->key;
q = r;
r = r->lchild;
free( q);
}
}
bool BST::Add( BSTNode * &_root, int _key){
if( ! _root){
_root = new BSTNode; _root->data = _key; _root->lchild = _root->rchild = NULL;
cout << "Add " << _key << endl;
return true;
}else if( _key == _root->data){
cout << "Add Fail: the same data already exists" << endl;
return false;
}else if( _key < _root->data){
cout << "Turn left when Add" << endl;
return Add( _root->lchild, _key);
}else{
cout << "Turn right when Add" << endl;
return Add( _root->rchild, _key);
}
}
bool BST::Find( BSTNode * _root, int _aim){
if( ! _root){
cout << "Find Fail: Null tree" << endl;
return false;
}else if( _root->data == _aim){
cout << "Found " << _aim << endl;
return true;
}else if( _root->data < _aim){
cout << "Turn right when Search" << endl;
return Find( _root->rchild, _aim);
}else{
cout << "Tuen left when Search" << endl;
return Find( _root->lchild, _aim);
}
}
int main(){
bst.Find(bst.iroot, 90);
bst.Add( bst.iroot, 90);
bst.Find( bst.iroot, 90);
bst.Add( bst.iroot, 80);
bst.Find( bst.iroot, 80);
bst.Add( bst.iroot, 85);
bst.Find( bst.iroot, 85);
bst.Find( bst.iroot, 80);
bst.Del( bst.iroot, 80);
system("pause");
}
