二叉搜索树是专门有利于搜索(时间复杂度为logn)的二叉树。
生成一棵二叉搜索树关键是不断地插入数据到该树中，若当前的root为NULL，则当前插入的节点为root，否则比较左右树插入，直到为NULL为之。
二叉搜索树的插入代码为:
void BST_Insert(int key)
{
构建当前节点current,初始化current,设置其value=key,左右父节点都为NULL;
//用x,y两个指针来跟踪current放置的位置
y=NULL;
x=root;
while(x)//x有下面的节点时
{
y=x;
x的key和当前参数里面的key做对比，若大于当前key，则x=left[x],否则x=right[x];
}
比较y和NULL的关系，若y==NULL,则root=NULL，有root=current;
设置parent[current]=y;
比较current的key和y的key的大小，若大，则left[y]=current,否则right[y]=current;
//插入完毕
}
使用代码表示为:
#include <iostream>
#include <cstdlib>
using namespace std;
#ifndef NULL
#define NULL 0
#endif
#ifndef MAXSIZE
#define MAXSIZE 10
#endif
typedef struct BST//Binary Search Tree
{
int key;
//maybe there are some other satellites
struct BST* left;
struct BST* right;
struct BST* parent;
} BST;
BST* root=NULL;
void BST_Insert(int key)//add value key to the Binary Search Tree
{
BST* y=NULL;//y records the parent node
BST* x=root;//x records the current node
BST* node = new BST();
node->key = key;
node->left = NULL;
node->right = NULL;
node->parent = NULL;
while(x!=NULL)
{
y=x;
if(key<x->key)
x=x->left;
else
x=x->right;
}
node->parent=y;
if(y==NULL)
root = node;
else
{
if(key<y->key)
y->left=node;
else
y->right=node;
}
}
void BST_Delete(BST* p)
{
if(p)
{
BST_Delete(p->left);
BST_Delete(p->right);
delete p;
}
}
void BST_Build()
{
int temp;
for(int i=0;i<MAXSIZE;i++)
{
temp=rand()%MAXSIZE;
cout<<temp<<" ";
BST_Insert(temp);
}
cout<<endl;
}
void BST_Inorder_Walk(BST* p)
{
if(p)
{
BST_Inorder_Walk(p->left);
cout<<p->key<<" ";
BST_Inorder_Walk(p->right);
}
}
int main(int argc,char* argv[])
{
BST_Build();
BST_Inorder_Walk(root);
BST_Delete(root);
cout<<endl;
system("pause");
return 0;
}