/* ======================================== */
/*    程式實例: 7_4_3.c                     */
/*    二叉樹的后序遍歷                      */
/* ======================================== */
#include <stdlib.h>

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

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

   btree newnode;                 /* 樹根指標           */
   btree current;                 /* 目前樹節點指標     */
   btree back;                    /* 父節點指標         */

   /* 建立新節點記憶體 */
   newnode = ( btree ) malloc(sizeof(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 postorder(btree ptr)
{
   if ( ptr != NULL )             /* 終止條件           */
   {
      postorder(ptr->left);       /* 左子樹             */
      postorder(ptr->right);      /* 右子樹             */
      printf("[%2d]\n",ptr->data);  /* 列印節點內容     */
   }
}

/* ---------------------------------------- */
/*  主程式: 建立二叉樹且用后序遍歷列印出來. */
/* ---------------------------------------- */
void main()
{
   btree root = NULL;             /* 樹根指標           */

   /* 二叉樹節點數據 */
   int data[9] = { 5, 6, 4, 8, 2, 3, 7, 1, 9 };
   root = createbtree(data,9);    /* 建立二叉樹         */
   printf("樹的節點內容 \n");
   postorder(root);               /* 后序遍歷二叉樹     */
}