【数据结构】二叉排序树、平衡二叉树

1. 二叉排序树(BST)

1. 定义

二叉排序树，又称二叉查找树（BST，Binary Search Tree）。

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

左子树上所有结点的关键字均小于根结点的关键字。
右子树上所有结点的关键字均大于根结点的关键字。
左子树和右子树又各是一棵二叉排序树。

对二叉排序树进行中序遍历，可以得到一个递增的有序序列。

二叉排序树可用于元素的有序组织、搜索。

2. 查找

左子树结点值 < 根节点值 < 右子树根节点值

若树非空，目标值与根结点的值比较：

若相等，则查找成功；
若小于根结点，则在左子树上查找，否则在右子树上查找。
查找成功，返回结点指针；查找失败，返回NULL。

普通循环实现方法：

// 二叉排序树根结点
typedef struct BSTNode{
    int key;
    struct BSTNode *lchild,*rchild;
}BSTNode,*BSTree;

// 在二叉排序树中查找值为key的结点
BSTNode *BST_Search(BSTree T,int key){
    while(T!=NULL&&key!=T->key){  // 若树空或者等于根结点的值，则结束循环
        if(key<T->key){
            T=T->lchild;  // 小于，在左子树上查找
        }else{
            T=T->rchild;  // 大于，在右子树上查找
        }
    }
    return T;
}

递归实现方法：

// 二叉排序树根结点
typedef struct BSTNode{
    int key;
    struct BSTNode *lchild,*rchild;
}BSTNode,*BSTree;

// 在二叉排序树中查找值为key的结点
BSTNode *BSTSearch(BSTree T,int key){
    if(T==NULL){
        return NULL;  // 查找失败
    }
    if(key==T->key){
        return T;  // 查找成功
    }else if(key<T->key){
        return BSTSearch(T->lchild,key);  // 在左子树中找
    }else{
        return BSTSearch(T->rchild,key);  // 在右子树中找
    }
}

说明：使用普通循环最坏空间复杂度为O(1)。使用递归最坏空间复杂度为O(h)。

3. 插入

若原有二叉排序树为空，则直接插入结点；否则，若关键字k小于根结点的值，则插入左子树，若关键字k大于根结点值，则插入右子树。

// 在二叉排序树插入关键字为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;  // 返回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,k);  // 插入到右子树
    }
}

说明：新插入的结点一定是叶子结点。

使用递归插入的最坏空间复杂度为O(h)。

// 二叉排序树的构造
void Creat_BST(BSTree &T,str[],int n){
    T=NULL;  // 初始时T为空树
    int i=0;
    while(i<n){  // 依次将每个关键字插入到二叉排序树中
        BST_Insert(T,str[i]);
        i++;
    }
}