树 Tree 基本信息及实现

TreePreview.png

树（Tree）是一种很重要的数据结构，在软件开发的多方面都有使用：

• 表示层级结构。
  • 计算机语言的抽象语法树。
  • 解析人类语言的树。
  • XML 和 HTML 文档对象模型。
  • 处理 JSON 和YAML 文档。
• 快速查找数据。
• 管理有序数据。

树的类型有很多，其有不同的形状和大小。这一篇文章将介绍树的基本信息，以及如何实现树。

1. 术语

下面是一些与树相关常见术语。

1.1 节点 Node

与链表相似，树也由节点构成。

TreeNode.png

每个节点包含数据和指向子节点的引用。

1.2 父节点 Parent、子节点 Child

Tree 从顶部向下看，和植物中的树很像，只是方向相反。

每个节点向上都有一个节点（最顶部节点除外），上面的节点称为父节点（parent node）。节点的下面，与其直接相连的称为子节点（child node）。在树中，每个child只有一个parent。

TreeParentChild.png

1.3 根节点 Root

树最顶部的节点称为根节点（root），根节点是唯一没有父节点的节点。

TreeRoot.png

1.4 叶子节点 Leaf

如果节点没有子节点，则称为叶子节点（leaf）。

TreeLeaf.png

此外，还有以下常用术语：

• 节点的度（degree）：该节点子树的个数称为该节点的度。
• 树的度：所有节点中，度的最大值称为树的度。
• 非叶子节点：度不为零的节点。
• 高度（height）：当前节点到最远叶子节点的路径长，所有树叶的高度为零。
• 深度（depth）：对于任意节点n，n的深度为从根到n的唯一路径长。有些地方认为根深度为0，有些地方认为根深度为1。
• 兄弟节点：具有相同父节点的节点互相称为兄弟节点。
• 节点的层数（level）：从根开始定义，根为第一层，根的子节点为第二层。以此类推。
• 堂兄弟节点：父节点在同一层的节点互为堂兄弟。
• 节点的祖先（ancestor）：从根到该节点所经分支上的所有节点。
• 子孙（descendant）：以某节点为根的子树中任一节点都称为该节点的子孙。
• 森林：由m（m >= 0）棵互不相交的树的集合称为森林。

2. 实现

Tree 由 node 构成，这里先创建TreeNode类。

创建一个 playground，并在 Sources 中添加TreeNode.swift文件，TreeNode代码如下：

public class TreeNode<T> {
    public var value: T
    public var children: [TreeNode] = []
    
    public init(_ value: T) {
        self.value = value
    }
}

每个 node 存储一个值和一个数组，数组里存储着 children。

在TreeNode中添加以下代码：

    /// 向当前节点添加子节点
    /// - Parameter child: 要添加的子节点
    public func add(_ child: TreeNode) {
        children.append(child)
    }

在 playground page 中添加以下代码：

example(of: "creating a tree") {
    let beverages = TreeNode("Beverages")
    
    let hot = TreeNode("Hot")
    let cold = TreeNode("Cold")
    
    beverages.add(hot)
    beverages.add(cold)
}

树可以很方便的用于层次结构问题。上述代码定义了三个节点，并组织成逻辑层次，其对应于以下结构：

TreeHierarchical.png

3. 遍历算法 Traversal Algorithms

线性表（如数组、链表、队列）有明确的开始、结束位置，遍历很简单。

TreeLinearCollections.png

与线性表相比，遍历树会变得复杂些。

TreeTraversal.png

遍历时左侧节点有优先权吗？深度与优先权有关联吗？在实际应用时，应根据要解决的问题决定遍历策略。不同类型树、不同类型问题，有不同遍历方式。

3.1 深度优先

在TreeNode.swift底部添加以下方法：

extension TreeNode {
    /// 深度优先遍历
    public func forEachDepthFirst(visit: (TreeNode) -> Void) {
        visit(self)
        children.forEach({
            // 使用递归遍历
            $0.forEachDepthFirst(visit: visit)
        })
    }
}

如果不想使用递归，可以使用栈实现。

在 playground page 添加以下代码，检验深度优先遍历：

func makeBeverageTree() -> TreeNode<String> {
    let tree = TreeNode("Beverages")
    
    let hot = TreeNode("hot")
    let cold = TreeNode("cold")
    
    let tea = TreeNode("tea")
    let coffee = TreeNode("coffee")
    let chocolate = TreeNode("cocoa")
    
    let blackTea = TreeNode("black")
    let greenTea = TreeNode("green")
    let chaiTea = TreeNode("chai")
    
    let soda = TreeNode("soda")
    let milk = TreeNode("milk")
    
    let gingerAle = TreeNode("ginger ale")
    let bitterLemon = TreeNode("bitter lemon")
    
    tree.add(hot)
    tree.add(cold)
    
    hot.add(tea)
    hot.add(coffee)
    hot.add(chocolate)
    
    cold.add(soda)
    cold.add(milk)
    
    tea.add(blackTea)
    tea.add(greenTea)
    tea.add(chaiTea)
    
    soda.add(gingerAle)
    soda.add(bitterLemon)
    
    return tree
}

上述代码创建的树如下：

TreeDepthFirst.png

添加以下代码：

example(of: "depth-first traversal") {
    let tree = makeBeverageTree()
    tree.forEachDepthFirst(visit: {
        print($0.value)
    })
}

输出如下：

--- Example of: depth-first traversal
Beverages
hot
tea
black
green
chai
coffee
cocoa
cold
soda
ginger ale
bitter lemon
milk

3.2 层序遍历

层序遍历根据 node depth，先遍历同一层节点。

extension TreeNode {
    /// 层序遍历
    public func forEachLevelOrder(visit: (TreeNode) -> Void) {
        visit(self)
        var queue = Queue<TreeNode>()
        children.forEach({
            queue.enqueue($0)
        })
        
        while let node = queue.dequeue() {
            visit(node)
            node.children.forEach{ queue.enqueue($0)}
        }
    }
}

这里使用队列而非栈确保节点读取顺序。

Queue是队列这篇文章创建的数据结构，你可以在文章底部的源码中获取。

forEachLevelOrder函数按照层序遍历：

TreeLevelOrder.png

使用以下代码进行层序遍历：

example(of: "level-order traversal") {
    let tree = makeBeverageTree()
    tree.forEachDepthFirst(visit: {
        print($0.value)
    })
}

运行后输出如下：

--- Example of: level-order traversal
Beverages
hot
cold
tea
coffee
cocoa
soda
milk
black
green
chai
ginger ale
bitter lemon

3.3 搜索

前面已经介绍了深度优先、层序遍历两种遍历方式，想要搜索 tree 是否包含指定元素就变得简单了。

extension TreeNode where T: Equatable {
    public func search(_ value: T) -> TreeNode? {
        var result: TreeNode?
        forEachDepthFirst { (node) in
            if node.value == value {
                result = node
            }
        }
        return result
    }
}

使用以下代码搜索指定值：

example(of: "searching for a node") {
    let tree = makeBeverageTree()
    
    if let searchResult1 = tree.search("ginger ale") {
        print("Found node: \(searchResult1.value)")
    }
    
    if let searchResult2 = tree.search("WKD Blue") {
        print(searchResult2.value)
    } else {
        print("Couldn't find WKD Blue")
    }
}

运行后控制台输出如下：

--- Example of: searching for a node
Found node: ginger ale
Couldn't find WKD Blue

深度优先遍历时，如果有多个匹配值，则会取最后一个。

4. 树算法题

4.1 同一层节点打印到同一行

根据节点所在层，将同一层节点打印到同一行。如下图：

TreePrintInLevel.png

输出应如下所示：

15 
1 17 20 
1 5 0 2 5 7 

使用层序遍历可以解决按照层打印的问题，只需判断出何时换行。如下所示：

func printEachLevel<T>(for tree: TreeNode<T>) {
  var queue = Queue<TreeNode<T>>()
  var nodesLeftInCurrentLevel = 0
  
  queue.enqueue(tree)
  while !queue.isEmpty {
    nodesLeftInCurrentLevel = queue.count
    // 循环打印一层
    while nodesLeftInCurrentLevel > 0 {
      guard let node = queue.dequeue() else { break }
      print("\(node.value)", terminator: " ")
      node.children.forEach { queue.enqueue($0) }
      nodesLeftInCurrentLevel -= 1
    }
    // 换行
    print()
  }
}

使用nodesLeftInCurrentLevel记录队列当前元素数量，此时打印队列元素时不打印换行符，直到该层打印结束才换行。

该算法时间复杂度为O(n)。由于初始化了队列作为节点的容器，空间复杂度也是O(n)。

4.2 为树添加父节点

树的定义中只包含了子节点，删除、旋转等操作时需要用到父节点，应如何为树添加父节点？

可以按照下面方式为树添加一个父节点属性：

public class TreeNode<T> {
    public weak var parent: TreeNode?
    ...
}

根节点没有父节点，因此这里使用了可选类型。节点对子节点强引用，对父节点需为弱引用，否则会产生循环引用。

总结

树有以下这些要点：

• 树与链表有一些相似的地方，但链表只能有一个子节点，树可以有多个子节点。
• 除根节点外，所有节点都只有一个父节点。
• 叶子节点没有子节点。
• 像层序遍历、深度优先遍历算法，适用于所有类型树。但可能因树类型不同，具体实现有所差异。

Demo名称：Tree
源码地址：https://github.com/pro648/BasicDemos-iOS/tree/master/Tree

欢迎更多指正：https://github.com/pro648/tips

本文地址：https://github.com/pro648/tips/blob/master/sources/树%20Tree%20基本信息及实现.md