#include <iostream.h>
#include "Menu.h"
#include "key.h"

struct tree                       
{
   int data;                      // 節點數據
   struct tree *left;             // 左子樹
   struct tree *right;            // 右子樹
};

struct MT{
    int data[100]; //保存每層元素
    int n;        //每層元素的個數
};  //層序遍歷保存二叉樹的結點

struct MT mt[100]; //假定二叉樹最大層數 不超過100層


typedef struct tree treenode;     // 樹的結構型態
typedef treenode *btree;          // 樹節點指標型態

void _InputData(int *data);  //輸入二叉樹數據

btree insertnode(btree root,int value);   //插入二叉樹的節點
btree createbtree(int *data,int len); //建立二叉樹
void inorder(btree ptr);// 二叉樹中序遍歷
void preorder(btree ptr); //二叉樹前序遍歷
void postorder(btree ptr);//二叉樹后序遍歷
void CX(btree ptr,int n);   //二叉樹層序遍歷

void _preorder_main(int *data,int n);   //前序遍歷_測試程序
void _inorder_main(int *data,int n);    // 中序遍歷_測試程序
void _postorder_main(int *data,int n);  //后序遍歷列__測試程序
void _CenXu_order_main(int *data,int n);//層序遍歷__測試程序

void _ViewTree_main(int *data,int);  //瀏覽樹
int _Edit_data(int *data); //修改初始數據

int _f3_main(){  //程序入口
    Menu m[10];  //繪制菜單
    m[1].Name="輸入樹";
    m[2].Name="瀏覽樹";
    m[3].Name="前序遍歷  ";
    m[4].Name="中序遍歷  ";
    m[5].Name="后序遍歷";
    m[6].Name="層序遍歷";
    m[7].Name="返回";
    m[8].Name="    ";
    int DATA_Tree[1000] = { 5, 6, 4, 8, 2, 3, 7, 1, 9 };
    int n=9;    
    int *data=DATA_Tree;
    int ID=1;
    while(1)
    {    
        ShowMenu("數據結構--二叉樹遍歷",m,8);  //顯示菜單
        ID=SelectMenuID(); //獲取選中的菜單ID
        switch(ID){
        case 1:{n=_Edit_data(data);InitKey();}break;
        case 2:{_ViewTree_main(data,n);InitKey();}break;
        case 3:{_preorder_main(data,n);InitKey();}break;
        case 4:{_inorder_main(data,n);InitKey();}break;
        case 5:{_postorder_main(data,n);InitKey();}break;
        case 6:{_CenXu_order_main(data,n);InitKey();}break;
        case 7:return 0;
        case 8:break;
        }
    }
    return 0;
}

int _Edit_data(int *data){ //修改初始數據
    int n;
    cout<<"\n請輸入結點總數n=";
    cin>>n;
    cout<<"輸入每個結點的數據"<<endl;
    cout<<"例如依次輸入：5, 6, 4, 8, 2, 3, 7, 1, 9\n"<<endl;
    for(int i=0;i<n;i++){  //輸入數據
        cout<<"["<<i<<"]=";
        cin>>data[i];
        cout<<"\n";
        }
    cout<<"\n您輸入的數據為：";
    for(int j=0;j<n;j++)cout<<data[j]<<" ";
    return n;
}

btree insertnode(btree root,int value){   //插入二叉樹的節點

   btree newnode;                 //樹根
   btree current;                 //目前樹節點指標
   btree back;                    //父節點指標
   newnode=new treenode;         //建立新節點
   newnode->data = value;         //建立節點內容 
   newnode->left = NULL;          //設定指標初值
   newnode->right = NULL;         //設定指標初值
   if(root==NULL) return newnode; //是根節點傳回新節點位置
   else
   {
      current = root;             //保留目前樹指標
      while ( current != NULL )
      {
         back = current;          //保留父節點指標
         if ( current->data > value )    //比較節點值
            current = current->left;     //左子樹
         else
            current = current->right;    //右子樹
      }
      if (back->data>value )back->left = newnode;    // 左子樹
      else back->right = newnode;   // 右子樹 
   }
   return root;  // 返回樹根
}


btree createbtree(int *data,int len){ //建立二叉樹
   btree root = NULL;             // 樹根指標
   int i;

   for ( i = 0; i < len; i++ )    // 用回路建立樹狀結構
      root = insertnode(root,data[i]);
   return root;
}
void preorder(btree ptr){ //二叉樹前序遍歷
   if ( ptr != NULL )             
   {
      cout<<ptr->data<<" ";
      preorder(ptr->left);        
      preorder(ptr->right);       
   }
}


void inorder(btree ptr){// 二叉樹中序遍歷
   if ( ptr != NULL )             // 終止條件
   {
      inorder(ptr->left);         // 左子樹
      cout<<ptr->data<<" ";
      inorder(ptr->right);        // 右子樹 
   }
}


void postorder(btree ptr){//二叉樹后序遍歷
   if ( ptr != NULL )             
   {
      postorder(ptr->left);       
      postorder(ptr->right);      
      cout<<ptr->data<<" ";
   }
}

void _preorder_main(int *data,int n){  //先序遍歷_測試程序
   btree root = NULL;             
   root = createbtree(data,n);    //建立二叉樹
   cout<<"樹的節點內容 n=";
   preorder(root);                //先序遍歷二叉樹
}

void _inorder_main(int *data,int n){ // 中序遍歷_測試程序
   btree root = NULL;             
   root = createbtree(data,n);    //建立二叉樹
   cout<<"樹的節點內容 n=";
   inorder(root);                 //中序遍歷二叉樹
}

void _postorder_main(int *data,int n){ //后序遍歷列__測試程序
   btree root = NULL;            
   root = createbtree(data,n);    //建立二叉樹
   cout<<"樹的節點內容 n=";
   postorder(root);               //后序遍歷二叉樹
}
//~

//////////////////////////////////////////////

int max_n=0;//保存最大層數
void CX(btree ptr,int n)   //層序遍歷
{
  if ( ptr != NULL )             
   {
      n++;  //層計數
      
      if(max_n<n)max_n=n;//保存最大層數

      mt[n].data[mt[n].n]=ptr->data;  //保存當前層的數據
      mt[n].n=mt[n].n+1;  //把該層的 元素個數+1
      CX(ptr->left,n);   //繼續瀏覽 左結點
      CX(ptr->right,n);  //繼續瀏覽 右結點
   }
}

void _CenXu_order_main(int *data,int n){//層序遍歷

   btree root = NULL;             
   
   root = createbtree(data,n);    //建立二叉樹

   cout<<"樹的節點內容";

   for(int m=0;m<100;m++)mt[m].n=0;
   
   
   CX(root,0);


   cout<<"該二叉樹的各層數據如下："<<endl;
   for(int mm=0;mm<=max_n;mm++)
   {
       for(int mn=0;mn<mt[mm].n;mn++)
       {
       cout<<mt[mm].data[mn]<<" ";
       }
       cout<<"\n";
   }
}

void ViewTree(btree ptr){  //瀏覽樹
     if ( ptr != NULL )             // 終止條件
   {
        cout<<ptr->data;
        if(ptr->left!=NULL || ptr->right!=NULL)
        {
            cout<<"(";
            ViewTree(ptr->left);
            if(ptr->right!=NULL)cout<<",";
            ViewTree(ptr->right);
            cout<<")";
        }
     }
}

void _ViewTree_main(int *data,int n)  //瀏覽樹
{

   btree root = NULL;             
   
   root = createbtree(data,n);    //建立二叉樹

   cout<<"樹的節點內容 n=";

   ViewTree(root);

}