大师兄，师傅被妖怪抓走啦！
这里只给出一个简单的实现，具体原理参见Google、Baidu的各个角落及各大教材。做两点说明：
仅仅实现了必要的左旋、右旋处理，左平衡、右平衡操作，以及数据的插入操作，
不可重复插入数据。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | typedef int Type; //~ 节点数据类型 typedef struct Node { Type data; int bf; Node *left, *right; Node(){ bf = 0; left = right = 0; } } AVLNode, *AVLTree; //~ 平衡树及其节点 void RRotate(AVLTree & T) //~ 右旋处理,T的左孩子成为新子树根 { AVLNode * tmp = T->left; T->left = tmp->right; tmp->right = T; T = tmp; } |
一个最小堆的C++模板。什么东西都想封装成类，做成模板，即使它仅仅就是一个普通的函数，尤其是用到一些全局的对象时，觉得封装成类看起来更紧凑一点，使用起来也更方便更顺手一些。这个最小堆模板实现了以下几个小特性：
容量不足时，能够动态地调整大小；
可以用一个数组来初始化，并建立最小堆；
没有复制构造，^*^.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | void reverse(Node * T) { assert(T); //~ 表头非空 Node* p = T->next, *t; if(p) { //~ 将第一个结点，即未来的表尾next域置空 t = p->next; p->next = NULL; p = t; } while(p) { //~ 将余下结点依次插入表头 t = p->next; p->next = T->next; T->next = p; p = t; } } |
有一点需要注意的是，由于STL内的容器的析构函数都不是virtual的，所以，继承这些容器的类(或者模板类)不能用于多态！这也是不提倡继承STL容器的原因。
不过，由于上面的代码中mstack
继承vector的目的不是使用多态特性，仅仅是复用了vector的接口而已，且复用也仅仅是内部复用；
由于是私有继承，你无法调用父类vector的接口，子类与父类接口并不一致，在语法就不能用于多态；
综上所述，这样的继承并没有什么潜在的危险。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | /* * pre存放先序序列， * in存放中序序列， * n为结点个数， * 返回二叉树根指针 */ BTree CreateBT(Type * pre, Type * in, int n) { if(n <= 0) return NULL; BTree bt = new BTNode; Type * p; int k; bt->data = *pre; for(p = in; p < in + n; ++p) if(*pre == *p) break; k = p - in; bt->lchild = CreateBT(pre+1, in, k); bt->rchild = CreateBT(pre+k+1, p+1, n-k-1); return bt; } |
严老太，在您面前小孙孙我实在心智底下啊！一个AVL就把我整的团团转，单向右旋，单向左旋，双向旋转先左后右，双向旋转先右后左，很简单的道理，您就是不肯轻易说出来，在那转啊转的，貌似很神秘的样子！
在构造AVL树的时候，会出现插入某个节点后输不再平衡的情况，这时候只需要找到离插入点最近的、平衡因子不合法的节点，调整以此节点为根的子树(*)，使其平衡因子合法，其实就是使这棵子树(*)的高度与插入节点前相比不发生变化。具体的调整策略因具体情况而异，但原则都是一样的：首先应该明确根节点大于左孩子而小于右孩子，另外，调整后的子树(*)的根是一定会发生变化的，且变化后的子树应该满足平衡条件，即平衡因子为1，0，-1之一。
AVL是一种二叉搜索树(Binary Search Tree)，被称为平衡树(Balanced Binary Tree)，由Adelsonr Velskii 和Landis 提出并以他们的名字命名。
今天看严蔚敏老太太的数据结构，她老人家是这么描述AVL的：AVL，它或者是一棵空树，或者是具有以下性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差(平衡因子：BF)的绝对值不超过1。看着这么个定义很别扭，总觉得对平衡因子的要求比较弱，也可能是我悟性较弱吧，在这句话上我很是下了一番功夫……如果这样来定义的话，可能会让我更容易理解一些：
关联式容器associative container:
被插入的元素并没有一个固定的位置。这不仅是指操作者可能更改其中元素的位置，还有可能——每当新插入一个元素时，容器都会自动的按照某种排序规则将新来的元素放置在合适的位置。也即，这种容器内元素的排列顺序由容器自己的排序规则决定，操作者无能为力。
B树
即二叉搜索树：