/*
程序作者： monkeylee
程序名稱： 二叉樹平衡因子
程序功能： 隨機生成用戶要求個數的整數，生成二叉樹（無重復），
   可以進行生成、遍歷、查找二叉樹，而且進行動態的查找，
   如果沒有找到節點就把這個值接到樹上
   能夠顯示節點的產生順序、平衡因子（失敗），節點值
創建時間： 2007.12.01
最后更新： 2007.12.03
*/

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

//自引用結構
struct treeNode
{
 int data;     //節點值
 int balance;    //平衡因子
 int order;     //生成順序
 struct treeNode *left;  //指向左子樹的指針
 struct treeNode *right;  //指向右子樹的指針
 struct treeNode *father;
}; /*結構定義END */

typedef struct treeNode TreeNode;
typedef TreeNode * TreeNodePtr;

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

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

 while(choices=instructions())
 {
  switch(choices)
  {
  case 1:
   rootPtr=NULL;
   printf("輸入要生成二叉樹的節點數>>");
   scanf("%d",&n);
   if(n<=0)
   {
    printf("輸入節點數必須大于等于1\n");
    break;
   }
   srand(time(NULL));
   for(i=1;i<=n;i++)
   {
    item=rand()%(10*n);
    insertNode(rootPtr,item,i);
   }/*END for*/
   break;


  case 2:
   printf("中序遍歷:\n");
   if(rootPtr==NULL)
    break;
   inOrder(rootPtr);
   printf("\n");
   break;
  case 3:
   printf("輸入要找的數>>");
   scanf("%d",&item);
   search(rootPtr,item,i);
   i++;
   break;

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

 printf("\n");

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

 //生成新節點，找到一個要連的地方
 TreeNodePtr currentPtr=rootPtr;
 TreeNodePtr newPtr;
 TreeNodePtr prePtr=rootPtr;
 if(newPtr=(TreeNodePtr)malloc(sizeof(TreeNode)))
 {
  newPtr->data=value;
  newPtr->balance=0;
  newPtr->order=order;
  newPtr->left=NULL;
  newPtr->right=NULL;
  newPtr->father=NULL;
 }/*END if*/

 else
 {
  printf("沒有分配空間成功!\n");
  exit(0);
 }/*END else*/
 

 /*如果樹為空*/
 if(rootPtr==NULL)
 {
  rootPtr=newPtr;
 }/*END if*/

 /*如果樹不為空*/
 else
 {
  //找到了要插入的位置由currentPtr來指向
  while(currentPtr!=NULL && prePtr->data!=value)
  {
   prePtr=currentPtr;
   if(value<currentPtr->data)
   {
    currentPtr=currentPtr->left;
   }
   else 
   {
    currentPtr=currentPtr->right;
   }
  }
  //-----------------------------------------------------------------左節點
  //如果最后插入到前一個節點的左節點
  if(value<prePtr->data)
  {
   //把新節點連上
   prePtr->left=newPtr;
   newPtr->father=prePtr;

   //如果插入節點有個兄弟節點，則只需改變新節點的父節點的平衡因子，其它不用管
   if(prePtr->right!=NULL)
   {
     prePtr->balance++;
   }

   /*如果插入節點沒有兄弟節點，修改新節點父節點的平衡因子，再往上面追溯
   這里分兩種情況，所追溯的節點沒有兄弟節點則肯定修改平衡因子，但是如果
   所追溯的節點有個兄弟節點，又要分兩種情況討論，如果所追溯的是它父節點的
   左孩子，那么如果它的父節點的平衡因子改變之后仍然小于等于0，則追溯停止
   如果大于0則還要繼續往上追溯，直到找到一個節點又兩個孩子，如果從左節點上去的
   則如果平衡因子大于0繼續否則停止，如果是從右節點上去的，如果其父節點平衡因子大于等于
   0則停止否則繼續追溯*/

   //插入節點沒有兄弟節點
   else
   {
    currentPtr=newPtr->father; //初始化currentPtr指向新插入節點的父節點
    prePtr=newPtr;    //初始化prePtr指向新節點

    //一直向上追溯，一直到父節點才停
    while(currentPtr->father!=NULL)
    {

     //如果currentPtr所指向的節點有兩個孩子，則有可能停了下來
     if(currentPtr->left!=NULL && currentPtr->right !=NULL)
     {
      //如果從左路上去
      if(currentPtr->left==prePtr)
      {
       currentPtr->balance++;
       if(currentPtr->balance<=0)
        break;
      }

      //如果從右路上去
      else
      {
       currentPtr->balance--;
       if(currentPtr->balance>=0)
        break;
       
      }
      currentPtr=currentPtr->father; //向上移動
      prePtr=prePtr->father;   //向上移動
     }
     //如果所指向的節點currentPtr所指向的節點只有一個孩子則改變了平衡因子繼續
     else
     {
      if(currentPtr->left==prePtr)
       currentPtr->balance++;
      else
       currentPtr->balance--;
      
      currentPtr=currentPtr->father; //向上移動
      prePtr=prePtr->father;   //向上移動
     }

    }/*END  while*/


    //處理currentPtr指到了根節點的情況
    if(currentPtr->father==NULL)
    {
     if(currentPtr->left==prePtr)
      currentPtr->balance++;
     else 
      currentPtr->balance--;
    }

   }/*END  else*/

  }/*END  else*/

 //-----------------------------------------------------------------右節點
  //如果插入的節點在前一個節點的右節點上
  else if(value>prePtr->data)
  {
   //連接新節點
   prePtr->right=newPtr;
   newPtr->father=prePtr;

   //如果在一個非葉子節點上插入，則只改變父節點的平衡因子
   if(prePtr->left!=NULL )
   {
     prePtr->balance--;
   }

   //如果在一個葉子節點上插入，
   else
   {
    currentPtr=newPtr->father; //初始化currentPtr
    prePtr=newPtr;    //初始化prePtr

    while(currentPtr->father!=NULL)
    {
     //如果currentPtr有兩個節點
     if(currentPtr->left!=NULL && currentPtr->right !=NULL)
     {
      if(currentPtr->left==prePtr)
      {
       currentPtr->balance++;
       if(currentPtr->balance<=0)
        break;
      }
      else
      {
       currentPtr->balance--;
       if(currentPtr->balance>=0)
        break;
       
      }
      prePtr=currentPtr;
      currentPtr=currentPtr->father;
     }
     //currentPtr節點只有一個節點
     else
     {
      if(currentPtr->left==prePtr)
       currentPtr->balance++;
      else
       currentPtr->balance--;
      prePtr=currentPtr;
      currentPtr=currentPtr->father;
     }

    }/*END  while*/
    if(currentPtr->father==NULL)
    {
     if(currentPtr->left==prePtr)
      currentPtr->balance++;
     else 
      currentPtr->balance--;
    }

   }/*END else*/

  }/*END else if*/

 }/*END else*/
}/*END insertNode()函數*/


//----------------------------------------------------------------------------------

/*對樹進行中序遍歷*/
void inOrder(TreeNodePtr rootPtr){
 /*如果樹不為空*/
 if(rootPtr!=NULL){
  inOrder(rootPtr->left);
  printf("[生成順序=%-3d] [節點值=%-5d] [平衡因子=%-3d]\n",rootPtr->order,rootPtr->data,rootPtr->balance);
  inOrder(rootPtr->right);
 }/*END if*/

}/*END inOrder()函數*/

//----------------------------------------------------------------------------------
/*查找從頭節點一直到查找值過程*/
void search(TreeNodePtr &rootPtr,int value,int i){
 TreeNodePtr prePtr=rootPtr;
 TreeNodePtr currentPtr=rootPtr;
 TreeNodePtr newPtr;
 int n=1;
 while(currentPtr!=NULL && currentPtr->data!=value){
  printf("%d > ",currentPtr->data);
  prePtr=currentPtr;
  if(value<currentPtr->data)
   currentPtr=currentPtr->left;
  else
   currentPtr=currentPtr->right;
  n++;
 }/*尋找*/

 //如果沒有找到節點
 if(currentPtr==NULL){
  printf("沒有找到,將這個值插入...\n");
  insertNode(rootPtr,value,i);
 }
}