Как перечислить дочерние элементы каждого узла в бинарном дереве поиска из обхода предзаказа?

Question

С учетом обхода предзаказа в виде вектора int (например, {7,4,3,6,5,8,10}), как я могу итеративно перечислить дочерние элементы каждого узла?

Example output
7 - 4 8
4 - 3 6
6 - 5
8 - 10

Я сделал это, генерируя дерево, а затем рекурсивно перечисляя каждого потомка, но мне нужно сделать это только с использованием заданного вектора. Любая идея?

Я не прошу код, просто несколько классных идей

Answer 1

После нескольких попыток я сделал это. Для каждой итерации вы должны находить все больший и меньший элемент, распечатывать их и устанавливать их как используемые, чтобы избежать печати значений из других ветвей.

#include<stdio.h>
#include<iostream>

using namespace std;

int main(){
    int preOrder[] = {7,4,3,6,5,8,10};
    int size = sizeof(preOrder)/sizeof(int);
    bool used[size] = {false};
    for(int i = 0; i < size; ++i){
        bool lesserFound = false;
        bool greaterFound = false;
        for(int j = i+1; j < size; ++j){
            if(used[j]==true)
                lesserFound=greaterFound=true;

            if(preOrder[j]<preOrder[i] && lesserFound==false){
                cout << preOrder[i] << " - LeftChild: " << preOrder[j] << endl;
                lesserFound=true;
                used[j]=true;
            }else if(preOrder[j]>preOrder[i] && greaterFound==false){
                cout << preOrder[i] << " - RightChild: " << preOrder[j] << endl;
                greaterFound=true;
                used[j]=true;
            }
        }
    }
}

Вывод:

7 - LeftChild: 4
7 - RightChild: 8
4 - LeftChild: 3
4 - RightChild: 6
6 - LeftChild: 5
8 - RightChild: 10