二分查找树BST(Binary Search Tree)目的是为了提高查找的性能,其查找在平均和最坏的情况下都是logn级别,接近二分查找。其特点是:每个节点的值大于其任意左侧子节点的值,小于其任意右节点的值。

一.BST节点的构造

二分查找树的节点与普通二叉树的节点类似:
typedef struct tree{
	int num; //二叉树节点的值
	struct tree *pLeft; //指向左孩子的指针
    struct tree *pRight;	//指向右孩子的指针    
}BST;