数据结构的期末作业是关于平衡二叉排序树的综合性实验，其中需要完成的功能有：
（1） 插入新结点
（2） 前序、中序、后序遍历二叉树 （递归）
（3） 前序、中序、后序遍历的非递归算法
（4） 层次遍历二叉树
（5） 在二叉树中查找给定关键字(函数返回值为成功1,失败0)
（6） 交换各结点的左右子树
（7） 求二叉树的深度
（8） 叶子结点数
（9） 删除某结点
搞了两三天，上面的功能都实现了。而且我弄的是模板，兼容性也就相对强了一些。
其实这对我只是一个锻炼而已，目测代码方面还有很多的地方可以改进，欢迎读者提出或指正。
弄这个的时候发现一个比较矛盾的地方，就是其中会有树交换子树的操作。交换后，原来升序将会变成降序，反之亦然。所以，我在做的时候就不是单纯的给出交换子树的算法，而是在这个处理过后修改一个标记。初始化排序是按非降排序的，如果进行过一次倒置操作，树将以非升方式排序。这样就保持了二叉排序树的特性了。
View Code 1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 9 using namespace std; 10 11 /********** simple stack template by Lyon 2012.11.24 **********/ 12 template 13 class Stack { 14 int maxSize, curSize; 15 T *elem; 16 public: 17 void init() { // initialize stack 18 maxSize = 16; 19 curSize = 0; 20 elem = (T *) malloc(maxSize * sizeof(T)); 21 } 22 bool empty() { // whether the stack is empty 23 return curSize == 0; 24 } 25 int size() { // get the size 26 return curSize; 27 } 28 void push(T e) { // push e into stack 29 while (curSize >= maxSize) { 30 maxSize <<= 1; 31 elem = (T *) realloc(elem, maxSize * sizeof(T)); 32 } 33 elem[curSize++] = e; 34 } 35 void pop() { // pop out the top element 36 assert(curSize > 0); 37 curSize--; 38 } 39 T top() { // get the top element 40 assert(curSize > 0); 41 return elem[curSize - 1]; 42 } 43 } ; 44 /****************************************************************/ 45 46 /********** simple queue template by Lyon 2012.11.24 **********/ 47 template 48 class Queue { 49 struct Node { 50 T elem; 51 Node *next; 52 Node (T &x) { 53 elem = x; 54 next = NULL; 55 } 56 } *head, *tail; 57 int curSize; 58 public: 59 void init() { // initialize queue 60 head = tail = NULL; 61 curSize = 0; 62 } 63 bool empty() { // whether the queue is empty 64 return curSize == 0; 65 } 66 int size() { // get the size 67 return curSize; 68 } 69 void push(T &e) { // push e into queue 70 if (head == NULL) { 71 head = tail = new Node(e); 72 } else { 73 tail->next = new Node(e); 74 tail = tail->next; 75 } 76 curSize++; 77 } 78 void pop() { // pop out the front element 79 assert(head != NULL); 80 Node *tmp = head; 81 head = head->next; 82 if (tail == tmp) tail = NULL; 83 delete tmp; 84 curSize--; 85 } 86 T front() { // get the front element 87 assert(head != NULL); 88 return head->elem; 89 } 90 T back() { // get the back element 91 assert(tail != NULL); 92 return tail->elem; 93 } 94 } ; 95 /****************************************************************/ 96 97 /********** SBTree(short for Size-Balanced Tree) template by Lyon 2012.11.24 **********/ 98 template 99 struct SBTNode { // size-balanced tree's node100 int size, depth, leaf; // size - subtree's size, depth - subtree's depth, leaf - the number of leaf in subtree101 T key;102 SBTNode *c[2]; // two child103 SBTNode (T k) {104 key = k;105 size = 1;106 depth = 1;107 leaf = 1;108 c[0] = c[1] = NULL;109 }110 } ;111 template 112 class SBTree { // size-balanced tree113 SBTNode *Root;114 bool less; // the way of sort115 void delTree(SBTNode *&rt) { // delete the tree116 if (!rt) return ;117 delTree(rt->c[0]);118 delTree(rt->c[1]);119 delete rt;120 rt = NULL;121 less = false;122 }123 void rotate(SBTNode *&x, bool left) { // rotate subtree x124 bool right = !left;125 SBTNode *y = x->c[left];126 x->c[left] = y->c[right];127 y->c[right] = x;128 y->size = x->size;129 x->size = (x->c[0] ? x->c[0]->size : 0) + (x->c[1] ? x->c[1]->size : 0) + 1;130 x->depth = max(x->c[0] ? x->c[0]->depth : 0, x->c[1] ? x->c[1]->depth : 0) + 1;131 y->depth = max(y->c[0] ? y->c[0]->depth : 0, y->c[1] ? y->c[1]->depth : 0) + 1;132 x->leaf = x->c[0] == NULL && x->c[1] == NULL ? 1 : (x->c[0] ? x->c[0]->leaf : 0) + (x->c[1] ? x->c[1]->leaf : 0);133 x = y;134 }135 void maintain(SBTNode *&rt, bool right) { // maintain subtree rt, if the right side of subtree is deeper136 if (!rt->c[right] || !rt) return ;137 bool left = !right;138 int ls = rt->c[left] ? rt->c[left]->size : 0;139 if (rt->c[right]->c[right] && rt->c[right]->c[right]->size > ls) rotate(rt, right);140 else if (rt->c[right]->c[left] && rt->c[right]->c[left]->size > ls) rotate(rt->c[right], left), rotate(rt, right);141 else return ;142 maintain(rt->c[0], false);143 maintain(rt->c[1], true);144 maintain(rt, false);145 maintain(rt, true);146 }147 void insert(SBTNode *&rt, SBTNode *x) { // insert x into subtree rt148 if (!rt) {149 rt = x;150 return ;151 }152 rt->size++;153 insert(rt->c[(x->key >= rt->key) ^ less], x);154 maintain(rt, (x->key >= rt->key) ^ less);155 rt->depth = max(rt->c[0] ? rt->c[0]->depth : 0, rt->c[1] ? rt->c[1]->depth : 0) + 1;156 rt->leaf = rt->c[0] == NULL && rt->c[1] == NULL ? 1 : (rt->c[0] ? rt->c[0]->leaf : 0) + (rt->c[1] ? rt->c[1]->leaf : 0);157 }158 bool erase(SBTNode *&rt, T k) { // erase key k in subtree rt159 if (!rt) return false;160 rt->size--;161 if (k == rt->key) {162 SBTNode *t;163 if (!rt->c[0] && !rt->c[1]) {164 delete rt;165 rt = NULL;166 } else if (!rt->c[1]) {167 t = rt, rt = rt->c[0];168 delete t;169 } else if (!rt->c[0]) {170 t = rt, rt = rt->c[1];171 delete t;172 } else {173 t = rt->c[1];174 while (t->c[0]) t = t->c[0];175 rt->key = t->key;176 return erase(rt->c[1], t->key);177 }178 } else return erase(rt->c[(k > rt->key) ^ less], k);179 if (rt) {180 rt->depth = max(rt->c[0] ? rt->c[0]->depth : 0, rt->c[1] ? rt->c[1]->depth : 0) + 1;181 rt->leaf = rt->c[0] == NULL && rt->c[1] == NULL ? 1 : (rt->c[0] ? rt->c[0]->leaf : 0) + (rt->c[1] ? rt->c[1]->leaf : 0);182 }183 return true;184 }185 void Traverse(SBTNode *rt, int kind) { // recursive traverse : 1.pre 2.in 3.post186 if (!rt) return ;187 if (kind == 1) cout << rt->key << ends;188 Traverse(rt->c[0], kind);189 if (kind == 2) cout << rt->key << ends;190 Traverse(rt->c[1], kind);191 if (kind == 3) cout << rt->key << ends;192 }193 void nonRecursiveTraverse(int kind) { // non-recursive traverse : 1.pre 2.in 3.post194 Stack *, int> > rec;195 SBTNode *cur;196 int t;197 rec.init();198 rec.push(make_pair(Root, 1));199 while (rec.size()) {200 cur = rec.top().first;201 t = rec.top().second;202 rec.pop();203 if (cur && t == kind) cout << cur->key << ends;204 if (!cur || t >= 3 || t <= 0) continue;205 // cout << cur->key << '-' << t << ends;206 rec.push(make_pair(cur, t + 1));207 rec.push(make_pair(cur->c[t - 1], 1));208 }209 }210 void reverse(SBTNode *rt) { // reverse subtree rt211 if (!rt) return ;212 swap(rt->c[0], rt->c[1]);213 reverse(rt->c[0]);214 reverse(rt->c[1]);215 }216 public:217 void init(bool cmp = false) { // initialize SBTree218 Root = NULL;219 less = cmp;220 }221 bool empty() {222 return Root == NULL;223 }224 void delTree() { // delete SBTree225 delTree(Root);226 cout << "The Size-balanced Tree is deleted!" << endl;227 }228 void insert(T x) { // insert x into SBTree229 SBTNode *tmp = new SBTNode (x);230 insert(Root, tmp);231 cout << "Element " << x << " Insert Successfully!" << endl;232 }233 bool erase(T k) { // erase k in SBTree234 if (erase(Root, k)) {235 cout << "Element " << k << " Erase Successfully!" << endl;236 return true;237 } else {238 cout << "Element " << k << " not found!" << endl;239 return false;240 }241 }242 void preTraverse() { // output the pre-traverse array243 cout << "The pre-Traverse array is:" << endl;244 Traverse(Root, 1);245 cout << endl;246 }247 void inTraverse() { // output the in-traverse array248 cout << "The in-Traverse array is:" << endl;249 Traverse(Root, 2);250 cout << endl;251 }252 void postTraverse() { // output the post-traverse array253 cout << "The post-Traverse array is:" << endl;254 Traverse(Root, 3);255 cout << endl;256 }257 void nonRecursivePreTraverse() { // in non-recursive way258 cout << "The pre-Traverse array is (non-recursive):" << endl;259 nonRecursiveTraverse(1);260 cout << endl;261 }262 void nonRecursiveInTraverse() { // in non-recursive way263 cout << "The in-Traverse array is (non-recursive):" << endl;264 nonRecursiveTraverse(2);265 cout << endl;266 }267 void nonRecursivePostTraverse() { // in non-recursive way268 cout << "The post-Traverse array is (non-recursive):" << endl;269 nonRecursiveTraverse(3);270 cout << endl;271 }272 bool find(T key) { // find key value in SBTree273 SBTNode *p = Root;274 while (true) {275 if (!p) return false;276 if (key == p->key) return true;277 if ((key < p->key) ^ less) p = p->c[0];278 else p = p->c[1];279 }280 }281 int depth() {282 return Root->depth; // the depth of SBTree283 }284 int leaves() {285 return Root->leaf; // the number of leaf in SBTree286 }287 void reverse() { // reverse SBTree288 less = !less;289 reverse(Root);290 cout << "Tree is reversed!" << endl;291 }292 void nonRecursiveReverseDFS() { // in non-recursive way293 less = !less;294 Stack *, int> > rec;295 SBTNode *cur;296 int t;297 rec.init();298 rec.push(make_pair(Root, 1));299 while (rec.size()) {300 cur = rec.top().first;301 t = rec.top().second;302 rec.pop();303 if (!cur || t >= 3 || t <= 0) continue;304 if (t == 1) swap(cur->c[0], cur->c[1]);305 // cout << cur->key << '-' << t << ends;306 rec.push(make_pair(cur, t + 1));307 rec.push(make_pair(cur->c[t - 1], 1));308 }309 }310 void nonRecursiveReverseBFS() {311 less = !less;312 Queue *> tmp;313 SBTNode *cur;314 tmp.init();315 tmp.push(Root);316 while (tmp.size()) {317 cur = tmp.front();318 swap(cur->c[0], cur->c[1]);319 if (cur->c[0]) tmp.push(cur->c[0]);320 if (cur->c[1]) tmp.push(cur->c[1]);321 }322 cout << "Tree is reversed!" << endl;323 }324 void levelTraverse() { // level traverse325 Queue *> q;326 cout << "The level traverse array is:" << endl;327 q.init();328 q.push(Root);329 SBTNode *cur;330 while (q.size()) {331 cur = q.front();332 q.pop();333 cout << cur->key << ends;334 if (cur->c[0]) q.push(cur->c[0]);335 if (cur->c[1]) q.push(cur->c[1]);336 }337 cout << endl;338 }339 } ;340 /*************************************************************************************/341 342 343 344 #define REP(i, n) for (int i = 0; i < n; i++)345 SBTree SBT;346 347 int main() {348 int n, e, op;349 char buf[100];350 351 SBT.init();352 cout << "请输入树的节点个数：";353 cin >> n;354 cout << "请输入" << n << "个整数：";355 REP(i, n) {356 cin >> e;357 SBT.insert(e);358 }359 system("pause > nul");360 system("cls");361 while (true) {362 while (true) {363 cout << "━━━━━━━━━━━━━━━━━┓\n";364 cout << " 1.查看树的前中后序及层次遍历 ┃\n";365 cout << " 2.查看树的前中后序遍历（非递归）┃\n";366 cout << " 3.查找树的结点 ┃\n";367 cout << " 4.查看树的深度和叶子结点个数 ┃\n";368 cout << " 5.交换树的左右子树 ┃\n";369 cout << " 6.插入新的结点 ┃\n";370 cout << " 7.删除结点 ┃\n";371 cout << " 8.退出程序 ┃\n";372 cout << "━━━━━━━━━━━━━━━━━┛\n";373 cout << "请输入操作编号：";374 cin >> op;375 if (0 <= op && op <= 8) break;376 cout << "输入错误，请重新输入!" << endl;377 system("pause > nul");378 system("cls");379 }380 switch (op) {381 case 1:382 if (SBT.empty()) cout << "当前树为空树" << endl;383 else {384 SBT.preTraverse();385 SBT.inTraverse();386 SBT.postTraverse();387 SBT.levelTraverse();388 }389 break;390 case 2:391 if (SBT.empty()) cout << "当前树为空树" << endl;392 else {393 SBT.nonRecursivePreTraverse();394 SBT.nonRecursiveInTraverse();395 SBT.nonRecursivePostTraverse();396 }397 break;398 case 3:399 cout << "请输入需要查找结点的值：";400 cin >> e;401 if (SBT.find(e)) cout << "查找成功，该结点存在！" << endl;402 else cout << "查找失败，该结点不存在！" << endl;;403 break;404 case 4:405 cout << "树的深度为：" << SBT.depth() << endl;406 cout << "树的叶子结点个数为：" << SBT.leaves() << endl;407 break;408 case 5:409 cout << "确定要交换树的左右结点吗？（交换以后，元素升降序将改变）" << endl << "按'Y'键后回车继续：";410 cin >> buf;411 strlwr(buf);412 if (buf[0] == 'y') {413 SBT.reverse();414 cout << "操作成功" << endl;415 } else cout << "已放弃操作" << endl;416 break;417 case 6:418 cout << "请输入新结点的值：";419 cin >> e;420 SBT.insert(e);421 cout << "结点已成功插入" << endl;422 break;423 case 7:424 if (SBT.empty()) cout << "当前树为空树，不能进行删除操作" << endl;425 else {426 SBT.nonRecursiveInTraverse();427 cout << "请输入要删除的结点的值: ";428 cin >> e;429 if (!SBT.erase(e)) cout << "操作失败，该结点不存在" << endl;430 else cout << "操作成功" << endl;431 }432 break;433 case 8:434 SBT.delTree();435 cout << "操作成功，可以安全退出！" << endl;436 system("pause > nul");437 return 0;438 default:439 cout << "出现异常！" << endl;440 return -1;441 }442 system("pause > nul");443 system("cls");444 }445 }
——written by Lyon