排序谓词，以深度优先搜索顺序对节点进行排序 [英] sort predicate to have nodes sorted in Depth First Search order

问题描述

我有一个节点列表，其中每个节点都属于一棵或多棵树。 （它们不一定共享一个共同的祖先）。

I have a list of nodes, where each of the nodes belong to one or multiple trees. (they do not necessarily share a common ancestor)

我想对节点进行排序，顺序与深度优先搜索时发现它们的顺序相同。

I want to sort the nodes in the same order I would find them when doing a Depth First Search.

我有一个谓词将树根排序在一起，另一个谓词将一个共同父母的孩子排序在一起。每个节点都有一个父级访问器和一个子级枚举器。我想避免出于性能原因使用Children枚举（如果可能）。

Let say I have a predicate for sorting tree roots together, and another predicate to sort children of a common parent together. Each node have a Parent accessor, and a children enumerator. I want to avoid using the Children enumeration for performance reasons (if possible).

将谓词传递给排序函数的伪代码是什么（谓词将如果节点1小于节点2，则返回一个布尔值。）

What can be the pseudo code for a predicate to pass to a sort function (the predicate would return a boolean value if node 1 is less than node 2).

推荐答案

我找到了一个简单的解决方案：

I found an easy working solution:

对于一个节点，有一个从根返回路径的函数。例如，在文件系统中，文件的路径可能是：c：\directory\file.txt，其中 C：， directory和 file.txt是父节点。

For a node, have a function that returns the path from the root. For example, in a file system, the path for a file could be : c:\directory\file.txt, where "C:", "directory" and "file.txt" are the parent nodes.

谓词只需要比较路径，就像简单的字符串比较一样。路径不必是字符串，路径比较功能需要从根开始逐个比较路径元素，并在路径元素不同时立即返回。

The predicate simply need to compare the paths together, as a simple string comparison would do. The path does not need to be a string, the path comparison function need to compare path elements one by one starting at the root, and return as soon a path element is different.

结果排序与深度优先搜索相同。

The resulting sort is the same as a Depth First Search.

这篇关于排序谓词，以深度优先搜索顺序对节点进行排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！