從根遍歷樹在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到樹的根。