如何从preorder和inorder遍历构建二叉树 [英] how to build a binary tree from preorder and inorder traversals

问题描述

我正在做一个关于从预订和inorder遍历（每个节点中的一个char）构建二叉树的任务，并且我试图围绕如何构建实际的树包裹我的大脑。

Im doing an assignment on building a binary tree from the preorder and inorder traversals (a char in each Node) and im trying to wrap my brain around how to build the actual tree.

以下是关于如何完成此操作的思考过程：

Here is my thought process on how to accomplish this:

1. 将预订中的第一个条目存储为根节点


2. 搜索该条目的inorder。


3. 将字符串放在根节点的左侧，并将它们保存为char数组。


4. 将字符放在根节点的右边，并将它们保存为字符数组。


5. 创建一个新树，其中root用作父节点，其中2孩子是左右char数组。


6. 继续递归，直到预订长度为0。

1. store the first entry in the preorder as the root node
2. search the inorder for that entry.
3. take the chars to the left of the root node and save them as a char array.
4. take the chars to the right of the root node and save them as a char array.
5. make a new tree, with the root as the parent and its 2 children being the left and right char arrays.
6. keep going recursively until the preorder length is 0.

我已经完成了步骤1-4，但我不太确定如何正确构建我的树，并且想知道是否有人有任何指针。谢谢。

I have steps 1-4 taken care of, but im not too sure how to properly build my tree, and was wondering if anyone had any pointers. Thank you.

推荐答案

在构建新树之前进行递归。因此，您的列表将如下所示：

Do the recursion before building the new tree. So, your list would look like this:

1. 如果数组的长度为1，则只返回包含此单个项目的叶节点。 （这是递归基础。）（O（1））


2. 将预订单数组中的第一个条目存储为根节点。 （O（1））


3. 在inorder数组中搜索该条目。 （O（n））


4. 将字符放在inorder数组中根节点的左侧，并将它们保存为char数组。从预订单数组中获取相同数量的字符（在根之后）。 （O（n）或O（1）当只是抛出指针/索引时。）


5. 将字符放在根节点的右边并保存它们作为char数组。从预订单数组中获取相同数量的字符（在第一部分之后 - 应该只是剩余部分）。 （O（n）或O（1）当只是抛出指针/索引时。）


6. 从两个char数组中递归地生成一个树。


7. 从两个右侧char数组递归生成一个树。


8. 将两个树与根节点组合在一起。 （O（1）。）

1. If the arrays have length 1, just return a leaf node with this single item in it. (This is the recursion foundation.) (O(1))
2. Store the first entry in the preorder array as the root node. (O(1))
3. Search the inorder array for that entry. (O(n))
4. Take the chars to the left of the root node in the inorder array and save them as a char array. Take the same amount of characters from the preorder array (after the root). (O(n), or O(1) when just throwing pointers/indexes around.)
5. Take the chars to the right of the root node and save them as a char array. Take the same amount of characters from the preorder array (after the first part – that should be just the remainding part). (O(n), or O(1) when just throwing pointers/indexes around.)
6. Recursively make a tree from both left char arrays.
7. Recursively make a tree from both right char arrays.
8. Combine both trees with your root node. (O(1).)

非递归部分可以在O（n）中完成总的来说，每个递归级别的总和也是O（n）。因此总运行时间取决于递归级别的数量。如果你有一个近似平衡的树，深度是O（log n），因此我们得到O（n·log n）。由于唯一必然缓慢的部分是在inorder数组中搜索根节点，我想如果我们对树有更多了解，我们可以优化它甚至更多。

The non-recursive parts can be done in O(n) overall, and summing them up for each recursion level is also O(n) each. The total runtime thus depends on the number of recursion levels. If you have a approximately balanced tree, the depth is O(log n), thus we get to O(n · log n) at all. As the only necessarily slow part is the search of the root node in the inorder array, I guess we could optimize that even a bit more if we know more about the tree.

在最坏的情况下，我们在树中的每个节点都有一个递归级别，达到复杂度O（n·n）。

In the worst case we have one recursion level for each node in the tree, coming to complexity O(n·n).

示例：预订ABCDEF，Inorder FEDCBA，树：

Example: Preorder ABCDEF, Inorder FEDCBA, Tree:

                                   +---+
                                   | A |
                                   ++--+
                                    |
                            +---+   |
                            | B +<--+
                            ++--+
                             |
                     +---+   |
                     | C +<--+
                     ++--+
                      |
              +---+   |
              | D +<--+
              ++--+
               |
       +---+   |
       | E +<--+
       ++--+
        |
+---+   |
| F +<--+
+---+

这篇关于如何从preorder和inorder遍历构建二叉树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！