什么是二叉搜索树
一棵二叉树的节点x，如果y是x左子树中的一个节点，那么y.keyx.key

二叉树的数据结构

[cpp]
typedef int data_t;

typedef struct BST
{
data_t data;
struct BST *left;
struct BST *right;
struct BST *parent;
}BST;

typedef int data_t;

typedef struct BST
{
data_t data;
struct BST *left;
struct BST *right;
struct BST *parent;
}BST;
二叉搜索树的遍历
我们可以通过一个简单的递归算法按序输出二叉搜索树中的所有关键字，这种算法称为中序遍历，类似的，先序遍历输出的根的关键字在其左右子树的关键字之间，后续遍历输出根的值在其左右子树的值之后

以下为二叉树的中序遍历的递归算法与非递归算法

[cpp]
void bst_nonrecur_inorder(BST *root)//use stack to store tree's node
{
stack s_bst;
while(s_bst.size() || root!=NULL)
{
if(root!=NULL)
{
s_bst.push(root);
root = root->left;
}
else
{
root = s_bst.top();
s_bst.pop();
cout << root->data << " ";
root = root->right;
}
}
}

void bst_inorder(BST *root)
{
if(root==NULL)
return ;
else
{
bst_inorder(root->left);
cout << root->data << " ";
bst_inorder(root->right);
}
}

void bst_nonrecur_inorder(BST *root)//use stack to store tree's node
{
stack s_bst;
while(s_bst.size() || root!=NULL)
{
if(root!=NULL)
{
s_bst.push(root);
root = root->left;
}
else
{
root = s_bst.top();
s_bst.pop();
cout << root->data << " ";
root = root->right;
}
}
}

void bst_inorder(BST *root)
{
if(root==NULL)
return ;
else
{
bst_inorder(root->left);
cout << root->data << " ";
bst_inorder(root->right);
}
}
注意：如果x是一棵n个结点字树的根，那么遍历该树需要O(n)时间

二叉树的查询
我们经常需要查找一个存储在二叉搜索树中的关键字。除了search操作之外，还支持诸如minnum,maxinum,successor(求后继节点),predecessor(前驱结点)的查询操作

树的查找
输入指向树根节点的指针和一个关键字k，如果这个检点存在，bst_search返回一个指向关键字k的节点的指针，否则返回NULL
下面为树查找的递归实现与迭代实现
[cpp]
//search a node in the binary-search-tree
BST *bst_search(BST *root, data_t data)
{
if(root==NULL || root->data== data)
return root;
if(datadata)
return bst_search(root->left, data);
else
return bst_search(root->right, data);
}

BST *bst_iterative_search(BST *root, data_t data)
{
if(root==NULL || root->data == data)
return root;
while(root!=NULL && data!=root->data)
{
if(datadata)
root = root->left;
else if(data>root->data)
root = root->right;
}
return root;
}

//search a node in the binary-search-tree
BST *bst_search(BST *root, data_t data)
{
if(root==NULL || root->data== data)
return root;
if(datadata)
return bst_search(root->left, data);
else
return bst_search(root->right, data);
}

BST *bst_iterative_search(BST *root, data_t data)
{
if(root==NULL || root->data == data)
return root;
while(root!=NULL && data!=root->data)
{
if(datadata)
root = root->left;
else if(data>root->data)
root = root->right;
}
return root;
}

最大关键字元素和最小关键字元素
从树根开始沿着left孩子指针，直到遇到一个一个节点的left指针为NULL，那么该节点的值就是该二叉搜索树的最小关键字。同理，从树根沿着right孩子指针，直到遇到一个节点的right指针为NULL为止，那么该节点的值就是该二叉搜索树的最大关键字
以下为实现代码
[cpp]
//return the minnest node of tree
BST *bst_mininum(BST *root)
{
if(root == NULL)
return NULL;
while(root->left!=NULL)
root = root->left;
return root;
}

//return the maxest node of tree
BST *bst_maxinum(BST *root)
{
if(root == NULL)
return NULL;
while(root->right!=NULL)
root = root->right;
return root;
}