树（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
网友评论