二叉排序树查找 递归 非递归

ustbfym 2019-10-31

算法思想
首先将待查关键字key与根结点关键字t进行比较,如果:
1)key=t,则返回根结点地址;
2)key<t,则进一步查找左子树;
3)key>t,则进一步查找右子树;


对应的递归算法如下:

BSTree SearchBST(BSTree bst, ElemType key) {
    if (!bst)
        return NULL;
    else if (bst->key == key)
        return bst;
    else if (bst->key > key)
        return SearchBST(bst->lchild, key);
    else
        return SearchBST(bst->rchild, key);
}

对应的非递归算法如下:

BSTNode *BST_Search(Bitree T, ElemType key, BSTNode *&p) {
    p = NULL;//p指向待查找结点的双亲,用于插入和删除操作中
    while(T!=NULL&&key!=T->data){
        if (key < T->data)
            T = T->lchild;
        else
            T = T->rchild;
    }
}

相关推荐