二叉排序树又叫二叉查找树，英文名称是：Binary Sort Tree. BST的定义就不详细说了，我用一句话概括：左 < 中 < 右。 根据这个原理，我们可以推断：BST的中序遍历必定是严格递增的。
在建立一个BST之前，大家可以做一下这个题目（很简单的）：
已知，某树的先序遍历为：4, 2, 1 ,0, 3, 5, 9, 7, 6, 8. 中序遍历为: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. 请画出该树。
我们知道，树的基本遍历有4种方式，分别是：
先序遍历；中序遍历；后续遍历；层次遍历。事实上，知道任意两种方式，并不能唯一地确定树的结构，但是，只要知道中序遍历和另外任意一种遍历方式，就一定可以唯一地确定一棵树，于是，，上面那个题目的答案如下：
#include <iostream>
using namespace std;// BST的结点 typedef struct node{int key;struct node *lChild, *rChild;}Node, *BST;// 在给定的BST中插入结点，其数据域为element, 使之称为新的BST bool BSTInsert(Node * &p, int element){if (p == NULL){p = new Node;p->key = element;p->lChild = p->rChild = NULL;}if (element == p->key){return false;}if (element < p->key){BSTInsert(p->lChild, element);}elseBSTInsert(p->rChild, element);return true;}void createBST(BST &p){int k;p = NULL;printf("请输入一组数字，#结束\n");while(scanf("%d", &k)==1)BSTInsert(p,k);}//先序遍历void preorderBST(BST p){if (p){cout << p->key << " ";preorderBST(p->lChild);preorderBST(p->rChild);}}//中序遍历（这个可以做为排序算法）//后面的堆排序需要用到这种方法void inorderBST(BST p){if (p){inorderBST(p->lChild);cout << p->key << " ";inorderBST(p->rChild);}}int main(void){BST T;createBST(T);inorderBST(T);cout << endl;return 0;
}
实验结果：
如果有可能，我带你去远行。躺在德德玛的草原，
