二叉搜索树在二叉树的结构基础上，增加了中序遍历即为按序输出各节点的Val值。
image
其基本数据结构的C++结构体描述为：
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
构造二叉搜索树、查找某一元素、查找最大元素、查找最小元素较为简单，直接附代码：
class SearchTree{
//二叉搜索树的查找(递归版本)
TreeNode*TreeSearch(TreeNode* pRoot, int key)
{
if(!pRoot || pRoot->val == key)
{
return pRoot;
}
if(key < pRoot->val)
{
return TreeSearch(pRoot->left, key);
}
else{
return TreeSearch(pRoot->right, key);
}
}
//二叉搜索树的查找(非递归版本)
TreeNode*TreeSearchIterative(TreeNode* pRoot, int key)
{
while (pRoot && key != pRoot->val){
if(key < pRoot->val)
{
pRoot = pRoot->left;
}
else{
pRoot = pRoot->right;
}
}
return pRoot;
}
//查找最大值
TreeNode*FindMax(TreeNode* pRoot)
{
while(pRoot->right){
pRoot = pRoot->right;
}
return pRoot;
}
//查找最小值
TreeNode*FindMin(TreeNode* pRoot)
{
while (pRoot->left){
pRoot = pRoot->left;
}
return pRoot;
}
};
