看到二叉搜索树，就会回想到当年在大学课堂学习数据结构的情景，真的是悠悠岁月，欲说当年好困惑。
二叉树的可以参考的资料繁多，这里就不多说了，非要说的话，请看算法导论第12章吧。
下面是代码，包含了一点点C++11的特性。
1、二叉树遍历，没有比递归实现更优雅简洁直观的了，非要说非递归就是好的话我也赞成，反正大家开心就好：
1 template<typename T>
2 void inorder_tree_walk(bst_node_cls<T>* x) {
3 if(x != nullptr) {
4 inorder_tree_walk(x->left);
5 cout << x->key << " ";
6 inorder_tree_walk(x->right);
7 }
8 }
2、如何描述二叉树的根节点和其他子节点：
1 template<typename T>
2 struct bst_node {
3 typedef bst_node<T> __node;
4 __node* parent;
5 __node* left;
6 __node* right;
7 T key;
8 void *data;
9 };
10
11 template<typename T> using bst_node_cls = bst_node<T>;
12
13 template<typename T>
14 struct binary_search_tree {
15 bst_node_cls<T>* root;
16 };
17
18 template<typename T> using bst_cls = binary_search_tree<T>;
3、二叉树的最小关键值和最大关键值
1 template<typename T>
2 bst_node_cls<T>* tree_minimum(bst_node_cls<T>* node) {
3 while(node->left != nullptr)
4 node = node->left;
5 return node;
6 }
7
8 template<typename T>
9 bst_node_cls<T>* tree_maximum(bst_node_cls<T>* node) {
10 while(node->right != nullptr)
11 node = node->right;
12 return node;
13 }
4、某个节点的后继与前驱。
后继就是key值比这个节点的key值就大那么一点点，不能更多了；前驱就是key值比这个节点的key值小那么一点点，不能更小了。
1 template<typename T>
2 bst_node_cls<T>* tree_successor(bst_node_cls<T>* node) {
3 bst_node_cls<T>* y = nullptr;
4
5 if(node->right != nullptr)
6 return tree_minimum(node->right);
7
8 y = node->parent;
9 while(y != nullptr && node == y->right) {
10 node = y;
11 y = y->parent;
12 }
13
14 return y;
15 }
16
17 template<typename T>
18 bst_node_cls<T>* tree_presuccessor(bst_node_cls<T>* node) {
19 bst_node_cls<T>* y = nullptr;
20
21 if(node->left != nullptr)
22 return tree_maximum(node->left);
23
24 y = node->parent;
25 while(y != nullptr && node == y->left) {
26 node = y;
27 y = y->parent;
28 }
29
30 return y;
31 }
5、节点的插入与删除
1 template<typename T>
2 void tree_insert(bst_cls<T>& tree, bst_node_cls<T>* z) {
3 bst_node_cls<T> *y = nullptr;
4 bst_node_cls<T> *x = tree.root;
5
6 while (x != nullptr) {
7 y = x;
8 x = (z->key < x->key) ? x->left : x->right;
9 }
10
11 z->parent = y;
12 if (y == nullptr) {
13 tree.root = z;
14 } else if (z->key < y->key){
15 y->left = z;
16 } else {
17 y->right = z;
18 }
19 }
20
21 template<typename T>
22 void transplant(bst_cls<T>& tree, bst_node_cls<T>* u, bst_node_cls<T>* v) {
23 if(u->parent == nullptr)
24 tree.root = v;
25 else if (u == u->parent->left) {
26 u->parent->left = v;
27 } else {
28 u->parent->right = v;
29 }
30
31 if(v != nullptr)
32 v->parent = u->parent;
33 }
34
35 template<typename T>
36 void tree_delete(bst_cls<T>& tree, bst_node_cls<T>* z) {
37 bst_node_cls<T>* y;
38
39 if(z->left == nullptr) {
40 transplant(tree, z, z->right);
41 } else if(z->right == nullptr) {
42 transplant(tree, z, z->left);
43 } else {
44 y = tree_minimum(z.right);
45 if(y.parent != z) {
46 transplant(tree, y, y->right);
47 y->right = z->right;
48 y->right->parent = y;
49 }
50 transplant(tree, z, y);
51 y->left = z->left;
52 y->left->parent = y;
53 }
54 }