二叉排序树（Binary Sort Tree）又叫二叉搜索树（Binary Sreach Tree）,简称BST。
二叉排序树的性质：如果任一结点的左子树非空，则左子树的所有结点的值都小于根结点的值；如果任一结点的右子树非空，则右子树的所有结点的值都大于根结点的值。
这个性质怎么理解呢？
现在比如说我要将 7 4 5 6 1 8 9这七个数放到一个二叉排序树中
首先，将7放入一个节点：
下面放第二个数字 4 ，这个数字在放的时候需要和我们的根节点比较大小，比根节点大就放在右边，比它小就放在左边，4比7小因此应该放在左边。
接下来放5，将5和7比较，发现比7小，因此应该放在左边，但这时左边已经有一个4了，那么我们需要把5和4进行比较，5大于4，因此应该放在4的右边。
接下来插6，6和7比，比7小，再和4比，比4大，再和5比，比5大，因此应该放在5的右边。
接下来放1，应该就放在4的左边。
接下来放8，8比7大，应该放在7的右边。
最后一个9，就应该放在8的右边。
至此，就将这几个数放在二叉排序树中了。
知道原理之后，就需要通过代码实现了。
#include
#include
typedef struct node {
int data;
struct node *left;
struct node *right;
}Node;
typedef struct tree {
Node *root;
}Tree;
void create_tree(Tree *tree, int val)
{
Node *node = (Node*)malloc(sizeof(Node)); //定于一个节点，将数放到节点中
node->data = val;
node->left = NULL;
node->right = NULL;
if (tree->root == NULL) {
tree->root = node; //如果根为空，就将这个节点放到根节点
}
else {
Node *temp = tree->root; //定义指针指向根节点
while (temp != NULL) {
if (val < temp->data) { //如果要放入的值小于根节点
if (temp->left == NULL) { //根节点左孩为空，就直接放入
temp->left = node;
return;
}
else {
temp = temp->left; //根节点左孩不为空，就指向下一个左孩节点
}
}
else {
if (temp->right == NULL) { //右孩为空，直接放入
temp->right = node;
return;
}
else {
temp = temp->right; //右孩不为空，指向下一个右孩节点
}
}
}
}
}
int main(int argc, char **argv)
{
int a[7] = {7,4,5,6,1,8,9};
Tree tree;
tree.root = NULL;
int i;
int len = sizeof(a) / sizeof(int);
for (i=0; i create_tree(&tree, a[i]); } return 0; } 遍历方法有三种，前序遍历，中序遍历，后序遍历，详细的情况在我上一篇文章中有讲解。 其中二叉排序树有一个性质比较重要，二叉排序树使用中序遍历输出的时候，输出的值是从小到大排列的。 总的代码如下 #include #include typedef struct node { int data; struct node *left; struct node *right; }Node; typedef struct tree { Node *root; }Tree; void create_tree(Tree *tree, int val) { Node *node = (Node*)malloc(sizeof(Node)); //定于一个节点，将数放到节点中 node->data = val; node->left = NULL; node->right = NULL; if (tree->root == NULL) { tree->root = node; //如果根为空，就将这个节点放到根节点 } else { Node *temp = tree->root; //定义指针指向根节点 while (temp != NULL) { if (val < temp->data) { //如果要放入的值小于根节点 if (temp->left == NULL) { //根节点左孩为空，就直接放入 temp->left = node; return; } else { temp = temp->left; //根节点左孩不为空，就指向下一个左孩节点 } } else { if (temp->right == NULL) { //右孩为空，直接放入 temp->right = node; return; } else { temp = temp->right; //右孩不为空，指向下一个右孩节点 } } } } } void preorder(Node *node) { if (node != NULL) { printf("data is %d\n",node->data); preorder(node->left); preorder(node->right); } } void inorder(Node *node) { if (node != NULL) { inorder(node->left); printf("data is %d\n",node->data); inorder(node->right); } } void postorder(Node *node) { if (node != NULL) { postorder(node->left); postorder(node->right); printf("data is %d\n",node->data); } } int main(int argc, char **argv) { int a[7] = {7,4,5,6,1,8,9}; Tree tree; tree.root = NULL; int i; int len = sizeof(a) / sizeof(int); for (i=0; i create_tree(&tree, a[i]); } inorder(tree.root); return 0; }