algorithm - 存在しない子が指定された事前注文トラバーサルからの二分木

Question

次のように、事前注文トラバーサルで表されるバイナリ ツリーがあります{1 4 6 10 0 0 0 7 0 8 0 0 2 5 0 0 3 9 0 0 0 }。 0 は、要素の子がないことを示します。

このデータから元のバイナリ ツリーを構築するにはどうすればよいですか? 再帰の問題を解決しようとしましたが、親として葉を持たない限り配列内の位置を計算できないため、ノードの正しい子を処理する方法を理解していません (葉がその後ろに 2 つのゼロがあり、子がないことを示します)。

解決策はかなり簡単でなければならないと思いますが、まだわかりません。

Answer 1

このような単純なものがうまくいくかもしれません。入力シーケンスの事前注文解釈でツリーを再構築する必要があるだけです。次のコードは、入力シーケンスを検証して、それが有効なツリー表現であることを確認しません。

struct BTNode {
    int data;
    BTNode* left;
    BTNode* right;
}

BTNode* BuildTree(int* sequence, int& pos) {
    int value = sequence[pos++];
    if (value == 0)
        return nullptr;
    BTNode* node = new BTNode;
    node->data = value;
    node->left = BuildTree(sequence, pos);
    node->right = BuildTree(sequence, pos);
    return node;
}