配列ベースのバイナリツリープリオーダ

Question

どのようにして、配列ベースのツリーを1つの順序に変換できますか？配列は含まれています

乾杯

public void preOrder(int index) { 

    if (index >= currSize) { 
     return; 
    } 

    System.out.println(items[index]); 
    preOrder(2^index + 1); //left 
    preOrder((2^index) + 2); //right 
} 

Answer 1

以下のようになります。

public void preOrder(int index) { 

    if (index >= currSize) { 
     return; 
    } 
    System.out.println(items[index]); 
    preOrder((2 * index)+1); 
    preOrder((2 * index)+2); 
} 

Answer 2

プリオーダートラバーサルでは、あなたは、あなたが再帰的に左部分木と右のサブツリーを処理する、最初の親を処理します。あなたが持っている表現は基本的にヒープの表現と同じです。したがって、どのノードの左と右の子が何であるかは明らかです。つまり、これを事前注文でトラバースし、ノードを訪問順にプリントアウトすることができます。

擬似コードは以下のようになり：

print_pre_order(index): 
    if index is beyond the size of the array: 
    return 
    else: 
    print value at index 
    print_pre_order(left child of index) 
    print_pre_order(right child of index) 

これは、各インデックスに対して、ヒープとして配置され、N左の子が2 * であり、nおよび右の子がn 2 *（になっているので+1）。配列のインデックスは1から始まると仮定していますが（ほとんどの言語は0から始まりますが）、0ベースの配列には簡単に適応できます。