二叉排序树又称二叉查找树

非递归实现BST的查找操作空间复杂度为O(1)，但是递归实现的空间复杂度为O(h) ，h为树的高度

#include <iostream>
using namespace std;
typedef struct BSTNode{
    int key;
    struct BSTNode *lchild,*rchild;
}BSTNode,*BSTree;

//非递归，空间复杂度为O(1)
BSTNode *BST_Search(BSTree T,int key){
    while(T!=NULL&&key!=T->key){
        if(key<T->key)
            T=T->lchild;
        else
            T=T->rchild;
    }
    return T;
}

//递归，空间复杂度为O(h)
BSTNode *BSTSearch(BSTree T,int key){
    if(T==NULL)
        return NULL;
    if(key==T->key)
        return T;
    else if(key<T->key)
        return BSTSearch(T->lchild,key);
    else
        return BSTSearch(T->rchild,key);
}