/* ======================================== */
/*    程式實例: 7_3_1.c                     */
/*    二叉樹的數組表示法                    */
/* ======================================== */

/* ---------------------------------------- */
/*  建立二叉樹                              */
/* ---------------------------------------- */
void createbtree(int *btree,int *data,int len)
{
   int level;                       /* 樹的階層           */
   int i;

   btree[1] = data[1];              /* 建立根節點         */
   for ( i = 2; i <= len; i++ )     /* 用回路建立其它節點 */
   {
      level = 1;                    /* 從階層1開始        */
      while ( btree[level] != 0 )   /* 是否有子樹         */
      {
         if ( data[i] > btree[level] )   /* 是左或右子樹  */
            level = level * 2 + 1;  /* 右子樹             */
         else
            level = level * 2;      /* 左子樹             */
      }
      btree[level] = data[i];       /* 存入節點數據       */
   }
}

/* ---------------------------------------- */
/*  主程式: 建立數組的二叉樹.               */
/* ---------------------------------------- */
void main()
{
   int btree[16];                   /* 二叉樹數組         */
   /* 二叉樹節點數據 */
   int data[10] = { 0, 5, 6, 4, 8, 2, 3, 7, 1, 9 };
   int i;

   for ( i = 1; i < 16; i++ )       /* 清除二叉樹數組     */
      btree[i] = 0;
   createbtree(btree,data,9);      /* 建立二叉樹         */
   for ( i = 1; i < 16; i++ )       /* 列出二叉樹內容     */
      printf("%2d: [%d] \n",i,btree[i]);
}