九度題目1009：二叉搜尋樹

題目1009：二叉搜尋樹

時間限制：1 秒

記憶體限制：32 兆

特殊判題：否

送出：4308

解決：1919

題目描述：

判斷兩序列是否為同一二叉搜尋樹序列

輸入：

開始一個數n，(1<=n<=20) 表示有n個需要判斷，n= 0 的時候輸入結束。

接下去一行是一個序列，序列長度小于10，包含(0~9)的數字，沒有重複數字，根據這個序列可以構造出一顆二叉搜尋樹。

接下去的n行有n個序列，每個序列格式跟第一個序列一樣，請判斷這兩個序列是否能組成同一顆二叉搜尋樹。

輸出：

如果序列相同則輸出YES，否則輸出NO

樣例輸入：

2

567432

543267

576342

樣例輸出：

YES

NO

來源：

2010年浙江大學計算機及軟體工程研究所學生機試真題

靜态二叉搜尋樹的非遞歸實作

思路：

由于僅僅隻需要周遊二叉樹即可，是以沒有必要花費時間建立指針樹，

隻需要在相應位置儲存資料周遊即可。

開一個一維數組，從a[1]開始存儲，a[1]的左孩子是a[2]，右孩子是a[3]，

同理，a[2]的左孩子是a[4]，右孩子是a[5]，a[3]的左孩子是a[6]，右孩子是a[7]

如圖：

                    a[1]

            a[2]          a[3]

     a[4]   a[5]   a[6]    a[7]

可以得出結論，a[i]的左孩子是a[2*i]，右孩子是a[2*i+1]。

首先将空的數組清為-1（輸入值都是大于0的），然後對插入的

值判斷，如果目前節點為-1，說明有空間，将數放在此位置即可。

如果目前節點不為-1，說明位置已被占，按照二叉排序樹的定義，

我們根據它與此節點的大小來判斷它往左還是右插

AC代碼：

#include<stdio.h>
#include<string.h>
char s[100];
int a[100],b[100];
void CreatTree(char s[],int a[])
{
   int j,n=strlen(s);
   int i=0;
   while(i<n)
   {
      for(j=0;j<100;)
      {
          if(a[j]==-1)
          {
             a[j]=s[i]-'0';
             break;  
          }
          else
          {
             if(a[j]>s[i]-'0')
             j=2*j;
             else
             j=2*j+1;
          }
      } 
      i++;      
   }
}
int main()
{
    int i,j,n,m;
    while(scanf("%d",&n),n!=0)
    {
       memset(s,0,sizeof(s));
       scanf("%s",s);
       for(i=1;i<100;i++)
       a[i]=-1;
       CreatTree(s,a);
       while(n--)
       {
          memset(s,0,sizeof(s));
          scanf("%s",s);
          for(i=1;i<100;i++)
          b[i]=-1;
          CreatTree(s,b);
          for(i=0;i<100;i++)
          if(a[i]!=b[i]) break;
          if(i==100)
          printf("YES\n");
          else
          printf("NO\n");
       }
    }
    return 0;
}