/* ======================================== */
/*    程式實例: 7_3_2.c                     */
/*    二叉樹的結構數組表示法                */
/* ======================================== */
#include <stdlib.h>

struct tree                         /* 樹的結構宣告       */
{
   int data;                        /* 節點數據           */
   int left;                        /* 指向左子樹的位置   */
   int right;                       /* 指向右子樹的位置   */
};
typedef struct tree treenode;       /* 樹的結構新型態     */
treenode btree[15];                 /* 宣告樹的結構數組   */

/* ---------------------------------------- */
/*  建立二叉樹                              */
/* ---------------------------------------- */
void createbtree(int *data,int len)
{
   int level;                       /* 樹的階層           */
   int pos;                         /* -1是左樹,1是右樹   */
   int i;

   btree[0].data = data[0];         /* 建立樹根節點       */
   for ( i = 1; i < len; i++ )      /* 用回路建立其它節點 */
   {
      btree[i].data = data[i];      /* 建立節點內容       */
      level = 0;                    /* 從樹根開始         */
      pos = 0;                      /* 設定pos值          */
      while ( pos == 0 )            /* 用回路找節點位置   */
      {
         /* 比較是左或右子樹 */
         if ( data[i] > btree[level].data )
            /* 右樹是否有下一階層 */
            if ( btree[level].right != -1 )
               level = btree[level].right;
            else
               pos = -1;            /* 是右樹             */
         else
            /* 左樹是否有下一階層 */
            if ( btree[level].left != -1 )
               level = btree[level].left;
            else
               pos = 1;             /* 是左樹             */
      }
      if ( pos == 1 )               /* 建立節點左右位置   */
         btree[level].left = i;     /* 鏈結左子樹         */
      else
         btree[level].right = i;    /* 鏈結右子樹         */
   }
}

/* ---------------------------------------- */
/*  主程式: 建立結構數組的二叉樹狀結構.     */
/*  數字-1表示沒有下一階層.                 */
/* ---------------------------------------- */
void main()
{
   /* 二叉樹節點數據 */
   int data[10] = { 5, 6, 4, 8, 2, 3, 7, 1, 9 };
   int i;

   for ( i = 0; i < 15; i++ )       /* 清除樹狀結構數組   */
   {
      btree[i].data = 0;            /* 設定初始內容       */
      btree[i].left = -1;           /* 設定初始內容       */
      btree[i].right = -1;          /* 設定初始內容       */
   }
   createbtree(data,9);            /* 建立二叉樹         */
   printf("    左  數據  右\n");
   printf("----------------- \n");
   for ( i = 0; i < 15; i++ )       /* 列出二叉樹內容     */
      if ( btree[i].data != 0 )     /* 是否是樹的節點     */
         printf("%2d:[%2d] [%2d] [%2d]\n",i,btree[i].left,
                 btree[i].data,btree[i].right);
}