数据结构与算法-二叉搜索树的查找

梦里梦外; 2022-05-29 12:20 152阅读 0赞

**二叉搜索树（BST， Binary Search Tree）,也称二叉排序树或二叉查找树**

**二叉搜索树**：一颗二叉树，可以为空；如果不为空，满足一下性质：

1.  非空左子树的所有键值小于其根节点的键值；
2.  非空右子树的所有键值大于其根节点的键值；
3.  左右子树都是二叉搜索树。

二叉搜索树递归查找实现：

// 传入树的根节点，并传入要查找的数字，如果有，返回对应的节点的地址，如果没有，返回空。
    BinaryTreeNode* BST_Recursive( BinaryTreeNode* BST, int x){
        if (!BST) return NULL;
        if (x > BST->val)
            return BST_Recursive(BST->right, x);
        else if(x < BST->val)
            return BST_Recursive(BST->left, x);
        else
            return BST;
    }

二叉搜索树迭代查找实现：

// 传入树的根节点，并传入要查找的数字，如果有，返回对应的节点的地址，如果没有，返回空。
    BinaryTreeNode* BST_Recurence( BinaryTreeNode* BST, int x){
        while( BST ){
            if (x > BST->val)
                BST = BST->right;
            else if(x < BST->val)
                BST = BST->left;
            else
                return BST;
        }
        return NULL;
    }

全部代码如下：

#include <iostream>
    
    using namespace std;
    
    struct BinaryTreeNode {
        int val;
        BinaryTreeNode *left;
        BinaryTreeNode *right;
        BinaryTreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };
    
    BinaryTreeNode* BST_Recursive( BinaryTreeNode* BST, int x){
        if (!BST) return NULL;
        if (x > BST->val)
            return BST_Recursive(BST->right, x);
        else if(x < BST->val)
            return BST_Recursive(BST->left, x);
        else
            return BST;
    }
    
    BinaryTreeNode* BST_Recurence( BinaryTreeNode* BST, int x){
        while( BST ){
            if (x > BST->val)
                BST = BST->right;
            else if(x < BST->val)
                BST = BST->left;
            else
                return BST;
        }
        return NULL;
    }
    
    int main(){
        BinaryTreeNode a(8);
        BinaryTreeNode b(3);
        BinaryTreeNode c(10);
        BinaryTreeNode d(1);
        BinaryTreeNode e(6);
        BinaryTreeNode f(15);
        a.left = &b;
        a.right = &c;
        b.left = &d;
        b.right = &e;
        c.right = &f;
    
        BinaryTreeNode *result = BST_Recursive(&a, 10);
        if(!result)
            printf("no\n");
        else
            printf("%d\n",result->val);
    
        BinaryTreeNode *result1 = BST_Recurence(&a, 10);
        if(!result1)
            printf("no\n");
        else
            printf("%d\n",result1->val);
        return 0;
    }