#include<cmath>
#include<iostream>
#include "Trees.h"
#define all 100
//進行先序搜索，結果保存到place[]里，同時記下樹的高度*ph，便于按高度調整打印的間距 
//loc為節點要保存的地址，為place[loc]
//place[]中存的節點是以層遍歷從上到下的，這就可以用類似堆的模式存節點 
void search(struct Btnode* ptr, char* place, int ht, int loc, int* ph)
{
   place[loc]=ptr->data_;
   if(ht>*ph)//如果高度超過現有高度 
      *ph=ht;//更新高度 
   if(ptr->lc_!=0)//有左子 
      search(ptr->lc_, place, ht+1, loc*2, ph);//搜左子，并將左子保存在place[loc*2] 
   if(ptr->rc_!=0)//有右子 
      search(ptr->rc_, place, ht+1, loc*2+1, ph);//搜右子，并將左子保存在place[loc*2+1]
}
void printBTree(struct Btnode* ptr)
{ 
   char place[all];
   int height=1, n, i, floor, j; 
   for(i=1;i<=all;i++)//初始化為0 
      place[i]=0;
   search(ptr, place, 1, 1, &height);//遍歷樹，height保存樹的高度 
   n=(int)pow(2,height)-1;//最多有pow(2,height)-1個節點 
   floor=1;//當前所在層數 
   for(i=1;i<=n;i++)//打印節點 
   {
      if(place[i]==0)//節點不存在 
         for(j=1;j<=(int)pow(2,height+2-floor)-1;j++)//按高度打印空格 
            std::cout<<" ";
      else//節點存在
      {
         if(i*2<=n&&place[i*2]!=0)//有左子 
         {
            for(j=1;j<=(int)pow(2,height-floor)-1;j++)//按高度打印空格
               std::cout<<" ";
            std::cout<<".";//打印連接子節點的"枝干"
            for(j=1;j<=(int)pow(2,height-floor)-1;j++)//打印連接子節點的"枝干"
               std::cout<<"-";
         }
         else//沒有左子 
            for(j=1;j<=(int)pow(2,height-floor+1)-1;j++)//按高度打印空格 
               std::cout<<" ";
               
         std::cout<<place[i];
         
         if(i*2<=n&&place[i*2+1]!=0)//有右子 
         {
            for(j=1;j<=(int)pow(2,height-floor)-1;j++)//打印連接子節點的"枝干"
               std::cout<<"-";
            std::cout<<".";//打印連接子節點的"枝干"
            for(j=1;j<=(int)pow(2,height-floor)-1;j++)
               std::cout<<" ";
         }
         else//沒有右子 
            for(j=1;j<=(int)pow(2,height-floor+1)-1;j++)//按高度打印空格 
               std::cout<<" ";
      }
      std::cout<<" ";
      
      if(i==(int)pow(2,floor)-1)//打印完一層，換行 
      {
         std::cout<<std::endl;
         floor++;
      }
   }
   std::cout<<"\n";
}