种左一颗多功能二叉查找树（类），纯粹练习数据结构（代码+部分说明+白话文） .
今日系我大一下学期第二日……
之前睇左好多结构都未实践，今日无咩做，用五个钟左右种左一颗多功能二叉树，支持如下操作：
1.build(s,n)｛有随机开关，随便开{……^____^}｝--------以一堆数为基础建树。
2.insert(key)--------插入结点。
3.del(key)--------删除指定关键字所在第一个结点。
4.cut(key)--------剪支（砍左以关键字key为根ge第一课子树）。
5.search(key)--------返回指定关键字第一个（因为有可能重复）指针。
6.max()--------返回整棵树ge最大关键字。
7.min()--------返回整棵树ge最小关键字。
8.pre(key)--------返回指定关键字ge前驱。
9.suc(key)--------返回指定关键字ge后继。
10.front_print()--------输出前序遍历。
11.middle_print()---------输出中序遍历。
12.behind_print()---------输出后序遍历。
13.left_son(key)--------返回关键字第一个结点ge左细路。
14.right_son(key)--------返回关键字第一个结点ge右细路。
15.l_rotate(key)--------左旋转第一个以key为关键字ge结点。
16.l_rotate(key)--------右旋转第一个以key为关键字ge结点。
17.get_root()---------返回根结点指针。
18.empty()--------检查树系唔系空左。
总共18个功能，各有用处挂我觉得，善用尼18个功能都几好ge~~5个钟其实大部分时间都系系度搵bug，有d感受到程序员个d痛苦。尼棵树剩系int容器，当然可以修改成为任意容器啦~~~｛=___=｝。
好咯……吾讲甘多废话拉，睇下代码咯。
//Muti-Function-Binary-Search-Tree//Athtor SGetEternal{=___+}凸 class BST{ private: struct node { node *p,*left,*right; int key; }; node *root,*x,*y,*w; void make_node(node *&temp) { temp=new node; temp->p=NULL; temp->left=NULL; temp->right=NULL; temp->key=0; } public: node* search(int key) { if (empty()) { printf("The tree is empty!!/n"); return NULL; } x=root; while (x->key!=key) { if (key>x->key) x=x->right; else x=x->left; if (x==NULL) break; } return x; } void insert(int key) { bool lr; if (root==NULL) { make_node(root); root->key=key; return ; } x=root; while (x!=NULL) { y=x; if (key>x->key) { x=x->right; lr=1; } else { x=x->left; lr=0; } } make_node(w); w->p=y; w->key=key; if (lr) y->right=w; else y->left=w; } void build(int *s,int n) { int i;#if 0 int a,b; for (i=0;i<n;i++) { srand((int)time(0)); a=rand()%n; b=rand()%n; swap(s[a],s[b]); }#endif for (i=0;i<n;i++) insert(s[i]); } void del(int key) { if (empty()) { printf("The tree is empty!!/n"); return ; } y=search(key); if (y==NULL) { printf("No such node!!/n"); return ; } if (y==root && y->right==NULL) { root=y->left; delete y; return ; } if (y==root && y->left==NULL) { root=y->right; delete y; return ; } w=y; if (y->left!=NULL && y->right!=NULL) y=search(suc(key)); x=y->left; if (x==NULL) x=y->right; if (x!=NULL) x->p=y->p; if (y!=root) { if (y==y->p->right) y->p->right=x; else y->p->left=x; } if (y!=w) w->key=y->key; delete y; } int max() { if (empty()) { printf("The tree is empty!!/n"); return 0; } node *x=root; while (x->right!=NULL) x=x->right; return x->key; } int min() { if (empty()) { printf("The tree is empty!!/n"); return 0; } node *x=root; while (x->left!=NULL) x=x->left; return x->key; } int suc(int key) { if (empty()) { printf("The tree is empty!!/n"); return 0; } x=search(key); if (key==max()) { printf("It's already the max number!!/n"); return 0; } if (x==NULL) { printf("No such number in the tree!!/n"); return 0; } if (x->right!=NULL) { x=x->right; while (x->left!=NULL) x=x->left; } else { y=x->p; while (y->left!=x) { x=y; y=y->p; } x=y; } return x->key; } int pre(int key) { if (empty()) { printf("The tree is empty!!/n"); return 0; } x=search(key); if (key==min()) { printf("It's already the min number!!/n"); return 0; } if (x==NULL) { printf("No such number in the tree!!/n"); return 0; } if (x->left!=NULL) { x=x->left; while (x->right!=NULL) x=x->right; } else { y=x->p; while (y->right!=x) { x=y; y=y->p; } x=y; } return x->key; } int left_son(int key) { if (empty()) { printf("The tree is empty!!/n"); return 0; } if (search(key)==NULL) { printf("No such node!!/n"); return 0; } x=search(key)->left; if (x==NULL) { printf("This node doesn't have left son!!/n"); return 0; } else return x->key; } int right_son(int key) { if (empty()) { printf("The tree is empty!!/n"); return 0; } if (search(key)==NULL) { printf("No such node!!/n"); return 0; } x=search(key)->right; if (x==NULL) { printf("This node doesn't have right son!!/n"); return 0; } else return x->key; } void l_rotate(int key) { if (empty()) { printf("The tree is empty!!/n"); return ; } x=search(key); if (x->right==NULL) { printf("It can't left-rotate!!/n"); return ; } else { w=x->right; w->p=x->p; if (x->p!=NULL) { if (x==x->p->right) x->p->right=w; else x->p->left=w; } x->p=w; x->right=w->left; w->left=x; if (w->left!=NULL) w->left->p=x; if (x==root) root=w; } } void r_rotate(int key) { if (empty()) { printf("The tree is empty!!/n"); return ; } x=search(key); if (x->left==NULL) { printf("It can't right-rotate!!/n"); return ; } else { w=x->left; w->p=x->p; if (x->p!=NULL) { if (x==x->p->right) x->p->right=w; else x->p->left=w; } x->p=w; x->left=w->right; w->right=x; if (w->right!=NULL) w->right->p=x; if (x==root) root=w; } } void front_print(node *temp) { if (empty()) { printf("The tree is empty!!/n"); return ; } if (temp!=NULL) { printf("%d ",temp->key); front_print(temp->left); front_print(temp->right); } } void middle_print(node *temp) { if (empty()) { printf("The tree is empty!!/n"); return ; } if (temp!=NULL) { middle_print(temp->left); printf("%d ",temp->key); middle_print(temp->right); } } void behind_print(node *temp) { if (empty()) { printf("The tree is empty!!/n"); return ; } if (temp!=NULL) { behind_print(temp->left); behind_print(temp->right); printf("%d ",temp->key); } } void cut(node *temp) { if (empty()) { printf("The tree is empty!!/n"); return ; } if (temp!=NULL) { cut(temp->left); cut(temp->right); if (temp->p!=NULL) { if (temp->p->right==temp) temp->p->right=NULL; else temp->p->left=NULL; } if (temp==root) root=NULL; delete temp; } } inline node* get_root() {return root;} inline bool empty(){return root==NULL;} BST () {root=NULL;} ~BST (){} };