从根遍历树在Objective-C的所有儿童

Question

什么，我想做一个简单的版本是把这样的树：

到像这样的数组：“ABC”，“ABD “，”ae“]

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

我已经尝试通过在递归块中放入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到树的根。