数据结构 -- 树形查找（一）二叉排序树

二叉排序树

二叉排序树的定义

二叉排序树，又称二叉查找树

一棵二叉树或者是空二叉树，或者是具有以下性质的二叉树：

左子树上所有结点的关键字均小于根结点的关键字

右子树上所有结点的关键字均大于根结点的关键字

左子树和右子树又各是一棵二叉排序树

（二叉排序树中序遍历，可以得到一个递增的有序序列）

二叉排序树的查找

typedef struct BiTNode{
    ElemType data;						//数据域
    struct BiTNode * lchild,*rchild;	//左右孩子
}BiTNode,*BiTree;

//查找实现
BSTNode *BST_Sreach(BSTree T,int key){
    while(T!=NULL&&key!=T->key){
        if(key<T->key) T=T->lchild;
        else T = T->rchild;
    }
    return T;
}//最坏时间复杂度O(1)

//递归实现
BSTNode *BST_Sreach(BSTree T,int key){
    if(T==NULL) return NULL;
    if(key == T->key) return T;
    else if(key < T->key) return BST_Sreach(T->lchild,key);
    else return BST_Sreach(T->rchild,key);
}//最坏时间复杂度O(n)

二叉排序树的插入

//在二叉排序树插入关键字为k的新结点（递归实现）
int BST_Insert(BSTree &T,int k){
    if(T==NULL){
        T=(BSTree)malloc(sizeof(BSTNode));
        T->key = k;
        T->lchild = T->rchild = NULL;
        return 1;
    }
    else if(k == T->key)	return 0;		//树中存在相同关键字的结点，插入失败
    else if(k<T->key)	return BST_Insert(T->lchild,k);
    else return BST_Insert(T->rchild,key);
}

二叉排序树的构造

//按照str[]中的关键字序列建立二叉排序树
void Create_BST(BSTree &T,int str[],int n){
    T = NULL;
    int i = 0;
    while(i<n){
        BST_Insert(T,str[i]);
        ++i;
    }
}

二叉排序树的删除

先搜索找到目标结点：

①若删除的结点z是叶结点，则直接删除

②若要删除的结点z只有一棵左子树或右子树，则让z的子树称为z的父节点的子树，代替z的位置

③若要删除的结点有左右两棵子树，则令z的直接后继（或直接前驱）代替z，然后从二叉排序树中删去这一个直接后继（或直接前驱），这样就转化成了第一或第二种情况

查找效率分析

查找长度 – 在查找运算中，需要对比关键字的次数称为查找长度，反映了查找操作的时间复杂度