树 | waitwalker

数据结构与算法

发布日期: 2019-04-14

文章字数: 612

阅读时长: 2 分

阅读次数:

群组
Flutter,iOS,Android,Python等,闲聊工作&技术&问题;
个人主页:https://waitwalker.cn
telegram群链接:https://t.me/joinchat/Ej0o0A1ntlq5ZFIMzzO5Pw

树的定义

一棵树(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
    }