算法题请提供一个函数实现二叉排序树的查找功能。

[问答题]

算法题

请提供一个函数实现二叉排序树的查找功能。

二叉排序树的定义：

二叉排序树又称二叉查找树，它或者是一棵空树，或者是具有如下性质的二叉树：

1、若它的左子树非空，则左子树上所有结点的值均小于根结点的值；

2、若它的右子树非空，则右子树上所有结点的值均大于或等于根结点的值；

3、左右子树本身就是两棵二叉排序树。

节点的结构定义如下：

typedef struct tagNode

{

int iKey; ///结点的键值

struct tagNode *pLChild; ///左子树的指针

struct tagNode *pRChild; ///右子树的指针

}NODE, *PNODE;

函数定义如下：

PNODE SearchTree(PNODE pRoot, int iKey, PNODE &pFather);

编程小海浪

public static boolean sort(BinaryTree root, int key, BinaryTree p){
        if(root == null){
            f = p;
            System.out.println("查找失败！");
            return false;
        }
        else if(root.val == key){
            f = root;
            System.out.println("查找成功！");
            return true;
        }
        else if(root.val >= key)
            return sort(root.left, key, root);
        else
            return sort(root.right, key, root);
    }

发表于 2019-09-19 17:07:35 回复(1)

瀟嚴

/*在根指针bst所指二叉排序树中，递归查找某关键字等于key的元素，若查找成功，返回指向该元素结点指针，否则返回空指*/
BSTree  SearchBST(BSTree bst, KeyType 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);/*在右子树继续查找*/
    }

编辑于 2019-09-10 15:28:32 回复(0)