// Created by Nick Schrock, April 22, 2001 /* Prof. Markov, I believe I have a different, but still correct, solution to number 4 on the practice final. The idea is to make a copy of the array, sort it and then visit the bst in in-fix order. The code is elegant, but has probably too heavy of payload per recursive call (just whipped this up though :)). Here it is.... */ #include #include #include #include using namespace std; void makeBalancedBST(unsigned *begin, unsigned numElem); void mkBST_rec(unsigned current, unsigned *bst, unsigned *sorted, const unsigned numElem); int main() { // this is a driver program for the above function // it is not a part of the solution of problem 4 srand(49384074); const unsigned N=13; unsigned a[N+1],i; for(i=1; i!=N+1; i++) a[i]=rand() % 1000; // populate a cout << " Input array: " << endl; for(i=1; i!=N+1; i++) cout << a[i] << " " ; cout << endl; makeBalancedBST(a,N); cout << " BST-ordered array: " << endl; for(i=1; i!=N+1; i++) cout << a[i] << " " ; cout << endl; return 0; } void makeBalancedBST(unsigned *begin, unsigned numElem) { unsigned *sorted = new unsigned[numElem],ii(0); for (ii = 1; ii <= numElem; ++ii) sorted[ii-1] = begin[ii]; // Igor's comment: copy(begin+1,begin+numElem,sorted); // would do the same *and* instantiate into a memcpy() call sort(sorted,sorted+numElem); mkBST_rec(1,begin,sorted,numElem); } void mkBST_rec(unsigned current, unsigned *bst, unsigned *sorted, const unsigned numElem) { static unsigned sorted_idx(0); if (current*2 <= numElem) mkBST_rec(current*2,bst,sorted,numElem); bst[current] = sorted[sorted_idx++]; if ((current*2+1) <= numElem) mkBST_rec(current*2+1,bst,sorted,numElem); }