在常数时间内从二叉树中获取数据

Question

预序遍历： 

后序遍历： 

中序遍历： 

我有一个二叉树，每个节点都有预序遍历号、后序遍历号和中序遍历号(从0到11)。如何使用每个节点的中序遍历号、预序遍历号和后序遍历号，在常数时间内获得给定节点u为根的子树的大小？

编辑：

例如，要确定w是否在u的子树中，您需要u的前序号、u的后序号、w的前序号和w的后序号。

因为如果w的前序号大于u的前序号，并且w的后序号小于u的后序号，则我们可以得出结论：w在u的子树中。

- MinGW

---

你需要实现B树还是需要使用B树？如果你需要使用B树，有一些库可以支持你，你不需要自己实现。 - PersianGulf

@MinGw 你的意思是如果输入是5，那么答案应该是0、0和12，并且在每种情况下都需要恒定的时间吗？ - java_doctor_101

Answer 1

很棒的谜题！我希望这不是一份作业，因为我即将揭晓它。

`pre_order（u.right）- pre_order（u.left）+ post_order（u.right）- post_order（u.left）+ 1 ==子树中节点数。

`pre_order（u.right）- pre_order（u.left）`计算左子树中节点数，因为从左子树开头到右子树开头的“距离”就是左子树的大小。

同样，`post_order（u.right）- post_order（u.left）`计算右子树中节点数，因为左子树结尾和右子树结尾之间的差异就是右子树的大小。

添加1包括树本身的根。如果该侧没有孩子，则显然任一项可能为零。

---

上图中的节点没有名称。我的理解是上图中的数字表示pre_order（x）或post_order（x）或in_order（x）的值，其中x是我们不知道名称但其在树中的位置对观众来说是明显的节点。

在“现实生活”中，每个节点都包括：（可选名称），中序值，前序值，后序值，（可选）左子节点，（可选）右子节点和其他信息。

考虑最右下角的节点; `post_order（u）== 8`，`post_order（u.left）`未定义，`pre_order（u.left）`和`in_order（u.right）`等也是如此，因为它没有子节点。

考虑节点u，使得pre_order（u）== post_order（u）== in_order（u）== 3，然后post_order（u.left）== 1，pre_order（u.right）== 5 。

- Dwayne Towell

---

首先，这不是作业。但是我可能会在截止日期后发布我的作业。其次，你提供了一个很好的解决方法，但是你的方法并不需要常数时间，在这个问题中，你实际上看不到二叉树的形状。你应该只使用每个节点的数字。 - MinGW

它是常数时间。它使用节点中的4个（或更少）数字。没有搜索、迭代等。 - Dwayne Towell

左子节点的末尾和右子节点末尾的差异。在这里，您如何获取左侧和右侧末尾的数字？您所知道的唯一数字是给定节点u中的一个数字。 - MinGW

节点u知道它的左右子节点，因为它是一棵树。查看子节点是一个常数时间操作（没有迭代）。 - Dwayne Towell

如果你说Node，你知道它的左右子节点，它就能工作。但是我不确定这一点，因为只有一个Node u被给定。 - MinGW

问题：如果给定节点数u为8，那么 "pre_order(u.left) == 0" 是否成立？ - MinGW