576      技術社區[雲棲]

九度題目1009：二叉搜索樹

題目1009：二叉搜索樹
時間限製：1 秒
內存限製：32 兆
特殊判題：否
提交：4308
解決：1919
題目描述：
判斷兩序列是否為同一二叉搜索樹序列
輸入：
開始一個數n，(1<=n<=20) 表示有n個需要判斷，n= 0 的時候輸入結束。
接下去一行是一個序列，序列長度小於10，包含(0~9)的數字，沒有重複數字，根據這個序列可以構造出一顆二叉搜索樹。
接下去的n行有n個序列，每個序列格式跟第一個序列一樣，請判斷這兩個序列是否能組成同一顆二叉搜索樹。
輸出：
如果序列相同則輸出YES，否則輸出NO

樣例輸入：
2
567432
543267
576342
0
樣例輸出：
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;
}

最後更新：2017-04-03 05:39:38

  上一篇： 匯編的 DEBUG 命令

  下一篇： Atom介紹和安裝步驟