二叉排序树

二叉排序树（Binary Sort Tree）,又叫二叉查找树。
它是一棵空树或者是具有以下性质的数

  • 左子树不为空，左子树所有节点的值均小于自身根节点的值
  • 右子树不为空，右子树所有节点的值均大于自身根节点的值
  • 左右子树也是二叉排序树

二叉排序树-查找

  • 递归查找二叉排序树
  • 若查找成功则指针指向该元素节点true
  • 否则指针指向查找路径上访问的最后一个节点返回false

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// SearchBST为递归函数,lchild为左孩子,rchild为右孩子

Status SearchBST(BiTree T,int key,BiTree f,BiTree *p){
    if(!T)
    {
        *p = f;
        return FALSE;
    }
    else if (key==T->data){
        *p = T;
        return TRUE;
    }
    else if (keydata){
        return SearchBST(T->lchild,key,T,p);
    else
        return SearchBST(T->rchild,key,T,p);
    }
}

算法分析

  • 二叉排序树的查找运用了构造二叉树的特性，节点中满足一定的次序关系即：左子树节点一定比其双亲节点小，右子树节点一定比其双亲节点大
  • 最少查找为1
  • 最多查找为二叉排序树的深度
  • 二叉排序树的查找性能取决于二叉排序树的形状（深度）

算法复杂度