构造树给出pre序遍历 [英] Construct tree with pre-order traversal given

问题描述

一个特殊类型的树被赋予其中所有的叶子都标有→和其他标有 N 。每个节点可以有0个或最多2个节点。树的preorder穿越给出。

A special type of tree is given where all leaves are marked with L and others are marked with N. Every node can have 0 or at most 2 nodes. The preorder traversal of the tree is given.

给出一个算法，从这个遍历构建树。

Give an algorithm to build the tree from this traversal.

推荐答案

这是preorder遍历算法：

This is the preorder traversal algorithm:

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

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

显然根的标签被第一印刷。所以，你知道root具有标签 N 。现在递归算法的左子树。这也是 N 根据输入。递归上的左子树，这是→。现在，你必须原路返回，因为你已经达到了叶。在输入的下一个位置也是→，这样当前节点有右子标记→。原路返回一次。又原路返回，因为你已经添加了当前节点（最多2名儿童）的所有儿童。现在你是在根目录了。你必须去正确的，因为你已经去了离开。根据输入的，这是 N 。所以根的右子是 N 。那左边的孩子会→。这是你的树：

Obviously the label of the root is printed first. So you know the root has label N. Now the algorithm recurses on the left subtree. This is also N according to the input. Recurse on the left subtree of that, which is L. Now you have to backtrack, because you've reached a leaf. The next position in the input is also L, so the current node has a right child labeled with L. Backtrack once. Backtrack again, because you've added all the children of the current node (max 2 children). Now you're at the root again. You have to go right, because you already went left. According to the input, this is N. So the right child of the root is N. The left child of that will be L. This is your tree:

       N
     /   \
    N     N
   / \   /
  L   L L

请注意，该解决方案不一定是唯一的，但是这将让你一个可能的解决方案。

Note that the solution is not necessarily unique, but this will get you a possible solution.

伪code：

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

呼叫使用空节点。

Call with a null node.

后续问题：给予两个preorder和二叉树含有不同的节点标签，你怎么能独特地重构树的序遍历

Follow-up question: given both the preorder and the inorder traversal of a binary tree containing distinct node labels, how can you uniquely reconstruct the tree?

这篇关于构造树给出pre序遍历的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！