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

在有些时候,需求中含有类似公司结构的内容,本身就是个多叉树的结构,在交互过程中,遍历查找的效率低下,然后就想了一下用字典树的结构去封装,但是又存在一个问题,就是树必须有唯一一个根节点,如果有多家公司同属一家公司,这些公司之间都是独立的,没有母公司的话,字典树就不太适合了,然后就考虑一下,可不可以结合字典树及哈希表的优点,生成一个可用的公司结构类型的工具呢?在这种情况下,思虑后,写出了以下代码.(以下是修改后的,之前用的是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的结构,也是正确的,可放心使用(已经在项目中用到了的,这个还是改进后的工具)

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容