遍历一棵树，从根到 Objective-C 中的所有 children

Question

我想做的简化版本是像这样转动一棵树：

进入这样的数组：["abc","abd","ae"]

基本上我想遍历树从它的根节点到每个 children。

我尝试通过在递归块中放置一个 for-in 循环来做到这一点，但问题是每次递归块时 for 循环都会重新开始。当我异步尝试运行块时，我一直得到 EXC_BAD_ACCESS

有什么建议吗？

Answer 1

假设树是这样表示的：

@interface TreeNode : NSObject
@property(weak,nonatomic) TreeNode *parent;
@property(strong,nonatomic) NSArray *children;
@end

任何节点的谱系（这就是您要查找的）是从根节点到节点的节点列表。这可以像这样递归定义：

- (NSArray *)lineage {
    if (!self.parent) {
        return @[self];
    } else {
        NSMutableArray *lineage = [[self.parent lineage] mutableCopy];
        [lineage addObject:self];
        return lineage;
    }
}

你在寻找树叶的谱系，所以我们需要一种收集树叶的方法。如果我们可以遍历树，我们就可以做到这一点。这是块的一个很好的应用程序，就像这样：

- (void)depthFirst:(void (^)(TreeNode *))block {
    for (TreeNode *node in self.children) {
        [node depthFirst:block];
    }
    return block(self);
}

这提供了一种收集树叶的自然方式：

- (NSArray *)leaves {
    NSMutableArray *leaves = [@[] mutableCopy];
    [self depthFirst:^(TreeNode *node) {
        if (!node.children) [leaves addObject:node];
    }];
    return leaves;
}

将它们放在一起，我们得到：

- (NSArray *)lineagesOfLeaves {
    NSMutableArray lineages = [@[] mutableCopy];
    for (TreeNode *leaf in [self leaves]) {
        [lineages addObject:[leaf lineage]];
    }
    return lineages;
}

这些方法适用于树中的任何节点。不过，对于您的问题，您需要将 lineagesOfLeaves 发送到树的根。

遍历一棵树，从根到 Objective-C 中的所有 children

Traverse a tree from root to all children in Objective-C

tree

recursion

path

objective-c