二叉树
定义节点

class Node {
public:
int key;
struct Node *l;
struct Node *r;
Node(int _key): l(NULL), r(NULL), key(_key) {}
};

二叉树上一个节点，最少需要三个属性，一个用于表示节点编号的key值，一个指向左子节点的指针、一个指向右子节点的指针。

定义一棵树

class BTree {
public:
BTree() : root(NULL) {}
void insert(int key);
void insertRoot(int key);
void deleteNode(int key);
void print();

private:
Node *root;
private:
// 向h树指向的树中添加元素key，返回更新后的树
static Node *insertR(Node *h, int key);
// 右旋操作，可以令左子树深度减一，返回旋转后的树
static Node *rotateR(Node *h);
// 左旋操作，可以令右子树深度减一，返回旋转后的树
static Node *rotateL(Node *h);
// 将h树最小的元素上浮到树根部，返回最后上浮后的树
static Node *minToRoot(Node *h);
// 将两棵树合并成一棵树，返回合并后的树
static Node *join(Node *l, Node *r);
// 向h树中插入元素，并且插入的元素会存在树根部，返回插入后的树
static Node *insertT(Node *h, int key);
// 中序遍历h树
static void inOrder(Node *h);
// 从h树中删除key，返回删除后的树
static Node *deleteR(Node *h, int key);
};

树的操作很多，以上只是列举其中的一些操作，对于代码实现，难点反而在于正确理解递归调用，二叉树的性质反而很简单。只要能够理解这些递归调用的特点，添加新的操作方法反而不是太难。

封装

void BTree::insert(int key) {
this->root = insertR(this->root, key);
}

void BTree::insertRoot(int key) {
this->root = insertT(this->root, key);
}

void BTree::print() {
inOrder(this->root);
}

void BTree::deleteNode(int key) {
this->root = deleteR(this->root, key);
}

树的很多操作通过递归可以很容易的实现，所以需要对这些递归操作进行封装，可以简化外部操作。

插入元素

Node *BTree::insertR(Node *h, int key) {
if (h == NULL) return new Node(key);
if (h->key < key) {
h->r = insertR(h->r, key);
} else {
h->l = insertR(h->l, key);
}
return h;
}

插入元素必须递归地向树根部游走，直到遇到树根部，然后插入元素，再依次退回。递归调用的过程就是向下游走的过程，遇到NULL，表明已经走到树根部。

这里比较绕的就是返回值的语义，它表示插入元素后新生成的树。

旋转

Node *BTree::rotateR(Node *h) {
if (h->l == NULL) return h;
Node *x = h->l;
h->l = x->r;
x->r = h;
return x;
}

Node *BTree::rotateL(Node *h) {
if (h->r == NULL) return h;
Node *x = h->r;
h->r = x->l;
x->l = h;
return x;
}

树的旋转操作很有意思，它可以在不更改树的性质的情况下，改变左右子树的高度

合并子树

Node *BTree::minToRoot(Node *h) {
if (h->l != NULL) {
h->l = minToRoot(h->l); // 将最小元素提升到左子树的根部
h = rotateR(h); // 将左子树中最小元素提升到根部
}
return h;
}

Node *BTree::join(Node *l, Node *r) {
if (r == NULL) return l;
r = minToRoot(r); // 将r树的最小元素提升到根节点
r->l = l;
return r;
}

合并子树的操作也很有趣(这里的合并不是任意两个子树合并，而是左子树中任意元素必须小于右子树中最小的元素)：

如果希望将任意两棵树进行合并，则要麻烦许多。

相关阅读：