test.cpp

一些查找的程序

#include<iostream>
using namespace std;
#include"BST.h"


int Findsort(int sort,BSTNode<int> *p);
void ChangeTree( const BinarySearchTree<int> & p,BinarySearchTree<int> & q, int a[],int node);
int GetRootNumber(int a[],int node);



int main()
{   
	const int array = 100;
	int a[array];
	int suc = 1;
	int b = 0;
	int nodenum = 0;//记录二叉树的结点数 
	cout << "input an intergal array,end with -1" << endl;
	for(int i = 0;b != -1; i++)
	{   
		cin >> a[i];
		b = a[i];
	    
	}
	static BinarySearchTree<int> test;
	for(int n = 0; a[n] != -1; n++)
	{   
		suc = test.Insert(a[n]);
		nodenum ++;
		
	}
	test.SetInfo(test.Root);
	test.PrintInorder(test.Root);
	static BinarySearchTree<int> q;//用于构造
	ChangeTree(test,q,test.sort,nodenum);
   cout << ".....";
	
	return 0;

}


int Findsort(int sort,BSTNode<int> *p)
{
	if(sort == p->info +1)
		return p->data;
	else if(sort < p->info+ 1)
		return (Findsort(sort,p->left));
	else 
        return (Findsort((sort-p->info-1),p->right));

}

void ChangeTree(const BinarySearchTree<int> & p, BinarySearchTree<int> & q,int a[],int node){
    int sort1[100], sort2[100];
	int number = 0;
	number = GetRootNumber(a,node);
	int sec = q.Insert(a[number - 1]);
    for(int i = 0; i<number-1;i++)
		sort1[i] = a[i];
	for(int j = 0; j < node-number;j++)
		sort2[j] = a[number + j ];
	if(number - 1 != 0)
    ChangeTree(p,q,sort1,number-1);
	if(node - number != 0)
    ChangeTree(p,q,sort2,node-number);

}

int GetRootNumber(int a[],int node){

	int rec = 0;//作为余数
	int result = 0;
	int i = 1;
    while( node > result + i)
	{
		result += i;
		i *= 2;

	}
	i = i / 2;
	rec = node - result;
	if(rec > i)
		return ((result - 1)/2 + i + 1);
	else
		return ((result-1)/2 + rec + 1);
}