构造具有预先遍历遍历的树

Question

给出一种特殊类型的树,其中所有树叶都标有标记,L其他树标记有N.每个节点可以有0个或最多2个节点.给出了树的前序遍历.

给出一个算法来从这个遍历构建树.

Answer 1

这是预订序遍历算法:

Preorder(T)
  if (T is not null)
    print T.label
    Preorder(T.left)
    Preorder(T.right)

让我们试着找一个输入的算法NNLLNL.

显然,首先打印根标签.所以你知道root有标签N.现在算法在左子树上进行递归.这也是N根据输入.递归到左边的子树,即L.现在你必须回溯,因为你已经到了一片叶子.输入中的下一个位置也是L,因此当前节点有一个标有的右子项L.回溯一次.再次回溯,因为您已添加当前节点的所有子节点(最多2个子节点).现在你又回到了原点.你必须走对,因为你已经离开了.根据输入,这是N.所以根的正确的孩子是N.左边的孩子就是L.这是你的树:

       N
     /   \
    N     N
   / \   /
  L   L L

请注意,解决方案不一定是唯一的,但这将为您提供可能的解决方案.

伪代码:

k = 0
input = ... get preorder traversal vector from user ...
Reconstruct(T)
  if input[k] == N
    T = new node with label N
    k = k + 1 
    Reconstruct(T.left)
    Reconstruct(T.right)
  else 
    T = new node with label L
    T.left = T.right = null
    k = k + 1

使用空节点调用.

后续问题:给定包含不同节点标签的二叉树的预订和顺序遍历,您如何才能唯一地重建树？