从列表重建树，深度信息封装在列表中的条目 [英] Reconstruct a tree from a list, with depth info encapsulated in the entry of list

问题描述

我们建立了一个列表，从一棵树（不可以一定是二叉搜索树），通过深度优先遍历。

里面的每个条目是一对（K，D），k是一个节点的密钥，d是节点的深度。

现在，我们需要构建原树从列表中了。

我们怎么办呢？

---

请注意

1. 在树不一定是二叉搜索树
2. 我们不知道的深度优先遍历是否 pre级，有序或后序。

---

我的问题是

• 才能实现的条件下，这种反向工程？我知道二进制搜索树，我们需要至少两个遍历列表（例如，序和后序的列表），以重构原始树。
  • 如何？如果可能的话

解决方案

注意事项：

• 的中序遍历产生一种独特的树

• 在pre级和后序别：

  您可以在这两者之间没有区别：

    1 1
   / \
  2 2
   

  我就产生了一个在左边（这样做可以方便很多）。

我们可以说马上：

• 如果第一个节点是根（即不是深度0）：

  很无论在做，以便与空左子树，或pre-订单。

• 如果最后一个节点是根：

  很无论在做，以便与空右子树，或后序。

• 如果没有上面的：

  我们正在做的序遍历。

有关上述两种情况，我们不知道该做哪些遍历，最简单的方法是尝试生成树两种可能的遍历，并丢弃哪一个不工作（根据以下的限制），如果任。

有一些限制：

有关的顺序，我们不能向右，向上或如果当前​​节点是空的。

有关pre-订单，我们不能去左边或右边，如果当前节点是空的。

有关后序，我们设置当前节点之后去了 - 我们不能去左边或右边，而不必设置当前节点

。

在所有的情况下，我们尝试才上前将右向左走。

按向左走还是向右走，我的意思是创建一个（空的）左或右的孩子，并遍历该节点。
通过'上'，我的意思只是向上遍历已创建的树。

根据上述的限制，它应该是很容易编写的算法生成树。作为一个例子按序：

1. 如果新节点的深度比当前节点的深度更深：
   1. 如果当前节点是空的，没有一个左孩子，我们可以只创建一个左孩子，并设置为当前节点
   2. 否则，如果当前节点不是空的，并且没有一个右子，我们可以只创建一个右孩子，并设置为当前节点
2. 否则，如果深度是相同的当前节点和当前节点是空的，
   该节点的值设置为新的节点
3. 如果没有上述情况下触发，当前节点是空的，
   设置当前节点的父节点为当前节点
4. 如果没有上述情况引发的，失败
5. 如果1.1，1.2，或3触发，重复第1。

示例：

输入：（F，2），（G，2），（B，1），（1,2），（C，1），（A，0）

由于（一，0）是根，我们正在做的无论是在订单或后序。

于是我们产生2子树：

 按顺序后序
    。 。
   / /
  。 。
 / /
F F
 

（。表示空节点）

当我们得到（G，2），我们已经可以抛弃有序树，因为我们不能去的权利或从 F 的母公司，是因为它是空的，所以我们就完蛋了。

然后我们将继续与后序：

 。
   /
  。
 / \
F G


    。
   /
  b
 / \
F G


     。
   / \
  湾
 / \ /
F G我


     。
   / \
  公元前
 / \ /
F G我


     一个
   / \
  公元前
 / \ /
F G我
 

We built a list from a tree (not necessarily a binary search tree) via depth first traversal.

Each entry inside is a pair (k, d), k is the key of a node and d is the depth of that node.

Now we need to construct the original tree back from the list.

How do we do it?

---

Note

1. tree is not necessarily a binary search tree
2. we do not know whether the depth first traversal is pre-order, in-order or post-order.

---

My question is

• Can we achieve this reverse engineering under the conditions? I know for binary search tree, we need at least two traversal lists (e.g., inorder and postorder list) to reconstruct the original tree.
  • How? if possible

解决方案

Things to note:

• The in-order traversal produces a unique tree

• The pre-order and post-order don't:

  You can't differentiate between these two:

    1    1
   /      \
  2        2
  

  I'll just generate the one on the left (doing this makes it a lot easier).

What we can say right away:

• If the first node is the root (i.e. not depth 0):

  We're either doing in-order with an empty left subtree, or pre-order.

• If the last node is the root:

  We're either doing in-order with an empty right subtree, or post-order.

• If neither of the above:

  We're doing in-order traversal.

For the two cases above where we don't know which traversal to do, the simplest approach is to try to generate the trees for both possible traversals, and discard whichever one doesn't work (based on the below restrictions), if either.

Some restrictions:

For in-order, we can't go right or up if the current node is empty.

For pre-order, we can't go left or right if the current node is empty.

For post-order, we have to go up after setting the current node - we can't go left or right without having set the current node.

In all cases, we try to go left before going right before going up.

By 'go left' or 'go right', I mean creating an (empty) left or right child and traversing to that node.
By 'go up', I mean simply traversing upwards in the already created tree.

Based on the above restrictions, it should be easy to write an algorithm to generate the tree. As an example for in-order:

1. If the new node's depth is deeper than the current node's depth:
   1. If the current node is empty and doesn't have a left child, we can just create a left child and set that as the current node
   2. Otherwise, if the current node is not empty and doesn't have a right child, we can just create a right child and set that as the current node

2. Otherwise, if the depth is the same as the current node and the current node is empty,
   set that node's value to the new node
3. If none of the above cases triggered and the current node is empty,
   set the parent of the current node as the current node
4. If none of the above cases triggered, fail
5. If 1.1, 1.2, or 3 triggered, repeat from 1.

Example:

Input: (f, 2), (g, 2), (b, 1), (i, 2), (c, 1), (a, 0)

Since (a, 0) is the root, we're doing either in-order or post-order.

So then we generate 2 subtrees:

in-order        post-order
    .                .
   /                /
  .                .
 /                /
f                f

(. indicates an empty node)

When we get (g, 2), we can already discard the in-order tree, as we can't go right or up from f's parent, because it is empty, so we're stuck.

Then we continue with post-order:

    .
   /
  .
 / \
f   g


    .
   /
  b
 / \
f   g


     .
   /   \
  b     .
 / \   /
f   g i


     .
   /   \
  b     c
 / \   /
f   g i


     a
   /   \
  b     c
 / \   /
f   g i

这篇关于从列表重建树，深度信息封装在列表中的条目的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！