1. 二叉排序树

• 如果它的左子树不为空，那么左子树上的所有结点的值均小于它的根结点的值
• 如果它的右子树不为空，那么右子树上的左右结点的值均大于它的根结点的值
• 根结点的左子树和右子树又是二叉排序树。
  二叉排序树通常采用二叉链表作为存储结构。
  中序遍历二叉排序树便可得到一个递增有序序列。
  一个无序序列可以通过构造一棵二叉排序树变成一个有序序列，构造树的过程即是对无序序列进行排序的过程。

二叉排序树的二叉链表存储表示

typedef struct
{
    KeyType key;
    InfoType otherinfo;
}ElemType;
typedef struct BSTNode
{
    ElemType data;
    struct BSTNode *lchild,*rchild;
}BSTNode,*BSTree;

(1) 二叉排序树的递归查找

1. 若二叉排序树为空，则查找失败，返回空指针。
2. 若二叉排序树非空。将给定值key与根结点的关键字T->data.key进行比较。

• 若key等于T->data.key，则查找 成功，返回根结点地址。
• 若key小于T->data.key，则递归查找左子树。
• 若key大于T->data.key，则递归查找右子树。

BSTree SearchBST(BSTree T, KeyType key)//递归算法  
{           
    If((!T)|| key == T->data.key)     return T;                   
    else if(key <  T->data.key)      return SearchBST(T->lchild, key);           
    else    return SearchBST(T->rchild, key);  
} 
 

(2) 二叉排序树的插入

1. 若二叉树为空，则将待插入结点*S作为根结点插入到空树。
   2.若二叉排序树非空，则将key与根结点的关键字 T->data.key进行比较：

• 若key小于 T->data.key，则将*S插入左子树。
• 若key大于 T->data.key，则将*S插入右子树。

时间复杂度：插入一个节点算法的O(㏒2n)，插入n个的总复杂度为O(n㏒2n)。
二叉排序树插入的基本过程是查找，所以时间复杂度同查找一样。

void InsertBST(BSTree &T,ElemType e)
{
    if(!T)
    {
        S=new BSTNode;
        S->data =e;
        S->lchild = S->rchild =NULL;
    }
    else if(e.key <  T->data.key)  InsertBST(T->lchild,e);
    else if(e.key >  T->data.key)  InsertBST(T->rchild,e);
}

(3) 二叉排序树的创建

1. 将二叉排序树初始化为空树。
   2.读入一个关键字为key的结点。
2. 如果读入的关键字key不是输入结束的标志，则循环执行以下操作：

• 将此结点插入二叉排序树T中：
• 读入一个关键字为key的结点。

void CreateBST(BSTree &T)
{
    T=NULL;
    cin >> e;
    while(e.key != ENDFLAG)
    {
      InsertBST(T,e)    ;
      cin>>e;
    }
}

（4）二叉排序树的删除

void DeleteBST(BSTree &T,KeyType key)

2.平衡二叉树

（1） 左子树和右子树的深度之差的绝对值不超过1.
（2）左子树和右子树也是平衡二叉树。
若将二叉树上结点的平衡因子定义为该结点左子树和右子树的深度之差，则平衡二叉树上所有结点的平衡因子只可能是-1、0和1。