商競104F-P41二搜+後巡(CPP版參考)

這是依商業技藝競賽程式104年正式題第4題子題1稍微修改
資料檔第1列 一個數字 n ，代表 n 組資料，接著每組資料二列
每組的第1列一個數字x，每組第2列 x 個數字以逗號隔開
將讀入的 x 數字建成二元搜尋樹，然後依二元樹的後序拜訪 印出
參考程式碼：
/*
104f-p41_bst-pos 將 n 個數字建二元搜尋樹，再以後序巡訪序印出
第一列 整數 t:代表有 t組資料{ 0<t<10 }， 接著每組2列
每組第1列為 整數 n:代表有 n 個數字 { 3<= n <= 20 } ， 每組第2列有 n 個以逗號隔開的整數 vi {  0 <= vi <=99 for i=1~n }
*/

#include <iostream>
using namespace std;
const int MaxN = 21; //本題最多20個節點
struct nds  // 每一點有 值dt , 左子、右子 chi[0],chi[1]
{
int dt;
int chi[2]; // -1代表 沒有子樹 chi[0]左子，chi[1]右子
} nds[MaxN]; //本題最多20個節點
// 函式 gbst 建二元搜尋樹 
void gbst( int i, int v )
{
int p = 0 , dir; // dir:0左、1右
while( p != -1 )  //找到  null 節點 ，再 break
{
int pp = p;
if( v < nds[p].dt )    //往左樹
{
dir = 0;
p=nds[p].chi[0];
}
else {  // v > nds[p].v  往右樹
dir = 1;
p=nds[p].chi[1];
}
if ( p == -1 ) //左或右為null ，找到，加入
{
nds[pp].chi[dir] = i;
return;
}
}
}

// post_order 後序拜訪：先印左樹、再印右樹、最後 才印節點本身
void po_st( int p )
{
   if( p == -1 ) return;
   po_st( nds[p].chi[0] );
   po_st( nds[p].chi[1] );
   cout << nds[p].dt << ',';
}

int main(void)
{
   int i, v,n,x;
   char c;
   cin >> n;
   while( n-- )
   {
cin >> x;
for(i=0;i<x;++i) nds[i].chi[0] = nds[i].chi[1] = -1;
cin >> v; nds[0].dt = v;
for(i=1; i<x; ++i)
{
cin >> c >> v;    // 數字間有一 逗號 先讀c 再讀 v
nds[i].dt = v;
gbst( i , v );  // 呼叫函式建左右樹的連結表
}
//for(i=0; i<n; ++i)   // 測試列印 建好表後的 左樹、值、右樹
//   cout << nds[i].chi[0] <<':' << 先nds[i].dt <<':' << nds[i].chi[1] << endl;
    po_st( nds[0].chi[0] );  //先印 左樹
    po_st( nds[0].chi[1] );  //再印 右樹
    cout << nds[0].dt << endl; //最後才印根節點
   }
   return 0;
}
/*範例輸入
4
8
7,4,1,5,12,8,9,15
10
9,4,1,5,12,11,10,15,2,3
9
4,1,5,12,11,10,15,2,3
4
1,2,3,4
範例輸出 ------
1,5,4,9,8,15,12,7
3,2,1,5,4,10,11,15,12,9
3,2,1,10,11,15,12,5,4
4,3,2,1
*/