一、二叉搜索树

1、二叉搜索树（BST）：或者是一颗空树；或者是具有下列性质的二叉树：对于任何一个结点，设其值为K，则该结点的左子树(若不空)的任意一个结点的值都小于K；该结点的右子树(若不空)的任意一个结点的值都大于或等于K；而且它的左右子树也分别为二叉搜索树。

2、二叉搜索树的性质：按照中序周游将各结点打印出来，将得到按照由小到大的排列

3、二叉搜索树的效率就在于只需检索二个子树之一。从根结点开始，在二叉搜索树中检索值K。如果根结点储存的值为K，则检索结束。如果K小于根结点的值，则只需检索左子树。如果K大于根结点的值,就只检索右子树。这个过程一直持续到K被找到或者我们遇上了一个树叶。如果遇上树叶仍没有发现K，那么K就不在该二叉搜索树中。