Tree(树)

树的结构

普通树的结构如图所示

树结构

3个重要概念

1 Root(根):一棵树只有一个根，可以理解成树的入口
2 Node(节点):至少有一个child，根也是一个Node
3 Leaf(叶):没有child的节点

代码表示

@interface Node : NSObject

@property(nonatomic, copy) NSString *value;

//子节点
@property(nonatomic, strong, readonly) NSMutableArray *children;
//父节点,可能不存在(例如根节点),使用weak避免循环引用
@property(nonatomic, weak) Node *parent;

+ (instancetype)nodeWithValue:(NSString *)value;

- (void)addChild:(Node *)node;

- (Node *)searchWithValue:(NSString *)value;

@end

@interface Node ()

@property(nonatomic, strong, readwrite) NSMutableArray *children;

@end

@implementation Node

+ (instancetype)nodeWithValue:(NSString *)value
{
    return [[[self class] alloc] initWithValue:value];
}

- (instancetype)initWithValue:(NSString *)value
{
    if (self = [super init]) {
        _value = value;
    }
    
    return self;
}

- (void)addChild:(Node *)node
{
    if (!self.children) {
        self.children = [NSMutableArray new];
    }
    
    [_children addObject:node];
    
    node.parent = self;
}

- (Node *)searchWithValue:(NSString *)value
{
    if ([value isEqualToString:_value]) {
        return self;
    }
    
    for (Node *node in self.children) {
        
        Node *found = [node searchWithValue:value];
        
        if (found != nil) {
            return found;
        }
        /*这里写法出错，导致找bug找了一个小时
        if ([node searchWithValue:value]) {
            return node;
        }
         */
    }
    
    return nil;
}

@end

构造一颗如图所示的树

结构

- (void)nodeTest
{
    Node *beverages = [Node nodeWithValue:@"beverages"];//饮料
    
    Node *hot = [Node nodeWithValue:@"hot"];//热料
    Node *cold = [Node nodeWithValue:@"cold"];//冷料
    
    Node *tea = [Node nodeWithValue:@"tea"];//茶
    Node *coffee = [Node nodeWithValue:@"coffee"];//咖啡
    Node *cocoa = [Node nodeWithValue:@"cocoa"];//可可可乐
    
    Node *blackTea = [Node nodeWithValue:@"blackTea"];//黑茶
    Node *greenTea = [Node nodeWithValue:@"greenTea"];//绿茶
    Node *chaiTea = [Node nodeWithValue:@"chaiTea"];//红茶
    
    Node *soda = [Node nodeWithValue:@"soda"];//
    Node *milk = [Node nodeWithValue:@"milk"];//
    
    Node *gingerAle = [Node nodeWithValue:@"gingerAle"];//姜水
    Node *bitterLemon = [Node nodeWithValue:@"bitterLemon"];//
    
    [beverages addChild:hot];
    [beverages addChild:cold];
    
    [hot addChild:tea];
    [hot addChild:coffee];
    [hot addChild:cocoa];
    
    [cold addChild:soda];
    [cold addChild:milk];
    
    [tea addChild:blackTea];
    [tea addChild:greenTea];
    [tea addChild:chaiTea];
    
    [soda addChild:gingerAle];
    [soda addChild:bitterLemon];
    
  [beverages searchWithValue:@"cocoa"];// returns the "cocoa" node
  [beverages searchWithValue:@"greenTea"];// returns the "greenTea" node
  [beverages searchWithValue:@"soda"];//nil
}

参考连接

参考1(raywenderlich)