Swift算法俱乐部中文版 -- 树

2016-10-19 本文已影响140人云抱住阳光太阳没放弃发亮

树（Tree）表示对象之间的层次关系。这是一棵树：

树由节点（node）组成，这些节点彼此链接。

节点与他们的子节点有链接，并且通常与他们的父节点有链接。子节点（children）是给定节点下面的节点；父节点（parent）是上面的节点。节点总是只有一个父节点，但可以有多个子节点。

没有父节点的节点是根节点（root）。没有子节点的节点是叶节点（leaf）。

树中的链接不会形成循环。这不是一棵树：

这种结构称为图形（graph）。树实际上是一个非常简单的图形。（类似的，链表是一棵树的简单版本，想想吧！）

这篇文章谈论一个通用树。没有限制每个节点可能具有多少个子节点，或者树中的节点的顺序。

这里是一个简单的 Swift 语言的实现：

public class TreeNode<T> {
    public var value: T
    
    public var parent: TreeNode?
    public var children = [TreeNode<T>]()
    
    public init(value: T) {
        self.value = value
    }
    
    public func addChild(_ node: TreeNode<T>) {
        children.append(node)
        node.parent = self
    }
}

这描述了树中的单个节点。它具有通用类型 T ，对父节点 parent 的引用，和子节点数组 children。

添加描述方法 description() 以便您可以打印树的信息：

extension TreeNode: CustomStringConvertible {
    public var description: String {
        var s = "\(value)"
        if !children.isEmpty {
            s += " {" + children.map{ $0.description }.joined(separator: "，") + "}"
        }
        return s
    }
}

在 playground 测试：

tree.addChild(hotNode)
tree.addChild(coldNode)

hotNode.addChild(teaNode)
hotNode.addChild(coffeeNode)
hotNode.addChild(chocolateNode)

coldNode.addChild(sodaNode)
coldNode.addChild(milkNode)

teaNode.addChild(blackTeaNode)
teaNode.addChild(greenTeaNode)
teaNode.addChild(chaiTeaNode)

sodaNode.addChild(gingerAleNode)
sodaNode.addChild(bitterLemonNode)

tree.description // beverages {hot {tea {black，green，chai}，coffee，cocoa}，cold {soda {ginger ale，bitter lemon}，milk}}

这对应以下结构：

beverages 是根节点，因为它没有父节点。black，green，chai，coffee，cocoa，ginger ale，bitter lemon，milk是叶节点，因为它们没有子节点。

对于任何节点，都可以查看父节点，直到根节点：

teaNode.parent // "hot" 
nodeteaNode.parent!.parent // 根节点

我们经常在谈论树时使用这些定义：

树的高度。这是根节点和最低叶节点之间的链接数。在我们的例子中，树的高度是3，因为从底部到根节点需要经过三次跳跃。
节点的深度。此节点与根节点之间的链路数。例如 tea 的深度是 2，因为它需要两次跳跃到达根节点。（根节点的深度是0）

有许多不同的方法来构建树。有时你不需要有一个父节点。或者你只需要给每个节点最多两个子节点 - 这样的树被称为二叉树。一个常见的树类型是二叉搜索树（vs BST），一个更严格的二叉树，其中节点以特定方式排序以加速搜索。

在这里展示的通用树非常适合描述层次结构的数据，但它真的取决于你的应用程序需要有什么样的额外功能。

下面是一个如何使用 TreeNode 类来确定树是否包含特定值的示例。首先看看节点自己的 value 属性。如果不匹配，那么依次查看子节点的值。当然，那些子节点也是 TreeNode，所以他们重复递归相同的过程：首先看看自己的 value，然后看看自己的子节点。它们的子节点也会做同样的事情。

代码如下：

extension TreeNode where T: Equatable {
    func search(_ value: T) -> TreeNode? {
        if value == self.value {
            return self
        }
        for child in children {
            if let found = child.search(value) {
                return found
            }
        }
        return nil
    }
}

使用这个例子：

tree.search("cocoa")    // "cocoa" 节点
tree.search("chai")     // "chai" 节点
tree.search("bubbly")   // nil

也可以用数组来描述树。根据数组的索引创建不同节点之间的链接。例如，如果我们的节点对应的索引是：

0 = beverage    5 = cocoa       9  = green
1 = hot         6 = soda        10 = chai
2 = cold        7 = milk        11 = ginger ale
3 = tea         8 = black       12 = bitter lemon
4 = coffee

然后我们可以用下面的数组描述树：

[ -1, 0, 0, 1, 1, 1, 2, 2, 3, 3, 3, 6, 6 ]

数组中的每个元素都是指向其父节点的指针。索引为 3 的元素 tea ，数组中的值是 1 因为其父节点是 hot。根结点在数组中的值是 -1 因为它没有父节点。您只能从一个节点回到根节点，而不能反过来。

顺便说一下，你会看到关于森林（forest）的算法。不出所料，这是单独给树对象的集合的名称。

作者：Matthijs Hollemans -- Swift算法俱乐部

英文链接：https://github.com/raywenderlich/swift-algorithm-club/tree/master/Tree

Swift算法俱乐部中文版 -- 树

猜你喜欢

热点阅读