我已经了解了树遍历和树数据结构,因此我现在知道什么是预遍历树遍历,但是我也看到有些东西叫做修改后的预树遍历,但是我发现很难找到关于树遍历和文档的知识。两者之间有什么区别。有人可以对此发表评论吗?我确实找到了一篇有关解释它的文章,但是该图看起来与常规的预购相似,作者写的唯一一件事是一个节点有两个附加值,而且我不确定那是否正确。
我读过的文章:http://imrannazar.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
当我在Google上搜索时,似乎在几个地方都使用了此预购树遍历的修改版本,因此我发现有些奇怪,因为没有更多的文章解释这些差异。
最佳答案
我对命名有点不同意,也许您对此有一些困惑。
我将“遍历”定义为遍历的过程。
我们从遍历中得到的结果可能被称为“表示形式”。
MPTT更像是一种遍历,而不是遍历。
另外,左侧的值可以被认为是预购商品,而右侧的值可以被认为是预购商品(我们将介绍...)。
因此,我可能宁愿将其命名为“组合的前后前后遍历表示形式”。
现在来看这到底是什么。
如上所述,这只是一种表示。
让我们看一下一种从树生成这种表示的算法:
traverse(node, index)
node.left = index
for each child c of node
traverse(c, ++index)
node.right = ++index
从上面的代码可以看出,我们在递归给子代之前和之后都对节点进行了处理,因此可以将其视为前后遍历的某种组合。
现在,此订单与预订单或后订单之间最重要的区别是如何使用它。
前置或后置通常是您在树上运行或用于从中生成树的一种方法(可能是紧凑地将其存储到磁盘上,而当您实际想要使用树时,可能会在内存中生成典型的基于指针的表示形式)。
但是使用MPTT,这就是您在使用树时实际表示树的方式。这在不特别关注递归的数据库中特别有用。
您将MPTT值存储在表中,这些值将使您能够高效地执行各种查询。例如:(源自here)
以上两种方法都可以使用单个查询来执行,而递归表示将需要对路径中的每个节点进行一个查询,而对于后代则需要进行一些查询。