我们在上一篇博客中讲解了二叉树，这一次我们来实现二叉树的进阶——二叉查找树（Binary Search Tree），又称二插排序树(Binary Sort Tree)。所以简称为BST。二插查找树的定义如下：
1.若左子树不为空，则左子树上所有节点的值均小于它的根节点的值；
2.若右子树不为空，则右子树上所有节点的值均大于它的根节点的值；
3.左右子树也分别为二叉排序树；
二叉排序树的一个重要特点就是中序遍历是一个递增序列。示例代码上传至： https://github.com/chenyufeng1991/BinarySearchTree 。
（1）节点的构造
typedef int elemType; typedef struct BTNode{ int data; struct BTNode *lChild; struct BTNode *rChild; }BiTNode,*BiTree; |
（2）创建二叉树
创建二插排序树的过程就是一个不断插入节点的过程，并且最重要的就是查找插入的合适位置。
//创建二叉查找树 /** * 输入-1时创建结束,其实是一个不断插入的过程 */ int CreateBinarySearchTree(BiTree *T){ printf("请输入创建二叉查找树的数字序列：\n"); int num; scanf("%d",&num); while (num != -1) { Insert(T,num); scanf("%d",&num); } printf("%s函数执行，二叉查找树创建成功\n",__FUNCTION__); return 1; } |
（3）插入节点
//插入节点 void Insert(BiTree *T,int x){ //这里创建一个要插入的节点 BiTNode *pInsert = (BiTNode *)malloc(sizeof(BiTNode)); pInsert->data = x; pInsert->lChild = NULL; pInsert->rChild = NULL; if ((*T) == NULL) { *T = pInsert; } if ((*T)->lChild == NULL && x < (*T)->data) { (*T)->lChild = pInsert; } if ((*T)->rChild == NULL && x > (*T)->data) { (*T)->rChild = pInsert; } //递归实现 if (x < (*T)->data) { Insert(&(*T)->lChild, x); } if (x > (*T)->data) { Insert(&(*T)->rChild, x); } return; } |
（4）树的中序遍历和先序遍历
树的先序遍历+中序遍历可以唯一的确定一棵树。并且二叉排序树的中序遍历必定是一个递增的序列。用这样的方法可以来验证我们对一颗二叉排序树进行操作后是否正确。
//中序遍历二叉查找树 //打印的应该是一个递增的序列 void MiddleOrder(BiTree T){ if (T == NULL) { return; }else{ MiddleOrder(T->lChild); printf("%d ",T->data); MiddleOrder(T->rChild); } } //先序遍历二叉查找树 //因为先序遍历+中序遍历 可以唯一确定一棵树，等下可以验证树是否正确 void PreOrder(BiTree T){ if (T == NULL) { return; }else{ printf("%d ",T->data); PreOrder(T->lChild); PreOrder(T->rChild); } } |
