修改预购和仅预购有什么区别？

Question

我读过树遍历和树数据结构，所以我现在知道什么是预序树遍历，但我也看到有一种叫做修改预序树遍历的东西，但我发现找到关于它的好的答案或文档有点困难这两者之间的区别是什么。有人可以对此发表评论吗？我确实找到了一篇关于解释它的文章，但图表看起来与常规预购相似，作者唯一写的是一个节点有两个附加值，我不确定这是否正确。

我阅读的文章：http : //imrannaz.com/Modified-Preorder-Tree-Traversal 我也看过这个：http : //www.sitepoint.com/hierarchical-data-database-2/但我有一个很难相信这位自称是大学经济学专业的作者，他在撰写有关树结构的文章。Django 的 mptt 模块是它被使用的地方：http ://django-mptt.github.io/django-mptt/overview.html#what-is-modified-preorder-tree-traversal

当我在谷歌上搜索时，这个预序树遍历的修改版本似乎在几个地方被使用，所以我发现没有更多解释差异的文章有点奇怪。

Answer 1

我有点不同意命名，也许你这边对此有些困惑。

我将“遍历”定义为遍历的过程。

我们从遍历中得到的结果我可能称之为“表示”。

MPTT 与其说是遍历，不如说是一种表示。

此外，左边的值可以被认为是前序的，而右边的值可以被认为是后序的（我们会得到那个......）。

因此，我可能更愿意将其命名为“组合前/后序遍历表示”。

现在来看看这实际上是什么。

如上所述，它只是一种表示。

让我们看一下从树中生成这种表示的算法：

traverse(node, index)
   node.left = index

   for each child c of node
     traverse(c, ++index)

   node.right = ++index

从上面的代码可以看出，我们在递归到子节点之前和之后都对节点进行了一些操作，因此可以将其视为前序和后序遍历的某种组合。

现在这个和前序或后序之间更显着的区别在于它的使用方式。

前序或后序通常是您在树上运行或用于生成树的东西（可能将其紧凑地存储到磁盘，而当您真正想要使用树时，可能会在内存中生成典型的基于指针的表示）。

但是对于 MPTT，这将是您在使用它时实际表示树的方式。这在不特别关注递归的数据库中特别有用。

您将 MPTT 值存储在您的表中，这些值将使您能够有效地执行各种查询。例如：（源自此处）

• 要获取节点的所有后代，您需要在该节点的左右值之间寻找左值。

• 要获取节点的/所有祖先的路径，您需要查找左值小于此左值且右值大于此右值的节点。

以上两个都可以使用单个查询来执行，其中递归表示将需要对路径中的每个节点进行一次查询，并且......对后代进行一些查询。