#include "stdio.h"
#include "iostream.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  ;
}


void BST_Delete(TreeNode**tp ,int dData)   //删除节点 
{   
 TreeNode*root=*tp ;
    TreeNode* parent =NULL ;//父指针用来表示 是否是根节点  
 while(root!=NULL)  {  //循环查找
  if(dData<root->data)  //如果删除节点小于根节点数据
  {
   parent=root ;   //保存前一个节点的指针 
   root=root->lChild   ;  //dData小于root数据 那么查找左子树 

  } 
  else if(dData>root->data)
  {
   parent=root   ;
   root=root->rChild  ; //大于root数据那么查找右节点
 

  }
  else     //这里找到了节点 如果即不大于 节点数据 也不小于节点数据 并且节点不是NULL那就说明了 节点查找到了 ,揭晓来我们就需要判断节点并删除了。
  {        
   
   if(root->lChild==NULL&&root->rChild==NULL)  //是叶子节点  1、根节点    2、非根节点
   {
    if(parent==NULL)  //因为parent是NULL说明没有根节点   否则parent是不可能为NULL的
    {
     delete root  ;//直接删除根节点 
     root=NULL ;
        *tp=NULL ; 
     return ; //直接返回
    }
    else    //如果是非根节点的叶子节点  
    {  
     (parent->lChild==root)?(parent->lChild=NULL):(parent->rChild=NULL)  ;  //判断删除节点是parent的left还是right  
     delete root ;
     return  ;//对于叶子节点可以直接返回
     
    }
    
   }
   else if(root->lChild==NULL&&root->rChild!=NULL)  //待删除节点只有有孩子 情况和上面类似 
   { 
    if(parent==NULL)  //如果在是根节点 并且有右孩子的情况下 
    {
     *tp=root->rChild  ;//只有右孩子 那么指针移动到右孩子  保存到tp
     delete root ;  
     return ;
    }
    else
    {  
     (parent->lChild==root)?(parent->lChild=root->rChild):(parent->rChild=root->rChild) ; //令parent的left或者right指向 root的left
     delete root;
     return ;
    }
   }
   else  if(root->lChild!=NULL&&root->rChild==NULL)  //待删除节点只有左孩子 情况和上面类似 
   {
         
    if(parent==NULL)  //如果在是根节点 并且有右孩子的情况下 
    {
     *tp=root->lChild  ;//待删除节点只有左孩子 那么指针移动到左孩子
     delete root ;
     return ;
    }
    else
    {
     (parent->lChild==root)?(parent->lChild=root->lChild):(parent->rChild=root->lChild) ; //令parent的left或者right指向 root的left
     delete root ;
     return ;
    }
    
   }
   else  //最后一种  删除节点既有做孩子又有右孩子
   {
                   TreeNode  *p=root->lChild ;//定义一个p保存当前删除节点 我们利用这个节点左孩子找到最右下节点  。
                   while(p->rChild!=NULL)
       {
        parent=p ;  //保存右下节点的父节点指针
        p=p->rChild  ;//从待删除节点
       
       } 
       root->data=p->data ;
       parent->rChild=p->lChild ;
       delete p ;
      return ; 

   }
   
   
  }  
  
 
  
 }
 
}
int main(int argc,char*argv[])
{
 
    TreeNode *root=NULL;  //如果根节点指针在局部那么一定要初始化NULL否则程序崩溃 ,如果我们的指针是在全局定义的可以不初始化NULL全局变量放在静态存储区
 int a[]={32,36,15,53,18,45,72,48,16,93} ;
 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") ;
    BST_Delete(&root,36) ;
 InOrder(root) ;  


 return 1 ;
}