二叉搜索树（1）

二叉搜索树在二叉树的结构基础上，增加了中序遍历即为按序输出各节点的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;
}
};