树的基本实现
树用于展示物与物之间的等级关系，如下图所示
树由多个结点组成，每个结点都关联这另一个结点。
结点可以有多个子结点，但做多只能有一个父结点。没有父结点的结点称为根结点，没有子结点的结点称为叶子结点
这篇文章我们展示的是一个通用树，并没有限定一个结点下面需要多少个子结点，也没有规定这些结点的排序
public class TreeNode<T> {
public var value: T
public weak 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
}
}
重写类的description方法，使其方便打印查看
extension TreeNode: CustomStringConvertible {
public var description: String {
var s = "\(value)"
if !children.isEmpty {
s += " {" + children.map { $0.description }.joined(separator: ", ") + "}"
}
return s
}
}
使用方法:
let tree = TreeNode<String>(value: "beverages")
let hotNode = TreeNode<String>(value: "hot")
let coldNode = TreeNode<String>(value: "cold")
let teaNode = TreeNode<String>(value: "tea")
let coffeeNode = TreeNode<String>(value: "coffee")
let chocolateNode = TreeNode<String>(value: "cocoa")
let blackTeaNode = TreeNode<String>(value: "black")
let greenTeaNode = TreeNode<String>(value: "green")
let chaiTeaNode = TreeNode<String>(value: "chai")
let sodaNode = TreeNode<String>(value: "soda")
let milkNode = TreeNode<String>(value: "milk")
let gingerAleNode = TreeNode<String>(value: "ginger ale")
let bitterLemonNode = TreeNode<String>(value: "bitter lemon")
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)
通过上面的代码我们就建立了如下图所示的树。beverages为根结点，black，green，chai，coffee，cocoa，soda，milk, ginger ale bitter leamon为叶子结点.
对于任何结点，你都可以通过parent访问他们的父结点
teaNode.parent
teaNode.parent!.parent
通常我们会用以下的词来评论树
树的高度：从根结点到最底层的叶子结点的连接数，比如上图中树的高度为3.因为从根结点到最深的叶子结点有3次连接
结点深度：从根结点到该结点的连接数，比如上图中的tea的结点深度为2.因为从根结点到该结点有2次连接
还有很多其他方式来构建一棵树，比如有时候你可能不需要父结点，或者每个结点最多只有两个结点（二叉树）
树的遍历
当我们查找树是否包含某个值的时候，我们需要遍历树。先对比该结点的value值，如果不匹配，则依次遍历该结点的子结点。因为这些子结点的类型和当前结点的类型是一致的，所以可以直接使用递归的方式来遍历（查看子结点的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") // returns the "cocoa" node
tree.search("chai") // returns the "chai" node
tree.search("bubbly") // nil
