PreOrderからバイナリ検索ツリーを構築する

Question

preorderTransaversalからバイナリ検索ツリーを構築する方法。提案があればお勧めします。

Node constructTreeFromPreorder(int[] arr,int start,int end) 
{ 
if(arr==null){ 
    return null; 
}else{ 
    if(start>end){ 
     return null; 
    } 
    int element=arr[start]; 
    Node node=new Node(element); // create node 
    if(start==end){ 
     return node; 
    } 
    int index=start+1; 
    for(int i=index;i<=end;i++){ 
      index=i; 
     if(arr[i]>element){ 
      break; 
     } 
    } 
    node.left=constructTreeFromPreorder(arr, start+1, index-1); 
    node.right=constructTreeFromPreorder(arr, index, end); 
    return node; 
} 

Answer 1

プリオーダートラバーサルに対応する複数のバイナリツリーがあります。たとえば、予約注文トラバーサル[2,1,3]を考えてみましょう。つまり、これらの樹木のすべてのための先行順走査である：

2   2  2   2  2 
1 3  1   1  1   1 
     3   3   3   3 

あなたが一意にバイナリツリーを記述したい場合は、ちょうど先行順走査よりも多くの情報を必要としています。

質問を変更した後に追加されました。これらのうち、最初のものが有効なバイナリ検索ツリーです。あるプリオーダートラバーサルに対して複数のBSTがあるかどうかはわかりません。

リストに重複した項目がある場合は、任意の指定された受注トラバーサルに対して複数のツリーが存在する可能性があります。