数据结构中的树

在自然界中，树有一个很明显的特点是枝干会分叉，一个枝干会分叉成多个小枝干，小枝干还会继续分叉更小的枝干。不管哪个小枝干，循着方向总能找到上一级枝干，最终会到达树根。在我们的生活中，处处都充满了树的结构，很多事物的关系可以用树的结构来表示。

• 家族树： 家族人员可以用多种层次化的方式表示，图(a)的张老头有三个儿子，二儿子余杆也有两个儿子金根和银根。图(b)则是另一个视角，盼娣的父母对应着两人余校和梅文化，父亲余校上面也有父母两人。

• 企业组织架构： 学校、政府和企业的员工组织方式也是层次化的树状结构，下图中的总经理可以视为根部，下属五个部门，而各个部门下属多个分部，分部下面可能存在多个小部门或生产线，每条生产线下面还会存在多个员工。

• 文件的目录结构： 计算机中通常以文件夹或目录的方式组织文件，每个文件夹包含若干子文件夹和文件，而子文件夹下面还可以有多个文件夹。

像栈、队列、数组这些线性结构组织数据的方式是一个接着一个的，除了线性方式之外，还需要按层次化（hierarchical） 或非线性化（nonlinear）的方式表示数据。数据按层来划分，数据项出现在不同的层次上。树便是这样的数据结构，这种结构让组织数据的方式变得丰富多彩。

术语

不同于自然界中的树，数据结构中的树是倒过来的，根在上，枝叶在下。树（tree）由节点（node）和边（edge）组成，节点通过边连接，它也表示节点间的关系。节点根据边连接的排列不同，表明它们位于不同的层(level)，位于最顶层的节点称为根(root)，一棵树最多只有一个根节点。

下一层的节点是其上一层的子（children）节点，或称孩子节点。拥有子节点的是父（parent）节点，也称为父母节点。同一个父节点的子节点，称它们为兄弟。父节之上的所有节点称为祖先（ancestor），祖先节点的子节点以下所有节点称为后代（descendant）。

上图中，A 是所有节点的祖先，它们都是 A 的后代。位于最后一层的节点没有子节点，像这样的节点称为叶（leaf）节点，或叶子节点，其它有孩子的节点称为非叶（nonleaf）节点或内部（interior node）节点。根节点没有父节点，其它所有节点都有一个父节点，且只有一个。

层和深度都是从根节点往下开始数的，并且层从1开始，深度和高度从0开始。由下往上数，树的高度指的是最高子树的高度。从根节点开始，沿着节点的边可以到达任意节点，而且根节点到任何节点的路径都是唯一的，其中路径的长度是构成它的边的数量。上图中，通过节点 A、B、F 和 N，的路径长度为3，总共经过3条边，四个节点。

二叉树

如果树中的每个节点最多只有两个子节点，这样的树称为二叉树（binary tree），二叉树的所有节点最多只能有两个子节点，分别称为左子结点和右子节点，或者左子树和右子树。

下图的三棵都是二叉树。(a)中，N、P 和 F 是左子结点，P、O 和 G 是右子节点。左右子树是对于某个节点而言的，根节点有两棵子树，左子树的根是 F，右子树的根是 G。二叉树的所有子树都是二叉树。

• 满二叉树：如果一棵二叉树的所有叶节点都在同一层，并且每个父节点都有两个子节点，这样的二叉树称为满二叉树，上图(a)是一棵满二叉树。
• 完全二叉树：如果一棵二叉树除了最后一层之外，其它所有层都包含尽可能多节点，而且最后一层的节点从左边排满，右边可以不满，像上图(b)，这样的树称为完全二叉树。
• 即不满也不完全二叉树：上图(c)中，非叶子节点缺失了，是不满也不完全二叉树。

根据二叉树节点中的数据特点以及用途，二叉树可以分成多种类型。

堆

如果二叉树的父节点始终大于或小于子节点，这样的二叉树称为堆（Heap），也称为二叉堆（Binary Heap），如果不特别说明，堆一般是指二叉堆。如果父节点大于子节点，称为大顶堆（Max Heap），如果父节点小于子节点，称为小顶堆（Min Heap），堆这种特性可以用来实现优先队列，就以大顶堆来说，根节点始终是最大的，这对排列任务优先级很有用，因为根节点的优先级始终是最高的。

堆还可以实现排序，比如大顶堆，把顶部最大的元素拿走，堆重新恢复平衡后，顶部的元素就是所有元素中第二大的，利用这一特性可以实现数组升序或降序排列。

关于堆的更多内容，我们会在这篇文章中详细讨论。

二叉查找树

如果二叉树的左子节点始终小于父节点，父节点始终小于或等于右子节点，这样的二叉树称为二叉查找树（Binary Search Tree）。

分布在二叉查找树节点中的数据彼此间是有序的，类似于有序的线性表，可以用于需要快速查找数据的场景。

关于二叉查找树的更多内容，我们会在这篇文章中详细讨论。

表达式树

二叉树可以用来表示一个二元运算的代数表达式，运算符号 +、-、×、/ 和运算数，其中根节点保存运算符，其它节点保存运算符或运算数，这样的树称为表达式树（Expression Tree）。

用不同的方式遍历（本文后面对树的遍历有讨论）二叉表达式树会得到不同的结果。比如上图的二叉表达式树，应用中序遍历会得到符合我们日常书写习惯的表达式 (a+(b×c))\+(((d×e)+f)×g)，也称为中缀表达式。当使用前序遍历，会得到前缀表达式 +a×bc×\+×defg，使用后序遍历得到后缀表达式 abc×+de×f+g×。前缀表达式、中缀表达式、后缀表达式只是对表达式的不同记法，区别在于运算符相对于运算数的位置。前缀表达式的运算符位于运算数的前面，后缀表达式的运算符位于运算数的后面，中缀表达式的运算符位于运算数的中间。

中缀表达式是一种通用的算术或逻辑公式表示方法，运算符以中缀形式处于运算数的中间，是人们常用的算术表示方法。虽然人的大脑很容易理解与分析中缀表达式，但对计算机来说前缀和后缀表达式才是简单的，中缀表达式却很复杂。因此计算表达式的值时，通常需要先将中缀表达式转换为前缀或后缀表达式，然后再进行求值。

前缀表达式和后缀表达式的求值方式是类似的，以前缀表达式 ++a×bc×+×defg 为例，首先从右往左扫描表达式放入栈，如果是运算数直接入栈，遇上运算符就弹出栈顶两个运算数并运算，然后将运算结果作为运算数再放入栈中。重复这个过程直到表达式最左端，最后得出的结果即为表达式的结果。后缀表达式同理，区别是从左往右扫描。

中缀表达式可以转换成前缀或后缀表达式，以 1+(2+3)×4-5 转换为前缀表达式为例，转换过程分成三步完成。

1. 按照运算符优先级对所有运算单元加括号： 加了括号后，表达式变成 ((1+((2+3)×4))-5)。

2. 将运算符移动到对应括号的外面： 如果是前缀表达式，把运算符移至相应括号层的前面：-(+(1×(+(23)4))5)。 如果是后缀表达式，运算符移至相应括号层的后面：((1((23)+4)×)+5)-。

3. 去掉所有括号： 去掉括号后，前缀表达式得到：-+1×+2345。后缀表达式得到：123+4×+5-。

决策树

一个问题可以有有限个答案，可以是真或假、是或否，或者多选，如果一棵树的非叶子节点是这样的问题，那么这样的树称为决策树（Decision tree）。一般来说，决策树会是一棵多叉树，它能提供多个选项作为答案。决策树的问题从根开始，每一个分支都是问题的答案，子节点对应着另一个问题或者结论，如果子节点是结论，那么这个子节点就是叶结点。某些择偶标准可以当成一个决策过程，也可以用决策树表示：

决策过程从根开始，需要回答当前的问题才能进入下一个决策环节。当进入了叶节点，整个决策过程就结束了。

多叉树

如果一棵树中每个节点最多可以有 n 子节点，这样的树称为多叉树*（Multiway Tree）或者n叉树（n-ary tree），也叫一般树（general tree）。相比二叉树，多叉树有更强的表达能力，可以表示更复杂的关系。

B树

B树（B-Tree）是一种自平衡的多叉树结构，专门设计用在需要高效存储和检索大量数据的场景，比如数据库系统和磁盘的文件系统。B树的所有叶节点在同一层，而且所有内部节点的子节点数量都维持在一个预定的范围之内。这种结构让B树在保持平衡的同时，确保了数据的有序性，让查找、插入、删除变得很高效。

关于B树的更多内容，我们会在这篇文章中详细讨论。

博弈树

博弈树（Game Tree）是一种多叉树数据结构，用来描述策略性质的博弈过程，可以表示所有可能的决策和结果，从而帮助决策者（或算法）分析和选择最佳策略，在人工智能、特别是游戏人工智能中广泛应用。

比如说井字游戏，它棋局其实是一棵博弈树。游戏有两个玩家，一个画圈一个画叉，轮流分别在3×3的格子中画自己的符号，不论横、直、斜，谁能最先将自己的符号连成一条直线就视为胜利，如果都画满了但还没分出胜负则是和局。这个游戏能画图案的地方只有9个，只有765个可能局面，26830个棋局。如果将对称的视为不同棋局，则有255168个棋局。井字游戏的棋局可能的情形是有限的，以现在的计算机性能，只需要一瞬间就能列出它所有可能的棋局。

博弈树在人工智能的应用中相当重要，若要查找某个博弈中最佳步法的一个方式，可以用极小化极大算法和 Alpha-Beta 剪枝等技术，很快就能找出井字游戏的最佳步法。而像围棋这类大型的博弈游戏，以现在的计算机性能，没办法很快列出完整的博弈树，因此，对这类游戏通常会只搜索部分博弈树。一般来说，搜索的层数越多，能走出较佳步法的机率也越高。典型的博弈树通常会限制层数，还会剔除一些规则不允许的情况。

语法分析树

语法分析树（Syntax Analysis Tree，AST）用来表示语法结构，在编译器中很有用。编译器在生成中间代码之前，需要进行语法分析，编译器使用 AST 来检查程序代码的语法。为了囊括所有表达式，AST 必须是一棵多叉树。比如这段赋值表达式代码：a[index] = 3 + 6，总共有8个记号：

从这段表达式，我们可以构建出这样一棵分析树：

树的遍历

对于线性结构来说，我们很好定义某个元素的上一个元素和下一个元素，或者它前面的元素和后面的元素。遍历方式也很直观，可以按照从前往后的顺序遍历，也可以从后往前遍历。树是一种抽象的数据类型，很难说谁在谁的前面，哪个又在哪个的后面，可以这么说，树的节点有多少种排列方式就有多少种遍历方式，不过这其中大多数遍历方式并没有什么意义。基于各种树的特点，有几种遍历树的实用方式。

遍历二叉树

有两种思路可以遍历二叉树，先纵向后横向，或者先横向再纵向。先纵后横也叫深度优先（depth-first）遍历，先横后纵也叫宽度优先（breadth-first）遍历。

深度优先

根据访问左子树右子树和节点本身的不同顺序，深度优先也可分成三种不同的遍历方式。按照惯例，会先访问左边再访问右边。

• 前序遍历：

  1. 访问节点本身。
  2. 访问左子树。
  3. 访问右子树。

[+]
这种方式先完全探明一个子树再遍历其它，从上往下的节点只访问了左子结点，等探明子树逐层往上之后再访问右子节点。

中序遍历

1. 访问左子树。
2. 访问节点本身。
3. 访问右子树。

[+]
这种方式也是从上往下探明最底层的节点，但这时不会访问沿途的左子结点，而是先访问最底下的左子结点，然后是父节点，再到右子节点。这棵左子树访问完后，以这个过程不断访问父节点和右子节点。

后序遍历

1. 访问左子树。
2. 访问右子树。
3. 访问节点本身。

[+]
这种方式和也是从左子结点开始，先探明最左边的子树，访问了最左子树的左子结点后，接着到右子节点然后才是父节点。此时左子树访问完，再循环访问右子节点和父节点这个过程。

宽度优先

宽度优先即逐层遍历，从根节点一层一层往下遍历，因此也叫层序遍历

层序遍历

二叉树任意节点的子树也是二叉树，是一种递归的数据结构，深度优先的遍历使用递归是很自然的选择。层序遍历需要借助队列来实现。

use std::collections::LinkedList;

struct BinaryTree<T: Ord> {
    root: Option<Box<Node<T>>>,
}

struct Node<T> {
    v: T,
    left: Option<Box<Node<T>>>,
    right: Option<Box<Node<T>>>,
}

impl<T: Ord> BinaryTree<T> {

    /// 前序遍历
    fn preorder(&self) {
        fn preorder<V>(root: Option<&Box<Node<V>>>) {
            if let Some(node) = root {
                // 在这里访问节点
                preorder(node.left.as_ref());
                preorder(node.right.as_ref());
            }
        }
        preorder(self.root.as_ref());
    }

    /// 中序遍历
    fn inorder(&self) {
        fn inorder<V>(root: Option<&Box<Node<V>>>) {
            if let Some(node) = root {
                inorder(node.left.as_ref());
                // 在这里访问节点
                inorder(node.right.as_ref());
            }
        }
        inorder(self.root.as_ref());
    }

    /// 后序遍历
    fn postorder(&self) {
        fn postorder<V>(root: Option<&Box<Node<V>>>) {
            if let Some(node) = root {
                postorder(node.left.as_ref());
                postorder(node.right.as_ref());
                // 在这里访问节点
            }
        }
        postorder(self.root.as_ref());
    }

    /// 层序遍历，从根节点开始逐层往下，每一层从左往右遍历。
    /// 借助队列来实现。在循环中，访问当前节点时，将下一层的子节点也从左往右添加到队列，
    /// 下一次循环会按上一层的添加顺序从左往右弹出。
    fn level_order(&self) {
        let mut queue = LinkedList::new();
        if let Some(root) = &self.root {
            queue.push_back(root);
            while !queue.is_empty() {
                let node = queue.pop_front().unwrap();
                // 在这里访问节点
                if let Some(left) = &node.left {
                    queue.push_back(left);
                }
                if let Some(right) = &node.right {
                    queue.push_back(right);
                }
            }
        }
    }
}

遍历多叉树

对于多叉树，可以使用前序遍历、后序遍历和层序遍历。之所以不考虑中序遍历，是因为访问完左子树再访问父节点，你会发现此时的中序遍历并不好定义，因为我们无法确定怎样才算是访问完左子树。多叉树与二叉树的层序遍历并没有本质区别。

用二叉树表示多叉树

多叉树每个节点的子节点数量并不固定，操作多叉树的算法会比二叉树复杂。树在逻辑上是按层来表示的，树也是逻辑结构。用二叉树来表示多叉树，有时候可以简化问题。

下图中，(b)从根节点开始，除了第一个子节点，断开所有其它子节点的连接，然后将所有兄弟节点依次连起来。对所有子节点和后代节点执行同样的操作，就能得到一棵二叉树了。

树的结构变了，遍历的结果就未必相同了，我们来看看用各种遍历方式会得到怎样的结果。

• 多叉树的遍历结果：

  前序遍历：A B F G C H L M N I J D K E
  后序遍历：F G B L M N H I J C K D E A
  层序遍历：A B C D E F G H I J K L M N
  

• 二叉树的遍历结果：

  前序遍历：A B F G C H L M N I J D K E
  后序遍历：G F N M L J I H K E D C B A
  层序遍历：A B F C G H D L I K E M J N
  中序遍历：F G B L M N H I J C K D E A
  

对比之后你会发现，还是存在一些共性的。他们的前序遍历结果是相同的，而多叉树的后序遍历和二叉树的中序遍历结果也是相同的。唯有多叉树的层序遍历在二叉树中还没有与之对应的遍历方法。

用数组表示树

既然树是逻辑结构，我们也可以用一维的数组，按某种逻辑表示二维的树。在这之前，我们需要确定要多大的数组。

对于一棵 n 叉的满树来说，第0层的节点数是 $n^0$，第1层是 $n^1$，第2层是 $n^2$，第 $h$ 层的节点数是 $n^h$，整棵树的总节点数 $N$ 是：$N = 1+n+n^2+n^3+⋯+n^h$，这是一个等比数列求和问题，不难得出 $N = \frac {n^{h+1} - 1} {n-1}$。对于一棵高度 h 的 n 叉满树来说，需要的数组长度是：$\frac {n^{h+1} - 1} {n-1}$。

接下来，我们以一棵满的二叉树为例，从根开始，逐层往下，每一层从左往右映射到数组中。

完全二叉树的右侧叶结点会不完整，相应地，数组尾部留空处理。

如果是非满树和即不满也不完全的树，则相应位置的节点对应的数组位置留空。