Преобразование списка узлов в предзаказе обратно в двоичное дерево

Question

У меня есть список узлов в предзаказе, который мне нужно превратить в дерево.У меня есть несколько гарантий относительно результирующего дерева.

• Это полное двоичное дерево , означающее, что у каждого узла будет 0 или 2 дочерних элемента.
• Независимо от того,не узел является листом или ветвь содержится в списке предварительного заказа.

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

Примерсписка узлов в предзаказе может быть:

Branch(1), Branch(2), Leaf(3), Branch(4), Leaf(5), Leaf(6), Branch(7)

Результирующее дерево:

       1
     /   \
   2       7
  / \
 3   4
    / \
   5   6

Нет другого дерева, о котором я могу думать, которое могло бы быть построено из приведенного выше списка предзаказа..

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

Я бы предпочел решения на Rust, но приветствуются подсказки или решения на C, C ++, Python, Java или даже просто псевдокоде.

Answer 1

По прошествии некоторого времени я создал решение своей проблемы.

По сути, у вас есть переменная, которая содержит текущий узел, с которым вы работаете, начиная с корня.Когда вы встречаете ветвь, вы добавляете ветвь к дочерним узлам текущего узла, а затем устанавливаете текущий узел на эту ветвь.Когда вы встречаете лист, вы добавляете лист к дочерним узлам текущего узла.Вы делаете это в цикле while, пока список не станет пустым.В начале каждой итерации цикла вы проверяете, имеют ли дочерние узлы текущего узла == 2, если это так, вы указываете узлу указатель на его родителя и продолжаете делать это до тех пор, пока переменная текущего узла не укажет на узел, у которого <2 дочерних узла.</p>

Вот моя реализация Rust с ограничением:

struct Node { /* ... */ }
impl Node { /* ... */ }

enum NodeType {
    Branch(i32),
    Leaf(i32),
}

impl NodeType { /* ... */ }

fn list_to_tree(list: &[NodeType]) -> Node {
    let mut iter = list.iter();
    let root = Node::new(iter.next().unwrap().get_data());
    let mut node = &root;

    while let Some(next) = iter.next() {
        while node.child_count() == 2 {
            node = node.parent_ref();
        }

        match next {
            NodeType::Branch(data) => {
                node.add_child(Node::new(data));
                node = next;
            }
            NodeType::Leaf(data) => {
                node.add_child(Node::new(data));
            }
        }
    }

    root
}

Предполагается, что задан непустой список, и что этот список является правильным списком предварительного порядка, сделанным из дерева с точно 0 или 2детей на узел.

Answer 2

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

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

void preorder(Node * root)
{
  if (root == Node::NullPtr)
    {
      cout << "NULL ";
      return;
    }

  cout << root->key << " ";
  preorder(root->left);
  preorder(root->right);
}

Предположим, что у вас есть обход предзаказа в vector<string> объекте, тогда для получения исходного дерева вы можете сделать:

Node * restore(const vector<string> & a, int & i)
{
  string key = a[i++];
  if (key == "NULL")
    return Node::NullPtr;

  Node * p = new Node;
  p->key = key;
  p->left = preorder(a, i);
  p->right = preorder(a, i);

  return p;
}

И официальный интерфейс будет:

Node * restore(const vector<string> & a)
{
  int i = 0;
  return restore(a, i)
}