代码之家 › 专栏 › 技术社区 › Senseful

将分层平面数据(w/parentid)转换为具有缩进级别的排序平面列表的算法

hierarchical-data language-agnostic algorithm

Senseful · 技术社区 · 14 年前

我有以下结构:

MyClass {
  guid ID
  guid ParentID
  string Name
}

我想创建一个数组,其中包含元素的显示顺序应在层次结构中(例如,根据它们的“左”值),以及一个哈希,它将guid映射到缩进级别。

例如:

ID     Name     ParentID
------------------------
1      Cats     2
2      Animal   NULL
3      Tiger    1
4      Book     NULL
5      Airplane NULL

这基本上会产生以下对象:

// Array is an array of all the elements sorted by the way you would see them in a fully expanded tree
Array[0] = "Airplane"
Array[1] = "Animal"
Array[2] = "Cats"
Array[3] = "Tiger"
Array[4] = "Book"

// IndentationLevel is a hash of GUIDs to IndentationLevels.
IndentationLevel["1"] = 1
IndentationLevel["2"] = 0
IndentationLevel["3"] = 2
IndentationLevel["4"] = 0
IndentationLevel["5"] = 0

为了清晰起见,层次结构如下:

Airplane
Animal
  Cats
    Tiger
Book

我想尽可能少地重复这些项。我也不想创建分层数据结构。我更喜欢使用数组、哈希、堆栈或队列。

这两个目标是:

将ID的哈希存储到缩进级别。
根据左值对保存所有对象的列表进行排序。

当我得到元素列表时,它们没有特殊的顺序。兄弟姐妹应按其名称属性排序。

更新: 这看起来好像我自己还没有想出解决办法,只是想让别人帮我做这项工作。然而,我试着提出三种不同的解决方案,而且每种方案我都被卡住了。一个原因可能是我试图避免递归(可能是错误的)。我并没有公布目前为止我得到的部分解决方案,因为它们是错误的,可能会严重影响其他人的解决方案。

3 回复 | 直到 14 年前

Leftium 14 年前

我需要一个类似的算法来对具有依赖关系的任务进行排序(每个任务都可以有一个需要先完成的父任务)。 我发现 拓扑排序 . 这里是一个 iterative implementation in Python 有非常详细的评论。

在进行拓扑排序时,可以计算缩进级别。只需将节点的缩进级别设置为其父节点的缩进级别+1,因为它被添加到拓扑顺序中。

注意,可以存在许多有效的拓扑顺序。为了保证生成的拓扑顺序对具有子节点的父节点进行分组,选择一种基于局部排序信息生成的图的深度优先遍历的拓扑排序算法。

维基百科给出 two more algorithms for topological sort . 注意,这些算法没有那么好,因为第一个算法是广度优先遍历,第二个算法是递归的。

Jakub Hampl 14 年前

对于层次结构,您几乎肯定需要递归(如果允许任意深度)。我很快编写了一些Ruby代码来说明如何实现这一点。( ~~虽然我还没有做压痕~~ ):

# setup the data structure
class S < Struct.new(:id, :name, :parent_id);end

class HierarchySorter

    def initialize(il)
        @initial_list = il
        first_level = @initial_list.select{|a| a.parent_id == nil}.sort_by{|a| a.name }
        @final_array = subsort(first_level, 0)
    end

    #recursive function
    def subsort(list, indent_level)
        result = []
        list.each do |item|
            result << [item, indent_level]
            result += subsort(@initial_list.select{|a| a.parent_id == item.id}.sort_by{|a| a.name }, indent_level + 1)
        end
        result
    end

    def sorted_array
        @final_array.map &:first
    end

    def indent_hash
        # magick to transform array of structs into hash
        Hash[*@final_array.map{|a| [a.first.id, a.last]}.flatten]
    end

end

hs = HierarchySorter.new [S.new(1, "Cats", 2), S.new(2, "Animal", nil), S.new(3, "Tiger", 1), S.new(4, "Book", nil),
    S.new(5, "Airplane", nil)]

puts "Array:"
puts hs.sorted_array.inspect

puts "\nIndentation hash:"
puts hs.indent_hash.inspect

如果你不说红宝石,我可以用别的东西来做。

编辑: 我更新了上面的代码以输出两个数据结构。

输出:

Array:
[#<struct S id=5, name="Airplane", parent_id=nil>, #<struct S id=2, name="Animal", parent_id=nil>, #<struct S id=1, name="Cats", parent_id=2>, #<struct S id=3, name="Tiger", parent_id=1>, #<struct S id=4, name="Book", parent_id=nil>]

Indentation hash:
{5=>0, 1=>1, 2=>0, 3=>2, 4=>0}

Senseful 14 年前

Wonsung的文章帮助了很多,不过这是一个普通的图表,而不是一棵树。所以我对它做了一些修改,创建了一个专门为树设计的算法:

// Data strcutures:
nodeChildren: Dictionary['nodeID'] = List<Children>;
indentLevel: Dictionary['nodeID'] = Integer;
roots: Array of nodes;
sorted: Array of nodes;
nodes: all nodes

// Step #1: Prepare the data structures for building the tree
for each node in nodes
  if node.parentID == NULL
    roots.Append(node);
    indentLevel[node] = 0;
  else
    nodeChildren[node.parentID].append(node);

// Step #2: Add elements to the sorted list
roots.SortByABC();
while roots.IsNotEmpty()
  root = roots.Remove(0);
  rootIndentLevel = indentLevel[root];
  sorted.Append(root);
  children = nodeChildren[root];
  children.SortByABC();
  for each child in children (loop backwards)
    indentLevel[child] = rootIndentLevel + 1
    roots.Prepend(child)