二叉排序树

1.动态查找：.

动态查找所含的数据元素的个数可以随着所做的插入、删除等操作增加或减少。

2.定义：

二叉排序树(Binary SortTree）是具有下列性质的二叉树:
⑴若左子树不空，则左子树上所有结点的值均小于根结点的值;若右子树不空,则右子树上所有结点的值均大于根结点的值。简记为左小右大
(2)左右子树也都是二叉排序树。
示例：

注意：对二叉排序树进行中序遍历得到有序序列

3 12 24 37 45 53 61 78 90 100

3.二叉排序树的查找过程：

（1）若根结点的关键字值等于查找的关键字，成功;

（2）若根结点的关键字值不等于查找的关键字，

1.若小于根结点的关键字值,查其左子树;

2.若大于根结点的关键字值，查其右子树。

在左右子树上的操作类似。

结点结构：

template 
struct Node
{
T key;
~//其他域，按需添加
};

二叉排序树的存储结构：

 查找算法：

template 
void BinTree::searchBST(bittree *t,T key) //查找关键字为key的元素
{
if(!t||t->data.key==key)
 {
   if(t->data.key==key) //结点关键字与key相等
     cout<<"数据元素为"<data.key)  //结点大于key
   searchBST(t->lchild;key);
else   //结点小于key
   searchBST(t->rchild;key);
}