群组
欢迎加入群组,闲聊工作&技术&问题等

树的定义

        一棵树(tree)是一些节点的集合.这个集合可以为空集.若这个集合非空,则一个树由称做根(root)的节点r和多个子树T1,T2,…Tn组成,这些子树又可以有多个子树,这就让我们想到定义树一个常规方法就是递归,而每棵子树都与根节点r通过一条有向的边(edge)相连.
        每一棵子树叫做根r的儿子(child),根r称做每一棵子树的父亲(praent).所有节点组成的树,共有N个节点和N-1条边.没有儿子的节点也可以称做树叶(leaf),具有相同父亲的多个节点之间互称为兄弟(sibling).

节点的度

一个节点含有子节点的个数称为节点的度,树的度为树中某个节点的最大度即为树的度.

路径

从节点n1到nk看做是树的一条路径(path),这个路径包括了n1到nk的k个节点以及k-1条边,路径的长度也就是该路径上边的个数.

深度

对于任意节点ni的深度指的是从根节点r到节点ni的唯一有效路径的长度.根r的深度为0.

高度

对于任意节点ni的高度指的是从n到树叶节点最长路径的长.一棵树的高度指的是根r到树叶最长的路径长.

节点的层次

节点的层次指的是节点的层级,根r的层数是1,其儿子节点层次是2.所有子节点层次比父亲节点层次大1.

森林

由多棵树组成的集合称为森林.

tree

树的实现

树的构造

// MARK: - 树
class Tree<T:Equatable> {

    // 节点value
    var value:T

    // 子节点
    private(set) var children:[Tree] = []

    // 父节点
    var parent:Tree?

    // MARK: - 构造函数
    init(value:T) {
        self.value = value
    }
}

添加节点

/// 添加节点
    ///
    /// - Parameter treeNode: 子节点
    func addChild(treeNode:Tree) -> Void {
        children.append(treeNode)
        treeNode.parent = self
    }

源码地址

        这里的实现代码已放到GitHub,测试用例详见DataStructureAlgorithmTests.swift文件

参考文献

《数据结构与算法分析C语言描述》(Data Structures and Algorithm Analysis in C:Second Edition)–译者: 冯舜玺


  转载请注明: waitwalker

 上一篇
Class解读 Class解读
群组欢迎加入群组,闲聊工作&技术&问题等 类的声明首先我们在runtime.h文件中看到objc_class的结构声明: /// 类的声明结构 struct objc_class { Class _Nonnull i
下一篇 
快识别隐私政策(Fast OCR Privacy Policy) 快识别隐私政策(Fast OCR Privacy Policy)
我们尊重用户的隐私并对非法窃取用户隐私的行为予以坚决抵制.We respect user privacy and resist those who illegally steal user privacy. 1.快识别依据强大的云技术识别平
2019-04-13
  目录