c# - 生成站点地图的递归算法

Question

我有一个包含以下列的站点地图层次结构的数据表:

• 项目编号
• 父级
• 姓名
• 网址

我需要在 HTML 中生成一组嵌套列表(为清楚起见，将 anchor 元素留在外面):

<ul>
<li>Item 1</li>
<li>Item 2</li>
    <ul>
    <li>Sub Item 1</li>
    <li class="current">Sub Item 2</li>
    </ul>
<li>Item 3</li>
</ul>

树应该只包含通向“当前”节点/页面的分支(因此使用上面的示例不会显示项目“1”或“3”的任何子项目。任何人都可以帮忙提供一些伪代码/代码示例可以从叶到根遍历树构建 HTML？谢谢。

Answer 1

这是一些伪代码。这个想法很简单:从所有未标记的节点开始，然后标记当前节点的父节点、它的 父节点等等，直到到达根节点。通过这样做，您将准确标记从当前节点到根的路径上的节点。然后您可以简单地在另一遍中打印所有节点，仅在“标记”节点上递归。这是最优的(运行时间最多是您必须打印的节点数)。

for all n: mark[n]=False
n=current
while n!=root:
    n=parent[n]
    mark[n]=True

def print_tree(n):
    print_node(n)
    if mark[v]==True:
        print '<ul>'
        for each child c of n: print_tree(c)
        print '</ul>'

def print_node(n):
   if n==current: print '<li class="current">' else: print '<li>'
   print name[n]
   print "</li>"

print_tree(root)

parent[n] 和 name[n] 可能类似于 n.parent 和 n.name 在你的结构中。关于“对于 n 的每个子节点”部分——我假设您有一个邻接列表维护给定节点的所有子节点的列表。 (如果不这样做，那么打印子节点的顺序是什么？)在任何情况下，只需将每个节点添加到它的 parent 。列表的总大小最多是节点数(因为除根节点之外的每个节点恰好出现在一个列表中)所以这些列表不会占用太多内存(单个列表可能包含很多元素，但总大小是有界的)。