封装公司架构类型的数据结构(多叉树)

在有些时候,需求中含有类似公司结构的内容,本身就是个多叉树的结构,在交互过程中,遍历查找的效率低下,然后就想了一下用字典树的结构去封装,但是又存在一个问题,就是树必须有唯一一个根节点,如果有多家公司同属一家公司,这些公司之间都是独立的,没有母公司的话,字典树就不太适合了,然后就考虑一下,可不可以结合字典树及哈希表的优点,生成一个可用的公司结构类型的工具呢?在这种情况下,思虑后,写出了以下代码.(以下是修改后的,之前用的是Map,后来实际用起来,取出来的同级部门无序,改用数组,并增加了一些公开方法).
外层类:
{
Array<Node> _rootMap;
Map<ID,Node> _allNode;
}
节点类:
{
Obj element; //模型
String id; //模型id
Array<Node> arr; //模型对应的子部门
__weak Node parentNode; //模型对应的父部门
}
类似:

image.png

整个的数据结构:
_rootMap:存储着所有公司的节点,也就是根节点,每个节点对应一家公司,该公司节点Node下又存在子部门的Arr,并用弱引用指向父节点,整个过程下去,一个完整的关系结构就建好了
_allNode:保存着所有中间产生的节点,并用ID作为key,这样是为了快速查找到某个模型对应的节点,辅助用
为了让其变得更通用,通过协议的方式,让外部传本身id和父id字段.
这样整个数据结构的查找速度超快

上面是整个的思路和结构,下面上代码
公开的类及API

/*
 针对组织架构类型的数据结构

 注意事项:
 a.所有部门的id唯一
 b.最顶层部门的parentID必须相同,可以都为nil
 c.模型需要实现GYJDepartmentMapProtocal协议

 1.使用方式
 例子:针对这种类型的数据
 {
     "departments":[
         {
             "parentID":null,
             "id":"oi12",
             "info":"部门信息1"
         },
         {
             "parentID":"oi12",
             "id":"oias2",
             "info":"部门信息2"
         },
         {
             "parentID":"oi12",
             "id":"oi2d2",
             "info":"部门信息3"
         },....
     ]
 }
 
 @interface Model:NSObject <GYJDepartmentMapProtocal>
 
 @property(nonatomic,copy)NSString *parentID;
 @property(nonatomic,copy)NSString *id;
 .
 .
 .
 部门的其他属性
 
 @end
 
 @implementation Model
 
 - (NSString *)nodeId
 {
    return self.id;
 }
 - (NSString *)nodeParentId
 {
    return self.parentID
 }
 
 @end

工具类代码

@protocol GYJDepartmentMapProtocal <NSObject>
@required
//本身的id
- (NSString *)nodeId;
//父部门的id
- (NSString *)nodeParentId;

@end

@interface GYJDepartmentMap : NSObject

//添加元素
- (void)addElements:(NSArray<NSObject<GYJDepartmentMapProtocal>*> *)elements;
//返回当前id的所有子id的元素
- (NSMutableArray *)children:(NSObject<GYJDepartmentMapProtocal>*)element;
//获取父部门
- (NSObject<GYJDepartmentMapProtocal>*)parent:(NSObject<GYJDepartmentMapProtocal>*)element;
//返回兄弟部门
- (NSMutableArray<NSObject<GYJDepartmentMapProtocal>*>*)brothers:(NSObject<GYJDepartmentMapProtocal>*)element;

//返回所有的一级部门
- (NSMutableArray<NSObject<GYJDepartmentMapProtocal>*>*)roots;
//根据当前对象,对象的层级关系 祖父部门->....->父部门->当前部门
- (NSMutableArray<NSObject<GYJDepartmentMapProtocal>*>*)relationShipByElements:(NSObject<GYJDepartmentMapProtocal>*)element;
//所有的节点内容
- (NSMutableArray<NSObject<GYJDepartmentMapProtocal>*> *)allElements;
//清空保存的内容
- (void)clear;

@end

内部实现

#import "GYJDepartmentMap.h"
#import "GYJQueue.h"

#pragma mark 节点类
//节点
@interface GYJMultiwayNode : NSObject

@property(nonatomic,strong)NSObject<GYJDepartmentMapProtocal> *element; //存储的单个模型对象
@property(nonatomic,copy)NSString *myId;  //模型对象本身的部门id
@property(nonatomic,strong)NSMutableArray<GYJMultiwayNode *> *arr; //存储所有的子部门
@property(nonatomic,weak)GYJMultiwayNode *parent;  //父部门的节点

- (instancetype)initWithElement:(NSObject<GYJDepartmentMapProtocal> *)element myId:(NSString *)myId parent:(nullable GYJMultiwayNode *)parent;

@end

@implementation GYJMultiwayNode

- (instancetype)initWithElement:(NSObject<GYJDepartmentMapProtocal> *)element myId:(NSString *)myId parent:(nullable GYJMultiwayNode *)parent
{
    if (self = [super init]) {
        _element = element;
        _myId = myId;
        _parent = parent;
        _arr = [[NSMutableArray alloc]init];
    }
    return self;
}

@end

#pragma mark 关系类

@interface GYJDepartmentMap ()

//存储所有根部门的数组(内部是多层关系结构)
@property(nonatomic,strong)NSMutableArray<GYJMultiwayNode *> *rootDic;
//存储所有的部门(存储单个部门),维护的一个字典,快速根据id查找对应的node
@property(nonatomic,strong)NSMutableDictionary<NSString *,GYJMultiwayNode *> *allNodes;

@end

@implementation GYJDepartmentMap

- (instancetype)init
{
    if (self = [super init]) {
        _rootDic = [[NSMutableArray alloc]init];
        _allNodes = [[NSMutableDictionary alloc]init];
    }
    return self;
}
//添加元素
- (void)addElements:(NSArray<NSObject<GYJDepartmentMapProtocal>*> *)elements
{
    if(elements == nil || elements.count == 0) return;
    NSString *rootId = [self searchRootParentID:elements];
    //创建数组(存储的为0,1) 标记已用的对象,将OC的字符串比较转化为数值的直接比较,减少msgSend的函数调用
    int *markArr = (int *)malloc(sizeof(int) * elements.count);
    //数组内容初始化为0
    memset(markArr, 0, sizeof(int)*elements.count);
    //获取到所有的根节点
    NSArray<NSObject<GYJDepartmentMapProtocal>*> *tmp = [self searchAllRoot:elements byRootId:rootId markArr:markArr];
    //存储第一层的数据
    [self addNodeToRoot:tmp];
    //存储后面的数据
    [self addOthersNode:elements markArr:markArr];
    free(markArr);
}
- (void)addOthersNode:(NSArray<NSObject<GYJDepartmentMapProtocal>*> *)elements markArr:(int *)markArr{
    
    GYJQueue *queue = [[GYJQueue alloc]init];       //创建队列
    for (NSInteger i = 0; i < _rootDic.count; i++) {
        GYJMultiwayNode *node = _rootDic[i];
        [queue enterQueue:node];
    }
    while (![queue isEmpty]) {
        GYJMultiwayNode *node = (GYJMultiwayNode *)[queue outQueue];  //队列出队
        for (int i = 0; i<elements.count; i++) {
            if(*(markArr+i) == 1) continue;
            NSObject<GYJDepartmentMapProtocal>*element = elements[i];
            if ([node.myId isEqualToString:[element nodeParentId]]) {
                GYJMultiwayNode *childNode = [[GYJMultiwayNode alloc]initWithElement:element myId:[element nodeId] parent:node];
                [queue enterQueue:childNode];
                [node.arr addObject:childNode];
                [_allNodes setValue:childNode forKey:childNode.myId];
                *(markArr+i) = 1;
            }
        }
    }
}
- (void)addNodeToRoot:(NSArray<NSObject<GYJDepartmentMapProtocal>*> *)rootElements {
    if (rootElements==nil || rootElements.count==0) return;
    for (NSInteger i = 0; i < rootElements.count; i++) {
        NSObject<GYJDepartmentMapProtocal>*cur = rootElements[i];
        GYJMultiwayNode *node = [[GYJMultiwayNode alloc]initWithElement:cur myId:[cur nodeId] parent:nil];
        [_rootDic addObject:node];
        [_allNodes setValue:node forKey:[cur nodeId]];
    }
}
//查找所有根部门的父id,可以为空
- (nullable NSString *)searchRootParentID:(NSArray<NSObject<GYJDepartmentMapProtocal>*> *)elements
{
    //找出其中一个根部门,获取不存在的parentId
    NSObject<GYJDepartmentMapProtocal> *tmpElemnt = elements[0];
    mark:
    for (int i = 0; i<elements.count; i++) {
        NSObject<GYJDepartmentMapProtocal> *element = elements[i];
        if ([[tmpElemnt nodeParentId] isEqualToString:[element nodeId]]) {
            tmpElemnt = element;
            goto mark;
        }
    }
    return [tmpElemnt nodeParentId];
}
//查找统一的根部门
- (NSArray *)searchAllRoot:(NSArray<NSObject<GYJDepartmentMapProtocal>*> *)elements byRootId:(nullable NSString *)rootId markArr:(int *)markArr
{
    NSMutableArray<NSObject<GYJDepartmentMapProtocal>*> *tmp = [[NSMutableArray alloc]init];
    for (int i = 0; i<elements.count; i++) {
        NSObject<GYJDepartmentMapProtocal> *element = elements[i];
        if (rootId==nil && [element nodeParentId]==nil) {
            [tmp addObject:element];
            *(markArr+i) = 1;
        }
        if (rootId!=nil && [rootId isEqualToString:[element nodeParentId]]) {
            [tmp addObject:element];
            *(markArr+i) = 1;
        }
    }
    return tmp.copy;
}
//返回当前id的所有子id的元素
- (NSMutableArray *)children:(NSObject<GYJDepartmentMapProtocal>*)element
{
    if (element == nil) return nil;
    NSMutableArray *marr = [NSMutableArray array];
    GYJMultiwayNode *node = [self nodeSearchByID:[element nodeId]];
    for (NSInteger i = 0; i<node.arr.count; i++) {
        GYJMultiwayNode *childNode = node.arr[i];
        [marr addObject:childNode.element];
    }
    return marr;
}
//获取父部门
- (NSObject<GYJDepartmentMapProtocal>*)parent:(NSObject<GYJDepartmentMapProtocal>*)element
{
    if (element == nil) return nil;
    GYJMultiwayNode *node = [self nodeSearchByID:[element nodeId]];
    return node.parent==nil?nil:node.parent.element;
}
//返回根部门
- (NSMutableArray<NSObject<GYJDepartmentMapProtocal>*>*)roots
{
    NSMutableArray *marr = [[NSMutableArray alloc]init];
    for (NSInteger i = 0; i < _rootDic.count; i++) {
        GYJMultiwayNode *node = _rootDic[i];
        [marr addObject:node.element];
    }
    return marr;
}
//根据当前元素返回对应的部门node
- (GYJMultiwayNode *)nodeSearchByID:(NSString *)ID{
    if (ID == nil) return nil;
    if ([_allNodes.allKeys containsObject:ID]) {
        return [_allNodes valueForKey:ID];
    }
    return nil;
}
- (NSMutableArray<NSObject<GYJDepartmentMapProtocal>*>*)relationShipByElements:(NSObject<GYJDepartmentMapProtocal>*)element
{
    if (element==nil) return @[].mutableCopy;
    GYJMultiwayNode *node = [self nodeSearchByID:[element nodeId]];
    if (node==nil) return @[].mutableCopy;
    NSMutableArray *marr = [[NSMutableArray alloc]init];
    while (node.parent!=nil) {
        [marr insertObject:node.element atIndex:0];
        node = node.parent;
    }
    [marr addObject:element];
    return marr;
}
- (NSMutableArray<NSObject<GYJDepartmentMapProtocal>*> *)allElements{
    
    NSMutableArray *marr = [[NSMutableArray alloc]init];
    [_allNodes.allKeys enumerateObjectsUsingBlock:^(NSString * _Nonnull obj, NSUInteger idx, BOOL * _Nonnull stop) {
        [marr addObject:[_allNodes valueForKey:obj].element];
    }];
    return marr;
}

//返回兄弟部门
- (NSMutableArray<NSObject<GYJDepartmentMapProtocal>*>*)brothers:(NSObject<GYJDepartmentMapProtocal>*)element{
    GYJMultiwayNode *node = [self nodeSearchByID:[element nodeId]];
    if (node.parent == nil) {
        return [self roots];
    }
    GYJMultiwayNode *parent = node.parent;
    NSMutableArray *marr = [[NSMutableArray alloc]init];
    [parent.arr enumerateObjectsUsingBlock:^(GYJMultiwayNode * _Nonnull obj, NSUInteger idx, BOOL * _Nonnull stop) {
        [marr addObject:obj.element];
    }];
    return marr;
}
//清空保存的内容
- (void)clear
{
    [_rootDic removeAllObjects];
    [_allNodes removeAllObjects];
}

@end

下面是使用工具类验证效果的测试代码

@class DepartmentModel;

@interface RootModel : NSObject

@property(nonatomic,copy)NSString *requestReceiveTime;
@property(nonatomic,copy)NSString *timeConsuming;
@property(nonatomic,strong)NSArray<DepartmentModel *> *resultContent;

+ (NSDictionary *)returnFalseData;//测试数据
@end

@interface DepartmentModel : NSObject<GYJDepartmentMapProtocal>

@property(nonatomic,copy)NSString *id;
@property(nonatomic,copy)NSString *parentId;
@property(nonatomic,copy)NSString *name;
@property(nonatomic,copy)NSString *isAll;
@property(nonatomic,copy)NSString *isChoose;

@end

#import "RootModel.h"

@implementation RootModel

//YYModel 容器属性 需要实现的api
+ (nullable NSDictionary<NSString *, id> *)modelContainerPropertyGenericClass{
    return @{@"resultContent":[DepartmentModel class]};
}
//返回测试数据
+ (NSDictionary *)returnFalseData
{
    NSString *path = [[NSBundle mainBundle] pathForResource:@"departmentData.json" ofType:nil];
    NSString *jsonStr = [[NSString alloc]initWithContentsOfFile:path encoding:NSUTF8StringEncoding error:0];
    NSData *data = [jsonStr dataUsingEncoding:NSUTF8StringEncoding];
    NSDictionary *dic = [NSJSONSerialization JSONObjectWithData:data options:0 error:nil];
    return dic;
}

@end

@implementation DepartmentModel

//本身的id
- (NSString *)nodeId{
    return _id;
}
//父部门的id
- (NSString *)nodeParentId{
    return _parentId;
}
//为了打印时不打印地址,重写这个方法,打印出模型信息
- (NSString *)description
{
    return [NSString stringWithFormat:@"部门名:%@ ID:%@ 父ID:%@", _name,_id,_parentId];
}
@end

测试代码:

    //获取测试数据
    NSDictionary *dic = [RootModel returnFalseData];
    RootModel *model = [RootModel yy_modelWithDictionary:dic];
    NSArray<DepartmentModel *>* departments = model.resultContent;
    
    //创建数据结构,并将数据建立关系
    GYJDepartmentMap *map = [[GYJDepartmentMap alloc]init];
    [map addElements:departments]; //DepartmentModel需要实现 GYJDepartmentMapProtocal协议,关系的建立需要传本身id和父id
    
    //测试代码
    NSArray *roots = [map roots]; //获取所有的父部门
    NSLog(@"0.根部门%@",roots);
    NSInteger index = arc4random_uniform(100)%roots.count;
    NSLog(@"1.当前父部门%@",roots[index]);
    NSArray *children = [map children:roots[index]];
    NSLog(@"1.对应父部门的子部门%@",children);
  
    for (NSInteger i = 0; i<departments.count; i++) {
        DepartmentModel *model = departments[I];
        if ([model.id isEqualToString:@"yuangong2"]) {
            NSArray *relationShip = [map relationShipByElements:model];
            NSLog(@"relationShip:%@",relationShip);
        }
    }

打印结果

2022-06-15 16:51:53.269550+0800 CompleteBinaryTree[34023:1107423] 0.根部门(
    "\U90e8\U95e8\U540d:\U516c\U53f81 ID:gongsi1 \U7236ID:(null)",
    "\U90e8\U95e8\U540d:\U516c\U53f82 ID:gongsi2 \U7236ID:(null)"
)
2022-06-15 16:51:53.269981+0800 CompleteBinaryTree[34023:1107423] 1.当前父部门部门名:公司1 ID:gongsi1 父ID:(null)
2022-06-15 16:51:53.270420+0800 CompleteBinaryTree[34023:1107423] 1.对应父部门的子部门(
    "\U90e8\U95e8\U540d:\U8d22\U52a11 ID:caiwu1 \U7236ID:gongsi1",
    "\U90e8\U95e8\U540d:\U7814\U53d11 ID:yanfa1 \U7236ID:gongsi1"
)
2022-06-15 16:51:53.270754+0800 CompleteBinaryTree[34023:1107423] relationShip:(
    "\U90e8\U95e8\U540d:\U751f\U4ea7\U90e8 ID:shengchang2 \U7236ID:gongsi2",
    "\U90e8\U95e8\U540d:\U751f\U4ea7\U7ecf\U7406 ID:jingli_shengchang \U7236ID:shengchang2",
    "\U90e8\U95e8\U540d:\U64cd\U4f5c\U54582 ID:yuangong2 \U7236ID:jingli_shengchang",
    "\U90e8\U95e8\U540d:\U64cd\U4f5c\U54582 ID:yuangong2 \U7236ID:jingli_shengchang"
)

内容打印正确,并且我一个一个查看了map的结构,也是正确的,可放心使用(已经在项目中用到了的,这个还是改进后的工具)

最后编辑于：2022.09.07 15:35:16

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 204,732评论 6赞 478
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 87,496评论 2赞 381
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 151,264评论 0赞 338
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,807评论 1赞 277
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,806评论 5赞 368
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,675评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 38,029评论 3赞 399
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,683评论 0赞 258
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 41,704评论 1赞 299
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,666评论 2赞 321
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,773评论 1赞 332
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,413评论 4赞 321
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 39,016评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,978评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,204评论 1赞 260
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 45,083评论 2赞 350
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,503评论 2赞 343

封装公司架构类型的数据结构(多叉树)

推荐阅读更多精彩内容