/* ======================================== */
/*    程式實例: 12_6.cpp                    */
/*    二元樹類別實作                        */
/* ======================================== */
#include <iostream.h>

struct node                       /* 樹的結構宣告       */
{
   int data;                      /* 節點資料           */
   node *left;                    /* 指向左子樹的指標   */
   node *right;                   /* 指向右子樹的指標   */
};

class binaryTree                  /* 二元樹的類別宣告   */
{
private:
   node *head;                    /* 根節點的指標       */
   void inorder(node *ptr);       /* 成員函數:中序走訪  */
public:
   binaryTree() { head = NULL; }  /* 建構函數宣告       */
   void insertNode(int d);        /* 插入節點函數宣告   */
   void printTree();              /* 顯示二元樹的節點   */
   int search(int d);             /* 二元樹的走訪搜尋   */
};

/* ---------------------------------------- */
/*  成員函數: 二元樹中序走訪                */
/* ---------------------------------------- */
void binaryTree::inorder(node *ptr)
{
    if ( ptr != NULL )             /* 終止條件           */
    {
       inorder(ptr->left);         /* 左子樹             */
       /* 列印節點內容       */
       cout << "[" << ptr->data << "]"; 
       inorder(ptr->right);        /* 右子樹             */
    }
};

/* ---------------------------------------- */
/*  插入二元樹的節點                        */
/* ---------------------------------------- */
void binaryTree::insertNode(int d)
{
   /* 建立新節點記憶體 */
   node *temp = new node;           /* 建立新節點         */
   node *current;                   /* 目前樹節點指標     */
   int inserted = 0;                /* 是否插入新節點     */

   temp->data = d;                  /* 建立節點內容       */
   temp->left = NULL;               /* 設定指標初值       */
   temp->right = NULL;              /* 設定指標初值       */
   if ( head == NULL )              /* 是否是根節點       */
      head = temp;                  /* 根節點指標為新節點 */
   else
   {
      current = head;               /* 保留目前樹指標     */
      while( !inserted )
      {
         /* 比較節點值   */
	 if ( current->data > temp->data )
	 {
	    if ( current->left == NULL ) /* 是否是最左的子節點 */
	    {
	       current->left = temp; /* 接起父子的鏈結     */
	       inserted = 1;         /* 已經插入 */
	    }
	    else
	       current = current->left;    /* 左子樹      */
	 }
	 else
	 {
	    if ( current->right == NULL ) /* 是否是最右的子節點 */
	    {
	       current->right = temp; /* 接起父子的鏈結     */
	       inserted = 1;          /* 已經插入  */
	    }
	    else
	       current = current->right;   /* 右子樹      */
	 }
      }
   }
}

/* ---------------------------------------- */
/*  成員函數: 二元搜尋樹的搜尋              */
/* ---------------------------------------- */
int binaryTree::search(int d)
{
   node *temp = head;
   while ( temp != NULL )        /* 主回路             */
   { 
      if ( temp->data == d )     /* 找到了             */
	 return 1;
      if ( temp->data < d )      /* 比較資料           */
	 temp = temp->right;     /* 右子樹             */
      else
	 temp = temp->left;      /* 左子樹             */
   }
   return 0;                     /* 沒有找到           */
}   

/* ---------------------------------------- */
/*  成員函數: 中序走訪列印二元樹            */
/* ---------------------------------------- */
void binaryTree::printTree()
{
   inorder(head);                 /* 呼叫中序走訪函數  */ 
} 

/* ---------------------------------------- */
/*  主程式: 建立二元樹且用中序走訪列印出來. */
/* ---------------------------------------- */
void main()
{
   binaryTree btree;              /* 建立二元樹物件     */
   int i;

   /* 二元樹節點資料 */
   int data[9] = { 5, 6, 4, 8, 2, 3, 7, 1, 9 };
   for ( i = 0; i < 9; i++ )      /* 用回路建立樹狀結構 */
       btree.insertNode(data[i]); /* 插入二元樹的節點   */
   cout << "樹的節點內容 \n";
   btree.printTree();             /* 中序走訪二元樹     */
   cout << "\n請輸入搜索的數字: ";/* 輸出數字           */
   cin >> i;                      /* 輸入數字           */
   if ( btree.search(i) )         /* 搜尋輸入的數字     */
      cout << "找到節點! \n";
   else
      cout << "沒有找到節點! \n";
}