用给定的遍历遍历构造树

用给定的遍历遍历构造树

这是预遍历算法：

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

让我们尝试寻找输入的算法

NNLLNL

。

显然，首先打印了根标签。因此，您知道根目录具有label

N

。现在该算法在左子树上递归。这也

N

根据输入。递归到它的左子树上

L

。现在您必须回溯，因为您已经到了一片空白。输入中的下一个位置也是

L

，因此当前节点有一个标记为的右孩子

L

。回溯一次。再次回溯，因为您已经添加了当前节点的所有子节点（最多2个子节点）。现在，您又回到了根。您必须向右走，因为您已经向左走。根据输入，这是

N

。因此，根的正确子是

N

。那的左孩子将是

L

。这是你的树：

       N     /       N     N   /    /  L   L L

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

伪代码：

k = 0input = ... 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

用空节点调用。

后续问题 ：考虑到包含不同节点标签的二叉树的前序遍历和有序遍历，如何才能唯一地重建树？