了解伪代码以通过预遍历构造树 [英] Understanding pseudocode to construct tree from preorder traversal

问题描述

我需要执行与该问题中描述的任务类似的操作:
构造具有预定遍历的树

I need to do something similar to the task described in this question:
Construct tree with pre-order traversal given

这里有一个非常有用的答案，但是我不完全理解伪代码，所以我想知道是否有人可以帮助我描述发生了什么事情.

There is a really helpful answer here, but I don't understand the pseudocode fully, so I was wondering if someone could help describe to me what is going on.

k = 0 // Initialize
input = ... get preorder traversal vector from user ... // Get input
Reconstruct(T) // Reconstruct method with tree input
  if input[k] == N // If element of input is N
    T = new node with label N // Make a new node with label N in tree T
    k = k + 1  // Increment k for next loop (Is this whole thing a loop? or a method call?)
    Reconstruct(T.left) // ?????
    Reconstruct(T.right) // ?????
 else // If element of input is L
    T = new node with label L // Make a new node with label L in tree T
    T.left = T.right = null // ?????
    k = k + 1 // Increment k for next loop

我在评论中写了我对事情的理解，如果有人可以检查我的理解是正确的，以及问号在做什么，我将非常感激.此外，此伪代码是否会在输入中遇到L时通过遍历输入并回溯来生成新树?还是重建现有的二叉树?

I have written my understanding of things in the comments and I'd really appreciate it if someone could check that my understanding is correct, and what the question mark bits are doing. Also, is this pseudocode making a new tree by running through the input and backtracking whenever an L is encountered in the input? Or is it reconstructing an existing binary tree?

推荐答案

没有循环. k是全局范围的变量，可以在Reconstruct(T)中访问.它只是字符数组(输入字符串)的当前索引.

There is no loop. k is a globally-scoped variable which can be accessed within Reconstruct(T). It is simply the current index of the character-array (the input string).

如您所参考的问题中所述(具有预遍历遍历的构造树)，正确的算法是先做一个节点的左子节点，然后做右子节点，这是您在if.如果当前节点恰好是叶子L，则不要为其赋予子节点并返回到调用函数.

As explained in the question you referenced (Contsruct Tree with Pre-Order Traversal), The proper algorithm is to do the left-child of a node, then the right-child Which is what you see in the true section of the if. If the current node happens to be a leaf, L, then do not give it children and return to the calling function.

此函数的作用是沿着树的左边缘，将子代添加到所有N节点，而不是将子代添加到所有L节点(又称叶子)，直到字符串完成.

What this function does is follows the left edge of the tree, adding children to all N nodes and not adding children to all L nodes (aka leaves) until the string finishes.

当伪代码的作者说出T.left = T.right = null时，这意味着此时，当前节点没有左或右子节点(因为它是叶子).这只是一个断言，不一定需要包含在代码中.

When the author of the pseudocode says T.left = T.right = null, it means that at this point, the current node has no left or right child (because it is a leaf). This is just an assertion and does not necessarily need to be in the code.

这篇关于了解伪代码以通过预遍历构造树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！