/*
作者名稱： monkeylee
程序名稱： 添刪查改二叉樹
功能說明： 如果生成二叉樹每次都手工輸入整數，建立二叉樹，
   可以進行添加、遍歷、查找、刪除，如果插入的數和數中的數重復不予插入
創建時間： 2007.11.27
最后修改： 2007.12.1
修改原因： 
*/

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

//自引用結構
struct treeNode{
 int data;     //節點值
 struct treeNode *leftPtr; //指向左子樹的指針
 struct treeNode *rightPtr; //指向右子樹的指針
}; /*結構定義結束*/

typedef struct treeNode TreeNode;
typedef TreeNode * TreeNodePtr;

/*函數原型*/
void insertNode(TreeNodePtr &treePtr,int value);  //插入節點
void inOrder(TreeNodePtr treePtr);     //中序遍歷
int  instructions();         //菜單
void search(TreeNodePtr treePtr,int value);   //查找
void deleteNode(TreeNodePtr &treePtr,int value);  //刪除

//----------------------------------------------------------------------------------
/*主函數*/
void main(){
 int item;      //要操作的數據
 int choices;     //存儲隨機制的變量
 TreeNodePtr rootPtr=NULL;  //樹在開始的時候為空

 while(choices=instructions()){
  switch(choices){
  case 1:/*插入*/
   printf("輸入要插入的整數>>");
   scanf("%d",&item);
   insertNode(rootPtr,item);
   break;

  case 2:/*遍歷*/
   printf("中序遍歷：");
   inOrder(rootPtr);
   printf("\n");
   break;

  case 3:/*查詢*/
   printf("輸入要找的數>>");
   scanf("%d",&item);
   search(rootPtr,item);
   break;

  case 4:/*刪除*/
   printf("輸入要刪除的數字>>");
   scanf("%d",&item);
   deleteNode(rootPtr,item);
   break;

  default:/*輸入錯誤*/
   printf("請輸入正確的選項!\n");
  } /*結束switch*/
 }

 printf("\n");

} /*結束main函數*/
//----------------------------------------------------------------------------------
int instructions(){
 int choice;
 printf("菜單: 1.插入  2.遍歷  3.查找  4.刪除  0.退出\n>>");
 scanf("%d",&choice);
  return(choice);
} /*結束instructions*/
//----------------------------------------------------------------------------------
/*將節點插入到樹中*/
void insertNode(TreeNodePtr &treePtr,int value){

 //生成新節點，找到一個要連的地方，然后創建新節點newNodePtr
 TreeNodePtr newNodePtr;
 if(newNodePtr=(TreeNodePtr)malloc(sizeof(TreeNode))){
  newNodePtr->data=value;
  newNodePtr->leftPtr=NULL;
  newNodePtr->rightPtr=NULL;
 } /*結束if*/
 else{
  printf("沒有分配空間成功!\n");
  exit(0);
 } /*結束else*/
 

 /*如果樹為空，直接連接新節點*/
 if(treePtr==NULL){
  treePtr=newNodePtr;
 } /*結束if*/

 /*如果樹不為空*/
 else{

  /*要插入的數值小于當前節點終的數值*/
  if(newNodePtr->data<treePtr->data){
   insertNode(treePtr->leftPtr,newNodePtr->data);
  } /*結束if*/

  /*要插入的數值大于當前節點中的數值*/
  else if(newNodePtr->data>treePtr->data){
   insertNode(treePtr->rightPtr,newNodePtr->data);
  } /*結束else if*/


 } /*結束else*/
} /*結束insertNode()函數*/

//----------------------------------------------------------------------------------
/*對樹進行中序遍歷*/
void inOrder(TreeNodePtr treePtr){
 /*如果樹不為空*/
 if(treePtr!=NULL){
  inOrder(treePtr->leftPtr);
  printf("%5d",treePtr->data);
  inOrder(treePtr->rightPtr);
 } /*結束if*/

} /*結束inOrder()函數*/

//----------------------------------------------------------------------------------
/*查找，從頭節點開始*/
void search(TreeNodePtr treePtr,int value){
 TreeNodePtr currentPtr=treePtr;
 int n=1; //記錄查詢次數

 /*尋找*/
 while(currentPtr!=NULL && currentPtr->data!=value){
  printf("%d > ",currentPtr->data);
  if(value<currentPtr->data)
   currentPtr=currentPtr->leftPtr;
  else
   currentPtr=currentPtr->rightPtr;
  n++;
 } 

 if(currentPtr==NULL || currentPtr->data!=value){
  printf("沒有找到!\n");
  printf("尋找路徑=%d\n",n);
 }
 else if(currentPtr->data==value){
  printf("%d 找到!\n",value);
  printf("尋找路徑=%d\n",n);

 }
}

//----------------------------------------------------------------
/*將節點刪除*/
void deleteNode(TreeNodePtr &rootPtr,int value)
{
 TreeNodePtr prePtr=rootPtr;  //父節點
 TreeNodePtr currentPtr=rootPtr; //要刪除節點
 TreeNodePtr maxPtr=NULL;  //左子樹的最大值

 /*尋找要刪除節點，由currentPtr指向*/
 while(currentPtr!=NULL && currentPtr->data!=value)
 {
  prePtr=currentPtr;

  //比根節點的值小
  if(value<currentPtr->data)
   currentPtr=currentPtr->leftPtr;

  //比根節點的值大
  else
   currentPtr=currentPtr->rightPtr;
 }/*結束while*/

 //如果找到了,必須說明currentPtr！=NULL，假如NULL也不存在currentPtr->data
 if(currentPtr!=NULL && currentPtr->data==value)
 {

  //1.如果當前節點就是葉子節點
  if(currentPtr->leftPtr==NULL && currentPtr->rightPtr==NULL)
  {
   //如果整個樹只有一個節點
   if(currentPtr==rootPtr)
   {
    rootPtr=NULL;
    free(currentPtr);
   }

   else
   {
    //把父節點的所有子樹置空
    if(currentPtr==prePtr->leftPtr)
     prePtr->leftPtr=NULL;
    else
     prePtr->rightPtr=NULL;
    free(currentPtr);
   }/*結束else*/

  }/*結束if*/

  //2.如果只有一個右孩子
  else if(currentPtr->leftPtr==NULL && currentPtr->rightPtr!=NULL)
  {
   //如果刪除的正好是根節點
   if(currentPtr==rootPtr)
   {   
    rootPtr=currentPtr->rightPtr;
    free(currentPtr);
   }

   //如果要刪除的是左孩子
   else if(currentPtr==prePtr->leftPtr)
   {
    prePtr->leftPtr=currentPtr->rightPtr;
    free(currentPtr);
   }/*結束if*/

   //刪除的是右孩子
   else if(currentPtr==prePtr->rightPtr)
   {
    prePtr->rightPtr=currentPtr->rightPtr;
    free(currentPtr);
   }/*結束else*/

  }/*結束else if*/

  //3.如果只有一個左孩子
  else if(currentPtr->leftPtr!=NULL && currentPtr->rightPtr==NULL)
  {
   if(currentPtr==rootPtr)
   {
    rootPtr=currentPtr->leftPtr;
    free(currentPtr);
   }
   //如果刪除的是左孩子
   else if(currentPtr==prePtr->leftPtr)
   {
    prePtr->leftPtr=currentPtr->leftPtr;
    free(currentPtr);
   }
   //如果要刪除的是左孩子
   else if(currentPtr==prePtr->rightPtr)
   {
    prePtr->rightPtr=currentPtr->leftPtr;
    free(currentPtr);
   }/*借書if*/

  }/*結束else if*/

  //4.如果有兩孩子

  else if(currentPtr->leftPtr!=NULL && currentPtr->rightPtr!=NULL)
  {
   maxPtr=currentPtr->leftPtr;

   while(maxPtr->rightPtr!=NULL)
   {
    maxPtr=maxPtr->rightPtr;
   }
   //如果刪除的是根節點
   if(currentPtr==rootPtr)
   {
    rootPtr=currentPtr->leftPtr;
    maxPtr->rightPtr=currentPtr->rightPtr;
    free(currentPtr);
   }
   //如果刪除的是左子樹
   if(currentPtr==prePtr->leftPtr)
   {
    prePtr->leftPtr=currentPtr->leftPtr;
    maxPtr->rightPtr=currentPtr->rightPtr;
    free(currentPtr);
   }/*結束if*/

   else if(currentPtr==prePtr->rightPtr)
   {
    prePtr->rightPtr=currentPtr->leftPtr;
    maxPtr->rightPtr=currentPtr->rightPtr;
    free(currentPtr);

   }/*結束else*/

  }/*結束else*/

 }/*結束if*/
 
 else
 {
  printf("沒有找到!\n");
 }
 
}/*結束deleteNode函數*/