404 字
1 分钟
二叉搜索树查找最大（小）值
二叉搜索树查找最大最小值
上篇文章，我们知道了二叉搜索树是节点大于所有左子树并且小于所有右子树的一种二叉树。那么利用这个特性，我们要实现找到最大值和最小值，可以说是相当简单！
我们一直找节点的左孩子，就能找到最小值。同理，一直找节点的右孩子，就能找到最大值！
由于我们不能随便乱搞root，所以我们会拷贝一个root作为nownode来操作这个二叉树！
接着我们来考虑利用递归实现查找。
递归思想大道至简，不要想那么复杂，就是：大化小，懂终止。意思是把大问题拆解成小问题，必须写上终止条件！防止内存溢出。
一、循环实现
你可能会问，猪宝猪宝，你不是说用递归实现吗？
我知道你很疑惑，但是你先别疑惑，先来点简单的开胃菜
#include<iostream>using namespace std;struct BstNode{ int data; BstNode *left; BstNode *right;};int findmin(BstNode *root){ BstNode *nownode=root; //优先处理空树的情况 if(root==NULL){ cout<<"This is a empty tree!\n"; } //查找最小 while(nownode->left!=NULL){ nownode=nownode->left; } return nownode->data;}最好nownode指在8节点上。
二、递归实现
通过递归的话，我们就不需要用nownode指针来遍历了，但是依然是遍历，递归本身类似于遍历。
#include<iostream>using namespace std;struct BstNode{ int data; BstNode *left; BstNode *right;};int findmin(BstNode *root){ //优先处理空树的情况 if(root==NULL){ cout<<"This is a empty tree!\n"; } //写上终止条件哦！！！！！！！！！！！！ if(root->left==NULL){ return root->data; } return findmin(root->left);}巧妙吧。
函数调用栈我就不模拟咧，前面文章已经写过很多遍了，偷个懒😋
查找最大值基本，哦不，可以说完全一样。
#include<iostream>using namespace std;struct BstNode{ int data; BstNode *left; BstNode *right;};int findmax(BstNode *root){ //优先处理空树的情况 if(root==NULL){ cout<<"This is a empty tree!\n"; } //写上终止条件哦！！！！！！！！！！！！ if(root->right==NULL){ return root->data; } return findmin(root->right);}ok哈！天天开心！
二叉搜索树查找最大（小）值
https://fatdog.20060113.xyz/posts/bst-max-min/ 部分信息可能已经过时