二叉搜索(排序)树

一、定义
       二叉排序树又叫二叉查找树或者二叉搜索树，它首先是一个二叉树，而且必须满足下面的条件：
1）若左子树不为空，则左子树上所有结点的值均小于它的根节点的值；
2）若右子树不为空，则右子树上所有结点的值均大于它的根结点的值；
3）左右子树也分别为二叉排序树；

二、二叉树的遍历

二叉树

• 前序遍历（根-左-右）：ABDGHECKFIJ
• 中序遍历（左-根-右）：GDHBEAKCIJF
• 后序便利（左-右-根）：GHDEBKJIFCA
• 二叉搜索树的数据大小关系为：G<D<H<B<E<A<K<C<I<J<F，即中序遍历顺序；
• 从创建好的二叉搜索树，我们可以直接使用中序遍历得到排序；

三、二叉树在搜索上的优势
       数组的搜索比较方便，可以直接使用下标，但删除或插入就比较麻烦了，而链表与之相反，删除和插入都比较简单，但是查找很慢，这自然也是与这两种数据结构的存储方式有关，数组是取一段相连的空间，而链表是每创建一个节点便取一个节点所需的空间，只是使用指针进行连接，空间上并不是连续的，而二叉树就既有链表的好处，又有数组的优点；