建立多叉树

记录一次用于表示全国省市区地址树的建立和处理过程.

关于地址树的处理

当前服务端返回的节点数据是这样的:

{
                "id": "110102",
                "parentId": "110100",
                "parentIds": "110000,110100,110102",
                "name": "西城区",
                "parentName": "市辖区",
                "parentNames": "北京市市辖区西城区",
                "type": "3",
                "code": "110102",	// 暂未使用
                "sort": 2			// 暂未使用
}

可以将这个 JSON 转换为下面的这个实体:

struct Node {
	let nodeID: String		// id "110102"
    let parentID: String	// parentId "110100"
    let fullPath: String	// parentIds "110000,110100,110102"
	let name: String		// "西城区"
    let parentName: String	// "市辖区"
    let parentNames: String	// "北京市市辖区西城区"
    let depth: String		// "3"
}

操作:

• 获取指定 ID 的节点
• 获取指定 ID 节点的所有子节点.(在指定 ID 节点获取的时候就可以直接拿到.)

比如获取根节点后, 就可以直接拿到它的所有子节点, 就是一级节点.

拿到一个一级节点, 向下拿它的孩子就是所有的二级, 依次类推. 这样就无需每次去遍历整个地址数组了!!!! 且存储空间也可以减少很多!!!

如果能够将结构重建, 则可以减少很多内存占用, 比如可以将节点简化为如下的造型:

// 树节点的泛型定义: 如果 children.isEmpty == true, 则是叶子节点
class TreeNode<T> {
    let value: T
    let children: [TreeNode<T>]
}

extension TreeNode<T> {
    func isLeaf() -> Bool {
        return children.isEmpty
	}
}

struct Area {
	let nodeID: String		// id "110102"
	let name: String		// "西城区"
}

// 建树

// 根节点定义: 其中 children 是全部深度 1 的节点
let rootValue = Area(nodeID: "0", name: "")
let rootNode = TreeNode<Area>(value: rootValue, children: ...)

ContiguousArray 曰: 居然在 swift 中早就有了…即顺序存储的线性表.

为什么要选择 class 呢? 由于不知道该树中的 Node 是否会被外部修改, 如果使用 struct, 则修改不会被同步到树上, 而是被复制到新的地方, 所以说用 class 更好.

要解决问题:

• 建树: 通过原始数据, 按老办法过滤一遍?
• 遍历: BFS, DFS.

已经将工程放到这里了, 实际解决的时候用的是蛮力建树, 直接将每个结点连接到它的父结点, 不过这里将子节点存储放到双向链表中提高加入的效率.