C++写一个折半查找二叉树的判定树。能看出树形状。

/**
@file binsearch.cpp
@author (c) 2005 Zbigniew Jerzak (after Programming Pearls by Jon Bentley and C++ Language by Bjarne Stroustrup)

@brief Illustrates the use of assertions when using the C++ language

Assertions regarding binary search:

1. Sorted array[0..n-1]
2. We search for an element t
3. n>=0
4. array[0] <= array[1] <= ... <= array[n-1]
5. iff n==0 array is empty
6. Datatypes of t and array elements are the same
7. The return value is stored in variable p
8. iff p=-1 elemet t was not found in array[0..n-1] otherwise
9. 0 <= p <= n-1 && t=array[p]
*/

#include
#include

using namespace std;

#define INFO(str) str, __FILE__, __LINE__

/**
@brief Asserts using exceptions.

@returns Throws an exception X is the expression expr is not
true. No action is taken otherwise. Executes only
if the debug mode is set.
*/
template
inline void Assert(T expr, X x)
{
#ifndef NDEBUG
if(!expr) throw x;
#endif //NDEBUG
}

/**
@brief the basic exception class, to be subclassed
*/
class CException
{
public:
CException(string s, char* f, int l) : _s(s), _f(f), _l(l) {};
string err() const {
ostringstream stm;
stm << _l;
return _s + " [File: " + _f + "; Line: " + stm.str() + "]";
}
private:
string _s;
string _f;
int _l;
};

/**
@brief Thrown when the precondition is violated
*/
class CPreconditionException : public CException {
public:
CPreconditionException(string s, char* f, int l) : CException(s, f, l) {};
};

/**
@brief Thrown when the invariant is violated
*/
class CInvariantException : public CException {
public:
CInvariantException(string s, char* f, int l) : CException(s, f, l) {};
};

/**
@brief Thrown when the precondition is violated
*/
class CPostconditionException : public CException {
public:
CPostconditionException(string s, char* f, int l) : CException(s, f, l) {};
};

/**
@brief retuirns the index of the element t in array

@param array - the sorted array in which to find t
@param t - the element to find
@param n - the size of the array

@return Index of the element t in the array. If not found, returns -1.
*/
template
class CBinarySearch
{
public:
//c'tor & d'tor
CBinarySearch() {}
~CBinarySearch() {}

//array manipulation
int binsearch(const T *array, const T t, const int n) const;
void initarray(T *array, const int n, const int f, const int s) const;

//assertions related
class CAssertionException : public CException {
public:
CAssertionException(string s, char* f, int l) : CException(s, f, l) {};
};

void sortedEx(const T *array, const int n) const;
int sorted(const T *array, const int n) const;
int mustbe(const int lower, const int upper, const T *array, const T t) const;
};

/**
@brief Verifies that a value t is in the range of array
*/
template
inline int CBinarySearch::mustbe(const int lower, const int upper, const T *array, const T t) const
{
return(array[lower] <= t && t <= array[upper]);
}

/**
@brief returns the index of the element t in array

@param array - the sorted array in which to find t
@param t - the element to find
@param n - the size of the array

@return Index of the element t in the array. If not found, returns -1.
*/
template
inline int CBinarySearch::binsearch(const T *array, const T t, const int n) const
/**
precondition:
array[0] <= array[1] <= ... <= array[n-1]

postcondition:
p == -1 => t not found in array
0 <= p <= n => array[p] == t

This constitutes a contract -- hence we call this
programming/design by contract.

DBC advocates writing the assertions first.
*/

{
const string vpre = "Violated Precondition";
const string vpst = "Violated Postcondition";
const string vinv = "Violated Invariant";

/* Make sure the search makes sense */
if(n<1 || array[0] > t || t > array[n-1])
return -1;

/* precodition 2 variants*/
#ifndef NDEBUG
sortedEx(array, n);
#endif //NDEBUG
//Assert(sorted(array, n), new CPreconditionException(INFO(vpre)));

int lower=0;
int upper=n-1;

Assert( mustbe(lower, upper, array, t), new CInvariantException(INFO(vinv)));

int middle=-1;

while (lower <= upper)
{
Assert( lower <= upper && mustbe(lower, upper, array, t), new CInvariantException(INFO(vinv)));

//Assert( middle != ((lower + upper) / 2), new CInvariantException(INFO(vinv)));
middle = (lower + upper) / 2;

Assert( lower <= middle && middle <= upper && mustbe(lower, upper, array, t), new CInvariantException(INFO(vinv)));

if(array[middle] < t)
{
Assert( mustbe(middle+1, upper, array, t), new CInvariantException(INFO(vinv)));

lower = middle;

Assert( mustbe(lower, upper, array, t), new CInvariantException(INFO(vinv)));
}
else if (array[middle] == t)
{
Assert( array[middle] == t, new CPostconditionException(INFO(vpst)));
return middle;
}
else /* array[middle] > t*/
{
Assert( mustbe(lower, middle-1, array, t), new CInvariantException(INFO(vinv)));
upper = middle - 1;
Assert( mustbe(lower, upper, array, t), new CInvariantException(INFO(vinv)));
}

Assert( mustbe(lower, upper, array, t), new CInvariantException(INFO(vinv)));
}

Assert( lower > upper && mustbe(lower, upper, array, t), new CPostconditionException(INFO(vpst)));
/* t not in array */
return -1;
}

/**
@brief Verifies whether the array is sorted

@param array - the array to verify
@param n - array size

@return 1 if array is sorted, 0 otherwise.
*/
template
inline int CBinarySearch::sorted(const T *array, const int n) const
{
int i;
if(n>=2)
for(i=0; i if(array[i] > array[i+1])
return 0;
return 1;
}

/**
@brief Verifies whether the array is sorted

@param array - the array to verify
@param n - array size

@return Throws the CAssert whenever the array is not sorted, takes no action otherwise.
*/
template
inline void CBinarySearch::sortedEx(const T *array, const int n) const
{
if(!sorted(array,n)) throw new CAssertionException(INFO("Violated Sorted Precondition"));
}

/**
@brief Initializes given array with sorted values

@param array - array to initialize
@param n - number of elements
@param f - initial element
@param s - step

@return 0 on success, 1 otherwise
*/
template
inline void CBinarySearch::initarray(T *array, const int n, const int f, const int s) const
{
int i;
int elem = f;

for(i = 0; i {
array[i] = elem;
elem += s;
}
}

/**
@brief The main program body.

@returns 0 on successfull execution. 1 otherwise.
*/
int main(int argc, char **argv)
{
long array[50];
CBinarySearch bs;

bs.initarray(array, 50, 5, 2);
try
{
//array[25] = 2222;
cout << bs.binsearch(array, 13, 50) << endl;
}
/* catch (CBinarySearch::CAssertionException *e)
{
cout << e->err() << endl;
}
catch (CPreconditionException *e)
{
cout << e->err() << endl;
}
*/
catch (CException *e)
{
cout << e->err() << endl;
}

return 0;
}