数据结构综合性实验：多种功能的平衡二叉排序树

　　数据结构的期末作业是关于平衡二叉排序树的综合性实验，其中需要完成的功能有：
（1）插入新结点
（2）前序、中序、后序遍历二叉树（递归）
（3）前序、中序、后序遍历的非递归算法
（4）层次遍历二叉树
（5）在二叉树中查找给定关键字(函数返回值为成功1,失败0)
（6）交换各结点的左右子树
（7）求二叉树的深度
（8）叶子结点数
（9）删除某结点
　　搞了两三天，上面的功能都实现了。而且我弄的是模板，兼容性也就相对强了一些。
　　其实这对我只是一个锻炼而已，目测代码方面还有很多的地方可以改进，欢迎读者提出或指正。
　　弄这个的时候发现一个比较矛盾的地方，就是其中会有树交换子树的操作。交换后，原来升序将会变成降序，反之亦然。所以，我在做的时候就不是单纯的给出交换子树的算法，而是在这个处理过后修改一个标记。初始化排序是按非降排序的，如果进行过一次倒置操作，树将以非升方式排序。这样就保持了二叉排序树的特性了。
View Code
  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <cstdlib>
  5 #include <algorithm>
  6 #include <cassert>
  7 #include <ctime>
  8 
  9 using namespace std;
 10 
 11 /********** simple stack template by Lyon   2012.11.24 **********/
 12 template <class T>
 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 <class T>
 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 <class T>
 99 struct SBTNode { // size-balanced tree's node
100     int size, depth, leaf; // size - subtree's size, depth - subtree's depth, leaf - the number of leaf in subtree
101     T key;
102     SBTNode<T> *c[2]; // two child
103     SBTNode<T> (T k) {
104         key = k;
105         size = 1;
106         depth = 1;
107         leaf = 1;
108         c[0] = c[1] = NULL;
109     }
110 } ;
111 template <class T>
112 class SBTree { // size-balanced tree
113     SBTNode<T> *Root;
114     bool less; // the way of sort
115     void delTree(SBTNode<T> *&rt) { // delete the tree
116         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<T> *&x, bool left) { // rotate subtree x
124         bool right = !left;
125         SBTNode<T> *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<T> *&rt, bool right) { // maintain subtree rt, if the right side of subtree is deeper
136         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<T> *&rt, SBTNode<T> *x) { // insert x into subtree rt
148         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<T> *&rt, T k) { // erase key k in subtree rt
159         if (!rt) return false;
160         rt->size--;
161         if (k == rt->key) {
162             SBTNode<T> *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<T> *rt, int kind) { // recursive traverse : 1.pre 2.in 3.post
186         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.post
194         Stack<pair<SBTNode<T> *, int> > rec;
195         SBTNode<T> *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<T> *rt) { // reverse subtree rt
211         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 SBTree
218         Root = NULL;
219         less = cmp;
220     }
221     bool empty() {
222         return Root == NULL;
223     }
224     void delTree() { // delete SBTree
225         delTree(Root);
226         cout << "The Size-balanced Tree is deleted!" << endl;
227     }
228     void insert(T x) { // insert x into SBTree
229         SBTNode<T> *tmp = new SBTNode<T>(x);
230         insert(Root, tmp);
231         cout << "Element " << x << " Insert Successfully!" << endl;
232     }
233     bool erase(T k) { // erase k in SBTree
234         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 array
243         cout << "The pre-Traverse array is:" << endl;
244         Traverse(Root, 1);
245         cout << endl;
246     }
247     void inTraverse() { // output the in-traverse array
248         cout << "The in-Traverse array is:" << endl;
249         Traverse(Root, 2);
250         cout << endl;
251     }
252     void postTraverse() { // output the post-traverse array
253         cout << "The post-Traverse array is:" << endl;
254         Traverse(Root, 3);
255         cout << endl;
256     }
257     void nonRecursivePreTraverse() { // in non-recursive way
258         cout << "The pre-Traverse array is (non-recursive):" << endl;
259         nonRecursiveTraverse(1);
260         cout << endl;
261     }
262     void nonRecursiveInTraverse() { // in non-recursive way
263         cout << "The in-Traverse array is (non-recursive):" << endl;
264         nonRecursiveTraverse(2);
265         cout << endl;
266     }
267     void nonRecursivePostTraverse() { // in non-recursive way
268         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 SBTree
273         SBTNode<T> *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 SBTree
283     }
284     int leaves() {
285         return Root->leaf;    // the number of leaf in SBTree
286     }
287     void reverse() { // reverse SBTree
288         less = !less;
289         reverse(Root);
290         cout << "Tree is reversed!" << endl;
291     }
292     void nonRecursiveReverseDFS() { // in non-recursive way
293         less = !less;
294         Stack<pair<SBTNode<T> *, int> > rec;
295         SBTNode<T> *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<SBTNode<T> *> tmp;
313         SBTNode<T> *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 traverse
325         Queue<SBTNode<T> *> q;
326         cout << "The level traverse array is:" << endl;
327         q.init();
328         q.push(Root);
329         SBTNode<T> *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<int> 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