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

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

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

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

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


c++ loops traversal binary-search-tree preorder
person Miguel Reyes Martínez    schedule 12.04.2020    source источник
comment
обратите внимание на то, что правый потомок больше родителя, а левый меньше   -  person bobra    schedule 13.04.2020
comment
Оказывается, есть довольно простой способ сделать что-то подобное. Просто возьмите чистый лист бумаги и запишите простыми краткими предложениями на простом английском языке пошаговый процесс. Когда закончите, запланируйте экстренную встречу с резиновой уткой. Мы здесь не пишем целые программы для других людей и всегда отсылаем такие вопросы к вашей резиновой уточке. После того, как ваш резиновый утенок одобрит предложенный вами план действий, просто возьмите то, что вы записали, и переведите его непосредственно на C++. Миссия выполнена!   -  person Sam Varshavchik    schedule 13.04.2020
comment
Используйте std::stack<int> и перебирайте список, используя некоторую логику управления стеком. Нет необходимости в рекурсии.   -  person PaulMcKenzie    schedule 13.04.2020

Ответы (1)


arrow_upward
0
arrow_downward

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

#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
person Miguel Reyes Martínez    schedule 13.04.2020