数据结构和算法(五) - 树

与链表一样，树由节点组成。每个节点包含一些数据并跟踪其子节点。

父节点和子节点

每个节点（最顶层的节点除外）都连接到它上面的一个节点。 该节点称为父节点。 直接在其下方并连接到它的节点称为其子节点。 在树上，每个子节点只有一个父节点。

父节点与子节点

根节点

树中最顶层的节点称为树的根。 它是唯一没有父节点的节点

根节点

叶子

如果节点没有子节点，则该节点是叶子

节点的叶子

实现

创建一个树节点

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

每个节点存储一个值，并使用数组保存对其所有子节点的引用。

添加一个子节点

public func add(_ child: TreeNode) {
        children.append(child)        
    }

层次结构是树结构的自然候选者，定义了三个不同的节点并将它们组织成逻辑层次结构。

let beverages = TreeNode("Root")

let hot = TreeNode("node1")
let cold = TreeNode("node2")

beverages.add(hot)
beverages.add(cold)
beverages.children.forEach { (node) in
    print(node.value)  // node1,  node2
}

屏幕快照 2018-12-15 下午4.36.54.png

遍历算法

迭代线性集合（如数组或链表）非常简单。 线性集合有明确的开始和结束, 但是迭代树却不同, 哪边是开始?哪边又是结束? 从左边的叶子开始迭代还是从右边的叶子开始迭代?

深度优先遍历(Depth-first traversal)

对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次.

举个例子, 下图是一个树, 使用DFS遍历, 从Root点出发(访问顺序不固定, 因为Root 下有两个N1, N2), 若从N1开始, 其顺序为Root->N1->A->a, 此时没有路了, 开始回溯到A, (A)->b, 此时也没有路了, 回溯到A, (A)->c, 至此得到的顺序为Root->N1->A->a->b->c, 依次类推, 最终的结果为Root->N1->A->a->b->c->B->C->N2->D->d->e->E

屏幕快照 2018-12-16 下午1.42.56.png

代码实现, 首先构造一下这个树

func makeBeverageTree() -> TreeNode<String> {
    let tree = TreeNode("Root")
    
    let N1 = TreeNode("N1")
    let N2 = TreeNode("N2")
    
    let A = TreeNode("A")
    let B = TreeNode("B")
    let C = TreeNode("C")
    
    let a = TreeNode("a")
    let b = TreeNode("b")
    let c = TreeNode("c")
    
    let D = TreeNode("D")
    let E = TreeNode("E")
    
    let d = TreeNode("d")
    let e = TreeNode("e")
    
    tree.add(N1)
    tree.add(N2)
    
    N1.add(A)
    N1.add(B)
    N1.add(C)
    
    N2.add(D)
    N2.add(E)
    
    A.add(a)
    A.add(b)
    A.add(c)
    
    D.add(d)
    D.add(e)
    
    return tree
}

遍历实现

// 1
 func forEachDepthFirst(node:TreeNode, visit: (TreeNode) -> Void) {
        // 2
        visit(node)
        // 3
        children.forEach { (nextNode) in
            // 4
            nextNode.forEachDepthFirst(node: nextNode, visit: { (n) in
                 //5 
                visit(n)
            })
        }
    }

1. forEachDepthFirst函数需要一个node参数, 当前的节点, visit是一个闭包, 该闭包需要一个TreeNode参数, 无返回值. 这个闭包的主要的作用就是为了返回找到的节点
2. visit(node) 的参数是node, 代表当前的节点
3. 这个是比较绕的地方, 首先forEach是一个同步函数, 这就说明遍历是有序的, 而深度优先遍历需要的就是顺着一个分支一直往下查找, 直到结束. 详细的解释再说.
4. 调用自己, 进行递归操作
5. 回调

let tree = makeBeverageTree()
        tree.forEachDepthFirst(node: tree) {
            print($0.value)
        }

要比较清楚的了解forEachDepthFirst的执行过程, 首先要了解递归, 说起递归, 鸡生蛋, 蛋生鸡的现象其实都是抽象出来的递归，但是严格来说并不是递归，因为会一直重复下去，没有终止条件，那就称为死循环了。可以把递归理解为一个无线的循环, 但是在某一个满足条件的时刻就会结束循环.

用阶乘一个例子来讲解递归的执行流程

一个正整数的阶乘（factorial）是所有小于及等于该数的正整数的积，并且0的阶乘为1。自然数n的阶乘写作n!。即n!=1×2×3×...×n

代码实现

  func factorial(n:Int) -> Int
    {
        //递归边界
        if n == 0 {
            return 1
        }
        //递归公式
        return n * factorial(n: n - 1)
    }

事实上，计算机在运行过程中都是用栈来存储程序中的函数的，在递归运算时，函数也不断地被调用进栈，当运行完毕后再依次出栈。栈是先进后出, factorial被执行的时候回一直被压入栈, 当满足条件 n==0时, 开始返回, 依次出栈.

1. 当n=3时, 不满足条件, return 3 * factorial(n: 3 - 1), 此时 3 * factorial(n: 3 - 1)入栈, 位于栈底
2. 在第一步中 factorial 又调用了自己, 此时n=2, 不满足条件, 再次return 2 * factorial(n: 2 - 1), 此时2 * factorial(n: 2 - 1)入栈
3. factorial又掉了自己, 此时n=1, 不满足条件, 再次return 1 * factorial(n: 1 - 1), 此时1 * factorial(n: 1 - 1)入栈
4. 再次调用自己 又被压入栈, 此时n = 0, 满足条件, return 1, 函数返回, 被压入栈的函数, 依次从栈顶弹出.

这就是递归在栈中实现的执行和回退过程，回退过程的顺序是执行过程中的逆序，下一次调用都为上一次调用提供需要，这符合栈的特点，编译器就是利用这个特点来实现递归管理的。

再来说说我们的forEachDepthFirst递归, 如果说我们的树只有一个分支, 如下图所示

7AA3BB5D-3874-43D1-8D84-2A6AD25FF271.png
只考虑划线的部分, 这正好是一个栈的结构, 经过forEachDepthFirst递归之后, 栈底到顶底依次是Root->N1->A->a(因为实现从Root开始执行, Root最先被压入栈), 然后a满足添加, a下面没有节点, 无路可走了, 开始从栈中弹出. 依次弹出a, A, N1, Root. 函数里面的children.forEach做的事情就是从Root开始, 把每一条路径下面的节点分别压入栈, 依次又弹出.

广度优先遍历

广度优先遍历是以层为顺序，将某一层上的所有节点都搜索到了之后才向下一层搜索

其搜索结果为Root->N1->N2->A->B->C->D->E->a->b->c->d->e, 逐层的去遍历

public func forEachLevelOrder(node:TreeNode, visit: (TreeNode) -> Void) {
        visit(node)
        var queue = Queue<TreeNode>()
        // N1, N2 进入队列
        children.forEach {
            queue.enqueue($0)
        }
    
        /**
         * 搜索的原理就是同一层的节点依次入队列, 入队之后, 依次出队, 每次出队一个节点的时候, 会把出队的节点下的子节点入队, 然后在依次出队, 入队, 这样就达到了一层一层的查找
           以我们的图示为例, 执行顺序为, 先入队N1, N2, 然后N1出队, 把N1下的子节点加入队列, 此时队列是N2, A,B,C
            然后N2出队, D, E 入队, 此时队列是A,B,C,D,E, 依次类推
         */
        while let node = queue.dequeue() {
            visit(node)
            node.children.forEach {
                queue.enqueue($0)
            }
        }
    }

使用一下广度和深度遍历

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

       if let node = tree.search("a", searchNode: tree) {
            print(node.value)
        }else {
            print("not found")
        }

如果找到了我们要搜索的节点返回搜索的节点, 如果找不到, 则返回nil. 讲真, 这个深度和广度还真的绕, 需要好好屡屡, 断点打起来, debug一下.