数据结构与算法-二叉排序树的最大最小值搜索

港控/mmm° 2022-05-29 13:44 172阅读 0赞

**二叉排序树的最小搜索就是一直往左边找，最左边的节点就是最小值。**  
**二叉排序树的最小搜索：**  
递归实现：

BinaryTreeNode* Find_Min(BinaryTreeNode* BST){
        if(!BST)
            return NULL;
        else if( !BST->left )
            return BST;
        else
            return Find_Min( BST->left );
    }

循环实现：

BinaryTreeNode* Find_Min_Recurrence(BinaryTreeNode* BST){
        if(BST)
            while(BST->left)
                BST = BST->left;
        return BST;
    }

**二叉排序树的最大搜索就是一直往右边找，最右边的节点就是最大值。**  
**二叉排序树的最大搜索：**  
递归实现：

BinaryTreeNode* Find_Max(BinaryTreeNode* BST){
        if(!BST)
            return NULL;
        else if( !BST->right )
            return BST;
        else
            return Find_Max( BST->right );
    }

循环实现：

BinaryTreeNode* Find_Max_Recurrence(BinaryTreeNode* BST){
        if(BST)
            while(BST->right)
                BST = BST->right;
        return BST;
    }

测试程序：

#include <iostream>
    
    using namespace std;
    
    struct BinaryTreeNode {
        int val;
        BinaryTreeNode *left;
        BinaryTreeNode *right;
        BinaryTreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };
    
    BinaryTreeNode* Find_Min(BinaryTreeNode* BST){
        if(!BST)
            return NULL;
        else if( !BST->left )
            return BST;
        else
            return Find_Min( BST->left );
    }
    
    
    BinaryTreeNode* Find_Min_Recurrence(BinaryTreeNode* BST){
        if(BST)
            while(BST->left)
                BST = BST->left;
        return BST;
    }
    
    BinaryTreeNode* Find_Max(BinaryTreeNode* BST){
        if(!BST)
            return NULL;
        else if( !BST->right )
            return BST;
        else
            return Find_Max( BST->right );
    }
    
    BinaryTreeNode* Find_Max_Recurrence(BinaryTreeNode* BST){
        if(BST)
            while(BST->right)
                BST = BST->right;
        return BST;
    }
    
    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* res = Find_Min(&a);
        if(!res)
            printf("no\n");
        else
            printf("%d\n",res->val);
    
        BinaryTreeNode* res1 = Find_Min_Recurrence(&a);
        if(!res1)
            printf("no\n");
        else
            printf("%d\n",res1->val);
    
        BinaryTreeNode* res3 = Find_Max(&a);
        if(!res3)
            printf("no\n");
        else
            printf("%d\n",res3->val);
    
        BinaryTreeNode* res4 = Find_Max_Recurrence(&a);
        if(!res4)
            printf("no\n");
        else
            printf("%d\n",res4->val);
        return 0;
    }