#include "stdio.h"
typedef struct node
{
	int data ;
	node*lChild ;
	node*rChild ;
}TreeNode  ;
void Insert(TreeNode**root,int data)  //向二叉查找树中插入元素  采用非递归思想
{      
	 TreeNode * p=*root ;//获得根结点 
	 TreeNode*q=new TreeNode ;//分配一个要插入的新节点 
	 q->lChild=q->rChild=NULL ; //新分配节点的左节点=右节点等于NULL
	 q->data=data ;  //保存数据到节点    
     TreeNode *parent =p ; //用于保存父节点 
	 while(p!=NULL)  //循环搜索节点  
	 {
       parent=p ;  //首先parent指向root节点 
	   if(p->data>data)   //如果节点数据大于当前节点
		   p=p->lChild  ;//如果插入数据小于 节点数据那么指向左节点  我么最终是要找到一个NULL节点 
	   else
		   p=p->rChild  ;
	 }
	 //如果因为parent总是指向NULL节点的父节点 ,所以parent指向的节点不会为空,如果为空那么说明该树是一颗空的树。
	 if(parent==NULL) 
		 *root=q ; //将分配的节点作为根节点 
	 else if(parent->data>data)
		 parent->lChild=q ;   //<root左插
	 else
		 parent->rChild=q ;  //>root右插
} 

void InOrder(TreeNode*root)
{
	 if(root!=NULL)
	 {
	  InOrder(root->lChild) ;
	  printf("%d",root->data) ;
	  InOrder(root->rChild) ;
	 }
}
bool   Find(TreeNode*root,int fData)   //非递归方法查询
{
	if(root==NULL)
		return false ;  //搜索树为空返回false  
	while(root!=NULL)
	{  
		if(root->data==fData)
			return true ;  
		if(root->data>fData)
			root=root->lChild ;
		else
			root=root->rChild ;  
	}
    
   return false  ;
}

int main(int argc,char*argv[])
{
	 
    TreeNode *root=NULL;  //如果根节点指针在局部那么一定要初始化NULL否则程序崩溃 ,如果我们的指针是在全局定义的可以不初始化NULL全局变量放在静态存储区
	int a[]={2,3,6,8,0,9,3,1,5,7} ;
	for(int i=0;i<10;i++)
	Insert(&root,a[i]) ; 
	InOrder(root) ; 
	printf("\n") ;
	if(Find(root,0)) 
		printf("数据0找到\n") ;
	else
		printf("没有0数据\n") ;

	return 1 ;
}

二叉搜索树又称二叉查找树  , 他有这样的特点,根节点 的数据比他的左子树大.  比右节点小 ,中序遍历可以得到一棵升序的 序列 。

二叉搜索树可以采用递归和非递归方式建立 ,由于递归消耗内存较大 ,所以采用非递归方式 。