树形结构是指数据元素之间存在“一对多”（One-to-Many）的树形对应关系而形成的一类数据结构，树形结构是一类非常重要的非线性数据结构。一个树是由多个节点组成，每个节点又具有多个与其关联的子节点。现实中的很多事物的组织结构都可以用树来表示，例如一个公司的组织结构图，网页的DOM树。

树形结构一般都具有以下几个共同的特点：

1. 只有一个根节点。根节点没有父节点。
2. 除了根节点，所有的节点都只有一个父节点，不存在一个节点与两个或以上父节点存在关联的情况。
3. 无环。以任意一个节点作为起始节点，都不存在任何能够返回该起始节点的路径。

常用术语

• 节点，树中的数据元素，由数据项和数据元素之间的关联关系组成。
• 度，度主要表示子树的个数，根据观察位置不同，有不同的定义。
  • 节点的度，表示节点所拥有子树的数量。
  • 树的度，由树中所有节点的度的最大值决定。
• 子节点，也称为孩子（child），节点所拥有的子树的根节点，称为该节点的子节点。
• 父节点，如果一个节点拥有子树，那么该节点就被成为子树根节点的父节点（parent）。
• 兄弟节点，拥有相同父节点的节点成为兄弟节点。
• 子孙节点，节点所拥有的子树上的节点。
• 叶节点，没有子节点的节点。
• 内节点，至少拥有一个子节点的节点。
• 边，两个节点中间的连接。
• 路径，从节点到子孙节点过程中所经历的边和节点组成的序列。
• 层级，从根节点到树中某一个节点所经历路径上的分支数称为这个节点的层级。根节点是0级，根的子节点为1级。
• 高度，也可以称为深度，指树中的层的数量。
• 无序树，树中的任意一个节点与其子节点之间的次序没有紧要关联的树。
• 有序树，树中任意一个节点与其子节点之间有严格排列次序的树。二叉树是有序树，因为其左孩子和右孩子都有确切定义。

常见树的类型

• 二叉查找树。
• 自平衡二叉查找树。
• B树。
• 字典树。
• 空间数据分割树。

二叉树

二叉树（Binary Tree）是指树中的所有节点的度都不大于2的树，也就是说，二叉树中的所有节点最多只有2个子节点。二叉树的每个节点有左树和右树之分，而节点的左树和右树同样也是二叉树。

二叉树有几个特殊的类型：

• 满二叉树，二叉树中只包含度为0和2的节点，并且度为0的节点都在同一层上，这样的二叉树就被称为满二叉树。
• 完全二叉树，深度为k，有n个节点的二叉树，除第k层以外，其他各层的节点数都达到最大数量，第k层只有叶子节点，且第k层的叶子节点是从左至右依次排布，即为完全二叉树。完全二叉树的特点是叶子节点只可能出现在层级最大的两层上。
• 扩充二叉树，对已有二叉树进行扩充，直到所有的节点都变为度数为2的分支节点。
• 平衡二叉树，树的任意节点的左右两个子树的高度差的绝对值不超过1。

完全二叉树可以存放在一位数组中，堆排序所使用的数据结构也是完全二叉树。以下分别是完全二叉树和满二叉树、平衡二叉树的示意。

二叉树插图.png

二叉树的构建

要在代码中构建一个二叉树，首先就要从构建二叉树所用的数据结构开始。要构建一个二叉树，最简单的方法是构建一个节点类。

class Node<T>(val value: T) {
    var left: Node<T>? = null
    var right: Node<T>? = null
    var parent: Node<T>? = null

    fun hasLeftChild(): Boolean = this.left != null
    fun hasRightChild(): Boolean = this.right != null
    fun hasParent(): Boolean = this.parent != null
    fun isLeaf(): Boolean = this.left == null && this.right == null

    fun attachLeftChild(child: Node<T>) {
        this.left = child
        child.parent = this
    }

    fun attachRightChild(child: Node<T>) {
        this.right = child
        child.parent = this
    }
}

这样的一个节点类是最简单的二叉树节点实现，它能够保存自己的值，也可以持有左孩子和右孩子，还可以回溯自己的父级节点。有了这个节点类，接下来就可以来用它构造一棵二叉树了。

二叉树的遍历

二叉树的遍历是指不重复的访问二叉树中的所有节点，二叉树的遍历最常用的方法是采用递归。因为二叉树是在深度和广度两个方向上延伸的，所以对于二叉树的遍历就有深度优先和广度优先两种遍历策略。

深度优先遍历

深度优先遍历就是先沿着层级增加的路径，按一定顺序逐一访问深层级的节点。根据二叉树中每个根节点、左孩子和右孩子的访问顺序不同，二叉树的深度优先遍历可以分为前序遍历、中序遍历和后序遍历。

前序遍历

前序遍历是指使用先访问根节点，再访问左子树，最后访问右子树的顺序。以下是前序遍历方法。

fun Node<T>.preOrderTraversal(process: (T) -> Any) {
    process.invoke(this.value)
    this.left?.preOrderTraversal(process)
    this.right?.preOrderTraversal(process)
}

中序遍历

中序遍历是指使用先访问左子树，再访问根节点，最后访问右子树的顺序。以下是中序遍历方法。

fun Node<T>.inOrderTraversal(process: (T) -> Any) {
    this.left?.preOrderTraversal(process)
    process.invoke(this.value)
    this.right?.preOrderTraversal(process)
}

后序遍历

后序遍历是指使用先访问左子树，再访问右子树，最后访问根节点的顺序。以下是后序遍历方法。

fun Node<T>.postOrderTraversal(process: (T) -> Any) {
    this.left?.preOrderTraversal(process)
    this.right?.preOrderTraversal(process)
    process.invoke(this.value)
}

不使用递归的遍历方法

在使用递归进行二叉树遍历的时候，递归的特点使得我们可以以非常清晰的条理完成整棵二叉树的遍历，但是递归的缺点就是在二叉树深度较大的时候，会非常消耗系统资源。所以在追求性能或者比较均衡的实现的时候，可以借助栈来实现不使用递归的遍历。以下以前序遍历为例来展示不使用递归的二叉树遍历方法。

fun Node<T>.preOrderTraversal(process: (T) -> Any) {
    val queue = mutableListOf<Node<T>>()
    queue.add(this)
    while (queue.size > 0) {
        val pointer = queue.removeLast()
        process.invoke(pointer.value)
        pointer.right?.let(queue::add)
        pointer.left?.let(queue::add)
    }
}

栈是一个FILO的结构，所以在完成前序遍历的时候，需要先将最后遍历的右子树压栈。如果要使用FIFO结构的队列，则可以直接使用递归遍历中的顺序将遍历任务逐步排入。

这里使用一个普通的List模拟了一个栈，对于栈这种数据结构，只需要注意其操作，并不必要强调其实现名称。

广度优先遍历

相比深度优先遍历，广度优先遍历就比较容易理解了。广度优先遍历实际上就是逐层扫描树，一层一层的遍历，直到最大深度。广度优先遍历一般都采用一个队列来完成遍历任务，递归在广度优先中并不好用。使用队列来实现广度优先遍历的原理是将每一个节点的左孩子和右孩子依次排入队列，这样在进行处理时就会首先计算一层的节点。以下依旧提供一个简单的示例。

fun Node<T>.breadthFirstTraversal(process: (T) -> Any) {
    val queue = mutableListOf<Node<T>>()
    queue.add(this)
    while (queue.size > 0) {
        val pointer = queue.removeFirst()
        process.invoke(pointer.value)
        pointer.left?.let { queue.add(it) }
        pointer.right?.let { queue.add(it) }
    }
}