数据结构和算法(六) - 二叉树

什么是二叉树？

在计算机科学中，二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”和“右子树”，左子树和右子树同时也是二叉树。二叉树的子树有左右之分，并且次序不能任意颠倒。

根据二叉树的定义, 我们来实现二叉树

public class BinaryNode<Element> {
    //1
    public var value: Element
    //2
    public var leftChild: BinaryNode?
    //3
    public var rightChild: BinaryNode?
    //4
    public init(value: Element) {
        self.value = value
    }
}

1. value 用于存储当前节点的值
2. leftChild是当前节点的左节点, 做节点为可选值, 说明该值不确定
3. rightChild与leftChild类似
4. 初始化节点值

构造一个二叉树

func structureTree() -> BinaryNode<Int> {
    let zero = BinaryNode(value: 0)
    let one = BinaryNode(value: 1)
    let five = BinaryNode(value: 5)
    let seven = BinaryNode(value: 7)
    let eight = BinaryNode(value: 8)
    let nine = BinaryNode(value: 9)
    
    seven.leftChild = one
    one.leftChild = zero
    one.rightChild = five
    seven.rightChild = nine
    nine.leftChild = eight
    
    return seven
}

构造的二叉树示意图

屏幕快照 2018-12-18 上午11.08.08.png

二叉树遍历

二叉树遍历分为三种：前序、中序、后序

屏幕快照 2018-12-18 上午11.13.33.png

比如上图正常的一个满节点，A：根节点、B：左节点、C：右节点，前序顺序是ABC（根节点排最先，然后同级先左后右）；中序顺序是BAC(先左后根最后右）；后序顺序是BCA（先左后右最后根）。

怎么正确理解二叉树的遍历

遍历

 extension BinaryNode {
    
    // 中序
    func traverseInOrder(visit: (Element) -> Void) {
        leftChild?.traverseInOrder(visit: visit)
        visit(value)
        rightChild?.traverseInOrder(visit: visit)
    }
    
    // 前序
    func traversePreOrder(visit: (Element) -> Void) {
        visit(value)
        leftChild?.traversePreOrder(visit: visit)
        rightChild?.traversePreOrder(visit: visit)
    }
    
    // 后续
    func traversePostOrder(visit: (Element) -> Void) {
        leftChild?.traversePostOrder(visit: visit)
        rightChild?.traversePostOrder(visit: visit)
        visit(value)
    }
}

遍历节点使用的依然是递归的思想, 采用入栈依次递归调用自己, 采用出栈来结束递归, swift 给我们提供了一个很好的数据类型, 可选类型, 可选类型有值, 则执行递归操作, 可选对象无值, 则结束递归.

以中序遍历为例, traverseInOrder方法为BinaryNode的扩展, 调用者为structureTree() 是我们自己构建的一个二叉树

structureTree().traverseInOrder { 
     print($0) 
}

structureTree() 返回的节点为根节点, 从根节点开始开始寻找下面的节点, 如果打上断点, 查看堆栈调用过程, 如下图所示

屏幕快照 2018-12-19 下午3.04.27.png

traverseInOrder(visit:)被压入栈里三次, 因为我们有三个节点7, 1, 0, 当0被压入的栈的时候, 此时0节点的leftChild为空, 不再被压入栈, 接下来执行visit(value)出栈.
执行过程为节点存在左节点时, 左节点依次入栈, 直到不存在左节点为止, 左节点开始出栈, 左节点出栈之后, 开始查找右节点, 有, 入栈, 否则出栈, 依次类推.
感觉swift遍历二叉树代码量挺少, 就是理解起来费劲. 可以先以一个根节点, 两个子节点来理解这个遍历的方法, 无论有多少个节点, 都是在这三个节点的基础上扩展的.