Построить без бинарного дерева из предзаказа обход

Question

Учитывая список узлов и число детей, у него есть, построить (не бинарное) дерево из этого списка (который в предварительном порядке обходе)

например, я дал следующее:

1 3 
2 1 
3 0 
4 0 
5 0 

который является дерево, которое выглядит как

  1 
      /|\ 
     /| \ 
     2 4 5 
    /
     3 

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

Answer 1

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

Study изображение и обратите внимание, как рекурсии только начинается, когда есть дети, для конкретного узла (и что они в последний раз для количество детей, указанных на входе).

Попробуйте придумать код (или псевдокод) на бумаге.

---

Код для решения этого довольно проста: использовать vector<Node> для хранения ваших детей

#include <iostream> 
#include <vector> 
using namespace std; 

struct Node { 
    Node(int v) : val(v) {} 
    int val; 
    vector<Node*> children; 
}; 

Node *readTreeNode() { 
    int val, children; 
    cin >> val >> children; 
    Node *node = new Node(val); 
    for (int i = 0; i<children; ++i) 
    node->children.push_back(readTreeNode()); 
    return node; 
} 

int main() { 
    Node *root = readTreeNode(); 
    // Do the cleanup.. 
    return 0; 
} 

Live Example

Обратите внимание на цикл, где функция readTreeNode() рекурсивно называется

for (int i = 0; i<children; ++i) 
    node->children.push_back(readTreeNode()); 

Внутренние дети обрабатываются перед остальными.

Итоговые предостережений:

1. Я не реализовать обработку памяти (код выше утечки памяти). Будьте хорошим гражданином и освободите выделенную память или, еще лучше, используйте интеллектуальные указатели.

2. Там нет обработки ошибок (то есть никакой проверки ввода не узлы эффективно быть введены)