// Binary Search Trees // #include #include #include #include using namespace std; class Btree { public: Btree(string s); ~Btree() { delete left; delete right; } static int sval; int order() { int lcnt = left ? left->order() : 0; value = ++sval; int rcnt = right ? right->order() : 0; return 1 + lcnt + rcnt; } void print() { cout << value << ' '; if (left) left->print(); if (right) right->print(); } private: int value; Btree* left; Btree* right; }; int Btree::sval; Btree::Btree(string s) { value = 0; int n = s.length(); while (s[n-1]<33) n--; // trim off spaces and dos eol characters. if (n==2) { assert(s[0]=='(' && s[1]==')'); left = right = 0; return; } int cnt = 1; int splitpos=0; for (int i=1; i0 && splitpos1) left = new Btree( string(s,1,splitpos-1) ); else left = 0; if (splitpos