二叉搜索树
二叉查找树又叫二叉排序树，属于二叉树的一种特例，是空树或具有如下特点的树：
（1） 若左子树非空，则左子树上的所有节点的关键字值都小于根节点的关键字。
（2） 若右子数非空，则右子树上的所有节点的关键字值都大于根节点的关键字。
（3） 左右子树又是一个二叉搜索树。

由二叉搜索树的定义可知，在一棵非空的二叉搜索树中，其结点的关键字是按照左子树、根和右子树有序的，所以对它进行中序遍历得到的结点序列是一个有序序列。

二叉查找树的这种特殊性质使得它在查找元素的时候特别的方便,每一次查找都可以去掉一半的元素,因此查找的时间是O(logN).

C++代码实现
// 二叉查找树.cpp : Defines the entry point for the console application.
//

#include “stdafx.h”
#include
using namespace std;
struct Node
{
int key;//结点值
struct Node *parent;//父结点
struct Node *left;//左结点
struct Node *right;//右结点
};

void PrintTree(struct Node *Root)
{
struct Node *pointer=(struct Node*)malloc(sizeof(struct Node));
pointer=Root;
if(pointer!=NULL)
{
PrintTree(pointer->left);
printf(“%d “,pointer->key);
PrintTree(pointer->right);
}
}

struct Node *Insert(struct Node *Root,struct Node *newNode)
{
struct Node *back=(struct Node*)malloc(sizeof(struct Node));
struct Node *pointer=(struct Node*)malloc(sizeof(struct Node));
back=NULL;
pointer=Root;

//找到要插入的位置
while(pointer!=NULL)
{
back=pointer;
if(newNode->key key)
pointer=pointer->left;
else
pointer=pointer->right;
}

//新结点的Parent指针先指向父结点
newNode->parent=back;

if(back==NULL)
Root=newNode;//树为空，新结点成为树根
else
{
if(newNode->keykey)
back->left=newNode;
else
back->right=newNode;
}

return Root;
}

int main(int argc, char* argv[]){

struct Node *Root=NULL;
int value;
int n=0;
printf(“Please input the value you want to input:”);
while(n++<10){
scanf(“%d”,&value);
struct Node *newNode=(struct Node*)malloc(sizeof(struct Node));//或者 Node *newNode=new Node;
newNode->key=value;
newNode->parent=NULL;
newNode->left=NULL;
newNode->right=NULL;
Root=Insert(Root,newNode);
}
PrintTree(Root);
}
FROM:http://hi.baidu.com/tralon/blog/item/e3c5abfa08d9e91f6d22ebb3.html