数据结构与算法_05_树

本文介绍一种经典的数据结构——树。

1. 树理论基础

前面的数组、队列等数据结构，是线性结构，即元素之间的前后关系是一对一的，一个元素只有一个前驱元素、一个后继元素。而树则是非线性结构，一个元素只有一个前驱元素，但是可以有多个后继元素，即一对多的关系。

可以看到，树本身就是一个递归的定义。

1.1 基本术语

• 根节点、节点、前驱节点（双亲节点）、后继节点（孩子节点）、叶子节点（终端节点）、内部节点（非终端节点，根节点除外）、兄弟节点
• 节点的度：节点拥有的子树（子节点）个数
• 树的度：树内各节点的度的最大值
• 节点的祖先：从根到该节点所经分支上的所有节点。
• 节点的子孙：以该节点为根的子树中的任一节点。
• 层次：根节点为第一层，孩子节点为第二层，以此类推。
• 树的深度（树的高度）：树中节点的最大层次。
• 有序树：树中节点的各子树从左到右有次序。即规定左边为第一个孩子，如果节点子树互换位置，则表明这是两棵不同的树。
• 无序树：树中的子树可以交换位置，仍然看做是同一棵树。
• 森林：多棵（也可以是一棵）互不相交的树的集合。

1.2 二叉树

树作为一种数据结构，用来存储数据，而数据则是用来存取的。作为运算，上面的树实际上是很难找到规律的，那么为了方便计算，出现了一个“特殊的树”，即树中每个节点最多有两个子节点（二叉树）。同时如果树中每个节点都有两个子节点，则被称为完全二叉树、满二叉树等等。另外，子节点有左右之分，即左子树和右子树。

• 二叉树的结构最简单，规律性最强。
• 可以证明，所有的树都能转为唯一对应的二叉树，不失一般性。

二叉树在树结构的应用中起着非常重要的作用，因为对二叉的许多操作算法简单，而任何树都可以与二叉树相互转换，这样就解决了树的存储结构及其运算中存在的复杂性。

这里注意一下，二叉树不是树，也不是树的一种特殊情况。虽然二叉树和有序树比较像，但是二叉树即使有一个子树也会区分左子树还是右子树，而有序树只有一个节点时，则不会区分左右。

二叉树有以下五种基本形态

1.3 二叉树抽象数据类型定义

• 数据对象

  即存储的数据，比如存储整数、存储引用数据类型等等

• 数据关系

  定义左右节点

• 基本操作

  比如先序遍历、中序遍历、后续遍历等等。

1.4 满二叉树

二叉树的每一层都是满的，即节点数达到了最大，即2^k - 1，叶子节点全部在最底层。

1.5 完全二叉树

和满二叉树类似，只不过，不一定非要有两个节点，但是已有的节点必须是从左到右依次占满节点位置的。即如果缺少节点，则一定是右侧子节点空缺。

• 叶子节点只可能分布在层次最大的两层上。
• 对任意节点，如果其右子树的最大层次为i，那么其左子树的最大层次必为i或者i+1。

即满二叉树一定是完全二叉树。

1.6 二叉树的存储结构

和前面的数据结构一样，二叉树的存储结构也分为顺序存储结构和链式存储结构。

• 顺序存储结构（按照完全二叉树进行存储）

  即将二叉树的节点按照满二叉树的节点编号作为数组的下标索引存储。而根据完全二叉树的性质，下标为i的节点的左右两个子节点分别是2i和2i+1，这样就可以实现上下层之间的存取了。注意，这样对于非完全二叉树来说，就会出现空缺位置，但是这样做是无法避免的，为了方便存取，只能这样做。因此适合满二叉树和完全二叉树。

• 链式存储结构

  和线性链表一样，对于二叉树，至少需要两个指针指向左右孩子节点（被称为二叉链表）。（如果需要逆向指向双亲节点，还需要加一个指针，即三叉链表）

1.7 遍历二叉树

遍历的含义：顺着某一条搜索路径寻访二叉树中的节点，使得每个节点均被访问一次，而且仅被访问一次（又称周游）。访问的含义比较广，简单地说就是存取数据以及对数据进行运算，但是不能破坏数据结构。

遍历的目的就是将非线性的数据结构按照某个线性顺序依次访问节点。主要的遍历顺序有：

• 先序（根）遍历——根左右
• 中序（根）遍历——左根右
• 后序（根）遍历——左右根

上图中是采用递归的方式来遍历的，也有非递归的方式。我们知道，树的遍历分为左子树、根、右子树三部分，无论怎么遍历，左右子树都是分开遍历的，那么此时，就需要保存右子树（因为左子树是先访问的），但是保存右子树是没必要的，因为可以通过根节点来访问到右子树，所以需要保存根节点。另外，根据访问顺序可以看到，各个根节点是“先进后出”的，所以采用栈数据结构来存储根节点。以先序遍历为例，如下所示：

1. 访问根节点，并将其入栈。
2. 访问根节点的左子树，同样将该子树的根节点入栈。
3. 重复2步骤，直到当前节点的左子树为空，将栈中的根节点取出（访问节点），获得右子树。
4. 重复2、3步骤，直到栈为空。

除了上面的先序中序和后序遍历，还有一种层次遍历方法，即逐层遍历二叉树。这种方法实现比较简单，采用队列：

• 将根节点存入队列，
• 出队，访问节点，并将当前元素的左右节点放入队列，
• 继续出队，入队，直到队列为空。

1.8 线索二叉树

我们知道，当用二叉链表作为二叉树的存储结构时，可以很方便地找到某个节点的左右孩子。但是一般情况下，无法直接找到该节点在某种遍历序列中的前驱和后继节点。解决方法有如下几种：

• 遍历到该节点，找到其前驱和后继（费时）
• 增设前驱和后继（费空间）
• 利用二叉链表中的空指针域（我们知道，n个节点共有n+1个指针域为空）。

如果某个节点的左孩子为空，则将空的左孩子指针域修改为指向其前驱；如果某节点的右孩子为空，则将空的右孩子指针域修改为指向其后继。这种改变指向的指针称为“线索”，加上了线索的二叉树就被称为线索二叉树。

既然有前驱和后继了，就说明有了遍历顺序，那么对二叉树按照某种遍历次序使其变为线索二叉树的过程叫线索化。例子如下所示：

但是这样线索化之后，实际上就没办法区分某个指针到底指向的是其孩子节点还是其前驱和后继了。所以此时在节点中增设两个标志域ltag和rtag，约定如下：

• ltag=0，lchild指向该节点的左孩子
• ltag=1，lchild指向该节点的前驱
• rtag=0，rchild指向该节点的右孩子
• rtag=1，rchild指向该节点的后继

1.9 二叉搜索树

注意，不是完全二叉树。二叉搜索树指的是节点中的数值，左节点的值小于根节点的值，右节点的值大于根节点的值。这样在查找的时候，就相当于二分查找了。

1.10 平衡二叉搜索树

指的是在二叉搜索树的基础上，左右子树的高度差值不超过1。

2. 树经典题目

树的定义如下（Java）：

public class BinaryTreeNode {
    int value;
    BinaryTreeNode lchild;
    BinaryTreeNode rchild;

    public BinaryTreeNode() {}

    public BinaryTreeNode(int value) {
        this.value = value;
    }

    public BinaryTreeNode(int value, BinaryTreeNode lchild, BinaryTreeNode rchild) {
        this.value = value;
        this.lchild = lchild;
        this.rchild = rchild;
    }
}

2.1 二叉树的递归遍历

下面是三种遍历方式的递归实现

public class Traversal {

    public static void preOrderTraversal(BinaryTreeNode T) {

        if(T != null){
            System.out.println(T.value);
            preOrderTraversal(T.lchild);
            preOrderTraversal(T.rchild);
        }

    }

    public static void midOrderTraversal(BinaryTreeNode T) {
        if(T != null){
            midOrderTraversal(T.lchild);
            System.out.println(T.value);
            midOrderTraversal(T.rchild);
        }
    }

    public static void posOrderTraversal(BinaryTreeNode T) {
        if(T != null){
            posOrderTraversal(T.lchild);
            posOrderTraversal(T.rchild);
            System.out.println(T.value);
        }
    }

    public static void main(String[] args) {

        BinaryTreeNode btn1 = new BinaryTreeNode(7);
        BinaryTreeNode btn2 = new BinaryTreeNode(5, btn1, null);

        BinaryTreeNode btn3 = new BinaryTreeNode(4);

        BinaryTreeNode btn4 = new BinaryTreeNode(2, btn3, btn2);

        BinaryTreeNode btn5 = new BinaryTreeNode(6);
        BinaryTreeNode btn6 = new BinaryTreeNode(3, null, btn5);

        // final tree
        BinaryTreeNode btn7 = new BinaryTreeNode(1, btn4, btn6);

        // 1 2 4 5 7 3 6
        preOrderTraversal(btn7);

        System.out.println("===========");

        // 4 2 7 5 1 3 6
        midOrderTraversal(btn7);

        System.out.println("===========");

        // 5 7 5 2 6 3 1
        posOrderTraversal(btn7);

    }
}

2.2 二叉树的迭代遍历（非递归遍历）

前面提到过，有非递归的实现方式，即将根节点保存起来，方便后续取出访问其右节点。参考博客中的LeetCode标签中对应的题目。

2.3 二叉树的层次遍历

层序遍历就是逐层遍历二叉树，可以采用队列来实现。参考博客中的LeetCode标签中对应的题目。

3. 备注

部分参考代码随想录 (programmercarl.com)。数据结构之树_lishinho的博客-CSDN博客_数据结构树。数据结构中”树”的全面讲解 - 知乎 (zhihu.com)。B站《青岛大学数据结构与算法基础》