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

Question

У меня есть предварительный обход бинарного дерева, которое хранится в массиве, и я хотел бы воссоздать двоичное дерево на основе этого обхода. Мой массив выглядит следующим образом: {NNNLLNLLNLNLNNLLNLL}, где N представляет узел, а L - лист. Я бы хотел сделать это рекурсивно, но у меня возникли проблемы с алгоритмом. Любые предложения будут очень оценены.

Answer 1

Перед восстановлением дерева вам потребуется еще один обход. При любых двух проходах между тремя (Pre, Post, In) вы можете восстановить. Но, учитывая только одно, невозможно однозначно восстановить дерево.

Answer 2

Это должно работать при условии, каждый узел имеет 2 или 0 потомков (дерево, которое удовлетворяет это свойство называется полный или строгое бинарное дерево)

void create_from_traversal(Node* root, int& index) { 
    if (traversal[index] == 'L') { 
     root->left = root->right = NULL; 
     return; 
    } 
    root->left = new Node(); 
    create_from_traversal(root->left, ++index); 
    root->right = new Node(); 
    create_from_traversal(root->right, ++index); 
} 

Полный пример с проверкой:

#include <string> 
#include <iostream> 

class Node { 
public: 
    Node* left; 
    Node* right; 
}; 

std::string traversal = "NNNLLNLLNLNLNNLLNLL"; 

void create_from_traversal(Node* root, int& index) { 
    if (traversal[index] == 'L') { 
     root->left = root->right = NULL; 
     return; 
    } 
    root->left = new Node(); 
    create_from_traversal(root->left, ++index); 
    root->right = new Node(); 
    create_from_traversal(root->right, ++index); 
} 

void print_traversal(Node* root) { 
    if (root->left == NULL) { 
     std::cout << "L"; 
     return; 
    } 
    std::cout << "N"; 
    print_traversal(root->left); 
    print_traversal(root->right); 
} 

int main() { 
    Node* root = new Node(); 
    int index = 0; 
    create_from_traversal(root, index); 

    // Does it work? 
    print_traversal(root); // Output should be equal to given traversal 
    std::cout << std::endl; 
} 

Выход:

NNNLLNLLNLNLNNLLNLL