二叉排序树

二叉排序树的二叉链表类型定义

typedef struct btnode
{
    KeyType key;
    struct btnode *lchild, *rchild; // 指向左右孩子的指针 
} BSTNode, *BinTree;                // BinTree 为指向二叉链表结点的指针类型

BinTree bst; // bst 为指向二叉排序树根结点的指针

二叉排序树上的查找

BinTree SearchBST(BinTree bst, KeyType key)
{
    // 在根指针 bst 所指的二叉排序树上递归地查找键值等于 key 的结点。若成功，则返回指向该结点的指针，否则返回空指针
    if (bst == NULL) 
        return NULL;                             
    else if (key == bst->key) 
        return bst;                         // 查找成功 
    else if (key < bst->key)
        return SearchBST(bst->lchild, key); // 继续在左子树中查找
    else
        return SearchBST(bst->rchild, key); // 继续在右子树中查找     
}

二叉排序树的插入

由于二叉排序树这种动态树表是在查找过程中，不断地往树中插入不存在的键值而形成的，所以插入算法必须包含查找过程，并且是在查找不成功时进行插入新结点的操作。新插入的结点是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子。

例如，在下图所示的二叉排序树中，查找 key=22 不成功时，到达结点 20 的右子树，该位置恰好是新结点 22 的插入位置。

基于以上分析，可以将算法 SearchBST 略加修改，得到插入算法描述如下：

// 将查找算法略加修改
BinTree SearchBST(BinTree bst, KeyType key, BSTNode *f)
{
    // 指针 f 指向查到的结点的双亲，其初始值为 NULL
    if (bst == NULL) 
        return NULL;
    else if (key == bst->key)
        return bst;
    else 
        if (key < bst->key)
            return SearchBST(bst->lchild, key, bst); // 继续在左子树中查找
        else 
            return SearchBST(bst->rchild, key, bst); // 继续在右子树中查找
}

int InsertBST(BinTree bst, KeyType key)
{
    // 若根指针 bst 所指的二叉排序树上无键值为 key 的结点，则插入这个结点，并返回 1，否则返回 0
    BSTNode *p, *t, *f;
    f = NULL;
    t = SearchBST(bst, key, f);
    if (t == NULL) {
        p = (BSTNode *)malloc(sizeof(BSTNode));
        p->key = key;
        p->lchild = NULL;
        p->rchild = NULL;
        if (f == NULL)
            bst = p;       // 被插入结点 p 为新的根结点
        else if (key < f->key)
            f->lchild = p; // 被插入结点 p 为 f 左孩子
        else
            f->rchild = p; // 被插入结点 p 为 f 右孩子       
        return 1; 
    } else {
        return 0;                
    }
}