objective-c - 如何跟踪此对象图深度优先搜索算法中的深度？

Question

我有这段代码遍历一棵树，进行深度优先搜索。每个元素都只处理一次。很好。

-(void)iterateOverTree:(TreeNode *)node
{
    NSMutableArray * elements = [NSMutableArray array];
    [elements addObject:node];

    while([elements count])
    {
        TreeNode * current = [elements objectAtIndex:0];
        [self doStuffWithNode:current];
        for(TreeNode * child in current.children)
        {
            [elements addObject:child];
        }

        [elements removeLastObject];
    }
}

但是:如何跟踪图表中的当前深度？我需要知道深度级别。例如，我有这些节点:

A 有 child B、J。B有 child C。C有 child D。D 有 child E、F、I。

当A处于深度级别1时，则B为2，C为3。

通过递归，很容易跟踪当前的深度级别。只需在调用自身之前递增一个变量，并在调用自身之后递减它。

但是这里不可能有这种奇特的 while 循环。没有盒子中的盒子，就像递归一样。

我真的不想必须向 TreeNode 对象添加属性(或实例变量)，因为这应该可以以通用方式重用于任何类型的对象图。

有没有人知道如何做到这一点？我必须引入另一个数组来跟踪访问过的节点吗？

Answer 1

我认为您也确实需要堆叠深度。如果你有一个递归版本，这就是你实际上会做的事情。只是存储将是“不可见的”，因为您会使用调用堆栈而不是像现在这样使用显式堆栈。

如果对您有帮助，您可以轻松地将深度优先搜索转换为广度优先搜索，方法是将数组用作队列而不是堆栈。 (只需执行 removeFirstObject 而不是 removeLastObject。)然后您就会知道您总是按照非递减深度的顺序查看节点。但是，如果您需要精确的深度，我认为您仍然需要添加一些存储来跟踪何时必须增加当前深度。

更新:

如果您按照节点的父指针来备份树，则您应该能够在完全没有堆栈的情况下执行 DFS。这将使保持深度变得简单。但是你必须小心，不要通过重新扫描 child 来找出你在哪里来破坏线性时间最坏情况的复杂性。

如果您没有父指针，应该可以堆叠足够的信息来跟踪父指针。但这意味着您在堆栈上放置了比当前更多的信息，因此与直接堆栈深度相比并没有太大的改进。

顺便说一下，仔细看一下你的算法，当你得到下一个当前节点时，你是不是看错了数组的一侧？它应该像这样工作:

push root
while stack not empty:
   current = pop
   push all children of current