二叉树的原理与实现

1 二叉树的定义

二叉树 (Binary Tree) 是由 $n$ ($n \geq 0$) 个节点组成的有限集合,当 $n=0$ 时称为空二叉树;$n>0$ 的二叉树由一个根节点和两棵互不相交的、分别称为左子树和右子树的子二叉树构成。二叉树也是递归定义的。在 中定义的度、层次等术语,同样适用于二叉树。

二叉树有 5 种基本形态,如下图所示:

二叉树的 5 种基本形态

2 二叉树的性质

  • 性质 1: 设根节点的层次为 1,二叉树第 $i$ 层最多有 $2^{i-1}$ ($i \geq 1$) 个节点

    证明:(归纳法)

    1. 根是 $i=1$ 层唯一的节点,故 $2^{i-1} = 2^{0} = 1$,命题成立;
    2. 当 $i>1$ 时,带入公式可得 $i-1$ 层最多有 $2^{i-2}$ 个节点,由于二叉树中每个节点的度最多为 2,所以第 $i$ 层最多有 $2 \times 2^{i-2}=2^{i-1}$ 个节点,命题成立。
  • 性质 2: 在高度为 $h$ 的二叉树中,最多有 $2^{h}-1$ 个节点 ($h>0$)。

    证明:由性质 1 可知,高度为 $h$ 的二叉树中,节点数最多为 $\displaystyle\sum_{i = 1}^{h}2^{i-1}=2^k-1$。

  • 性质 3:设一棵二叉树的叶子(度为 0)节点数为 $n_0$,度为 2 的节点数为 $n_2$,则 $n_0=n_2+1$。

    证明:

    1. 设二叉树节点数为 $n$,度为 1 的节点数为 $n_1$,则有 $n=n_0+n_1+n_2$。
    2. 因为度为 1 的节点只有一个孩子,度为 2 的节点有两个孩子,叶子节点没有孩子,根节点不是任何节点的孩子,所以 $n=0\times n_0 + 1 \times n_1 + 2 \times n_2 +1$。

    综合上述两式,可得 $n_0=n_2+1$。

  • 性质 4:一颗具有 $n$ 个节点的完全二叉树,其高度 $h=[\log_2n]+1$。

    满二叉树和完全二叉树

    一棵高度为 $h$ 的满二叉树 (Full Binary Tree) 是具有 $2^h-1$ ($h \geq 0$) 个节点的二叉树。

    从定义知,满二叉树中每一层的节点数目都达到最大值。对满二叉树的节点进行连续编号,约定根节点的序号为 0,从根节点开始,自上而下,每层自左至右编号,如下中的树 (a) 所示:

    满二叉树与非满二叉树

    一棵具有 $n$ 个节点高度为 $h$ 的二叉树,如果它的每个节点都与高度为 $h$ 的满二叉树中序号为 $0$ ~ $n-1$ 的节点一一对应,则称这棵二叉树为完全二叉树 (Complete Binary Tree),如上图中的树 (b) 所示。

    满二叉树是完全二叉树,而完全二叉树不一定是满二叉树。完全二叉树的第 1 ~ $h-1$ 层是满二叉树,第 $h$ 层不强求满,并且该层所有节点都必须集中在该层左边的若干位置上。上图中的树 (c) 就不是完全二叉树。

    证明:对于一棵有 $n$ 个节点高度为 $h$ 的完全二叉树,有 $2^{h-1}-1 < n \leq 2^h-1$,对不等式移项并求对数,有 $h-1 < \log_2{(n+1)} \leq h$,由于二叉树的高度 $h$ 只能是整数,所以取 $h=[\log_2n]+1$。

  • 性质 5:一棵具有 $n$ 个节点的完全二叉树,对序号为 $i$ ($0 \leq i < n$) 的节点,有:
    • 若 $i=0$,则 $i$ 为根节点,无父母节点;若 $i>0$,则 $i$ 的父母节点序号为 $[(i-1) / 2]$。
    • 若 $2i+1<n$,则 $i$ 的左孩子节点序号为 $2i+1$;否则 $i$ 无左孩子。
    • 若 $2i+2<n$,则 $i$ 的右孩子节点序号为 $2i+2$;否则 $i$ 无右孩子。

3 二叉树的遍历规则

二叉树的遍历按照特定的规则和顺序遍历其中所有节点,且每个节点仅被访问一次。尽管二叉树是非线性结构,但其遍历方式访问节点的顺序是线性的,并且存在多种不同的遍历规则和顺序。

二叉树的遍历规则有深度优先广度优先两种:

  • 深度优先遍历(也称为孩子优先遍历)按照深度优先的原则,遍历完当前节点的所有子节点之后再回溯到父节点继续遍历,其中又分为先序遍历、中序遍历和后序遍历三种方式。
  • 广度优先遍历(也称为兄弟优先遍历、层次遍历)按照广度优先的原则,从上到下,从左到右逐层遍历每个节点。

3.1 深度优先遍历

已知 3 个元素共有 6 种排列方式,由 3 个元素 A、B、C 构成的一棵二叉树,如下所示:

1
2
3
4
       | 先遍历左子树     | 先遍历右子树
  A    | 1. 先根次序:ABC | CBA
 / \   | 2. 中根次序:BAC | CAB
B   C  | 3. 后根次序:BCA | ACB

观察上述序列可知,前 3 个序列的共同特点是,B 在 C 之前,即先遍历左子树,后遍历右子树;后 3 个序列分别与前 3 个序列的次序相反。实际上先遍历左子树还是先遍历右子树在算法设计上没有本质区别,因此约定遍历子树的次序是先左后右

二叉树深度优先的遍历次序有以下 3 种,遍历规则也是递归的,先遍历左子树,再遍历右子树,三者之间的差别仅在于访问节点的时机不同:

  1. 先根次序 (PreOrder): 访问根节点,遍历左子树,遍历右子树。
  2. 中根次序 (InOrder): 遍历左子树,访问根节点,遍历右子树。
  3. 后根次序 (PostOrder): 遍历左子树,遍历右子树访问根节点。

下面分别举一个例子:

  • 一棵二叉树的先根次序遍历顺序为:ABDGCEFH,先访问根节点 A,再访问 A 的左子树,最后访问 A 的右子树:

    二叉树先根次序遍历
  • 中根次序遍历顺序为:DGBAECHF,左、右子树上的所有节点,分别在根节点 A 访问前、后访问:

    二叉树中根次序遍历
  • 后根次序遍历顺序为:GDBEHFCA,最后访问根节点 A:

    二叉树后根次序遍历

3.2 广度优先遍历

二叉树的广度优先遍历是按层次进行的,遍历过程从根节点开始,逐层深入,从左至右依次访问完当前层的所有节点再访问下一层。

一棵二叉树的先根次序遍历顺序为:ABCDEFG,如下图所示:

二叉树层次遍历

4 二叉树的抽象数据类型

二叉树的主要操作有:创建二叉树、获得父母或孩子节点、遍历、插入和删除等。

首先我们声明二叉树的抽象节点类 AbstractNode<T>:

1
2
3
4
5
6
7
8
/**
 * 二叉树节点的抽象数据类型
 * @param <T> 元素类型
 */
public abstract class AbstractNode<T> {
    //数据域
    T data;
}
  • 这里我们只声明了数据域 data,剩下的字段交由实现类补充。

二叉树的数据节点可以有多种实现方式,例如二叉链表、三叉链表,甚至是基于数组的静态链表。不同的实现方式需要的指针域各不相同,但它们都需要有最基本的数据域。

然后声明二叉树的抽象数据类型 AbstractBinaryTree<T>

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
/**
 * 二叉树抽象数据类型
 * @param <T> 节点元素类型
 */
public abstract class AbstractBinaryTree<T> {
    //根节点
    protected AbstractNode<T> root;

    //判断是否是空树
    protected boolean isEmpty() {
        return root == null;
    }

    //返回树的节点数
    protected int size() {
        if (isEmpty()) {
            return 0;
        }
        return size(root);
    }
    protected abstract int size(AbstractNode<T> node);

    //返回树的深度
    protected int depth() {
        if (isEmpty()) {
            return 0;
        }
        return depth(root);
    }
    protected abstract int depth(AbstractNode<T> node);

    //返回关键字为 key 节点所在的层次
    protected abstract int level(T key);

    //输出树的先根次序遍历结果
    protected abstract void preOrder();
    //输出中根次序遍历序列
    protected abstract void inOrder();
    //输出树的后根次序遍历结果
    protected abstract void postOrder();
    //输出树的层次遍历结果
    protected abstract void levelOrder();

    //插入 x 元素作为根节点并返回
    protected abstract AbstractNode<T> insert(T x);
    //插入 x 元素作为 p 节点的左、右孩子并返回
    protected abstract AbstractNode<T> insert(AbstractNode<T> p, T x, boolean leftChild);
    //先序遍历查找首个关键字为 key 的节点
    protected abstract AbstractNode<T> search(T key);
    //判断是否包含关键字为 key 的元素
    protected abstract boolean contains(T key);
    //删除 p 节点的左、右子树
    protected abstract void remove(AbstractNode<T> p, boolean leftChild);
    //删除树的所有节点
    protected void clear() {
        root = null;
    }
}

二叉树抽象类中维护了根节点,并实现了 isEmpty()clear() 这两个简单的通用方法。其余的方法根据节点数据类型的不同,会交由特定的子类来实现。

5 二叉树的存储结构

二叉树主要采用链式存储结构,顺序存储结构仅适用于完全二叉树(满二叉树)。

5.1 顺序存储结构

二叉树的顺序存储结构是用数组来表示的,具体方法是将二叉树的节点按照**广度优先遍历(层次遍历)**的顺序依次存放在数组中,然后再根据数组下标的关系来确定节点之间的父子关系。

假设二叉树中的某个节点在数组中的下标为 $i$,则其左子节点在数组中的下标为 $2i + 1$,右子节点在数组中的下标为 $2i + 2$。其父节点在数组中的下标为 $[(i-1) / 2]$ (向下取整)。

顺序存储结构的优点是可以直接根据数组下标来访问节点,因此查找某个节点的效率很高。缺点是需要额外的存储空间来存放空节点(即二叉树中没有的节点),而且在插入和删除节点时需要移动大量的节点,效率较低。因此,顺序存储结构通常适用于节点数比较少、静态不变的二叉树。

以下是一棵 $n$ 个节点的完全二叉树及其顺序存储结构的示意图:

完全二叉树的顺序存储结构

5.2 链式存储结构

链式存储结构是一种灵活的存储方式,因为每个节点只需存储自身数据和指向左、右孩子的指针,可根据情况动态分配内存。常见的链式存储结构有二叉链表、三叉链表和静态二/三叉链表等。

5.2.1 二叉链表

二叉树的二叉链表存储结构如下:

二叉链表二叉树
  • 除了数据域之外,采用两个地址域分别指向左、右孩子节点。

采用二叉链表存储二叉树时,每个节点只存储了到其孩子节点的单向关系,没有存储到其父节点的关系。因此,要获得父节点需要从根节点开始进行二次查找,这将十分浪费性能。

5.2.2 三叉链表

二叉树的三叉链表存储结构如下:

三叉链表二叉树

其节点在二叉链表节点的基础上,增加一个地址域 parent 指向其父母节点,这样便存储了父母节点与孩子节点的双向关系

5.2.3 静态二/三叉链表

还有一种存储二叉树的方式是静态二/三叉链表,使用节点数组存储所有节点。每个节点都存储其左、右孩子节点下标,同时还可以(可选地)存储其父母节点下标。节点间的关系通过下标表示,如果某个节点不存在,则使用 -1 表示。

下面是一个静态三叉链表的示意图:

静态三叉链表二叉树

6 基于二叉链表的二叉树实现

首先声明二叉树实现类 BinaryTree<T>,该类继承自二叉树抽象类 AbstractBinaryTree<T>。同时,在 BinaryTree<T> 类中创建内部节点类 BinaryTreeNode<T>,该内部节点类继承自二叉树的抽象节点类 AbstractNode<T>

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * 基于二叉链表的二叉树实现类
 * @param <T> 节点元素类型
 */
public class BinaryTree<T> extends AbstractBinaryTree<T> {

    /**
     * 二叉链表节点类
     * @param <T> 节点元素类型
     */
    static class BinaryTreeNode<T> extends AbstractNode<T> {
        //指针域,分别指向左右孩子节点
        BinaryTreeNode<T> left, right;

        //构造方法
        public BinaryTreeNode(T data, BinaryTreeNode<T> left,
                              BinaryTreeNode<T> right) {
            this.data = data;
            this.left = left;
            this.right = right;
        }
        //构造叶子节点
        public BinaryTreeNode(T data) {
            super.data = data;
        }
        @Override
        public String toString() {
            return super.data.toString();
        }
        //判断是否是叶子节点
        public boolean isLeaf() {
            return this.left == null && this.right == null;
        }
    }
}

然后开始实现抽象类定义的抽象方法。

6.1 获取二叉树深度

这里需要有两个获取深度的重载方法:depth()depth(AbstractNode<T> node)。其中,depth() 的实现已经在抽象类中提供。depth() 方法会调用 depth(AbstractNode<T> node) 并传入 root 节点来计算深度。因此,我们需要计算从某个节点开始到叶子节点的最大深度:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
@Override
public int depth(AbstractNode<T> node) {
    //递归退出条件
    if (node == null) {
        return 0;
    }
    int maxChildDepth = 0;
    BinaryTreeNode<T> bNode = (BinaryTreeNode<T>) node;
    //递归左子树最大深度
    int leftChildDepth = depth(bNode.left);
    //递归右子树最大深度
    int rightChildDepth = depth(bNode.right);
    if (leftChildDepth > maxChildDepth) {
        maxChildDepth = leftChildDepth;
    }
    if (rightChildDepth > maxChildDepth) {
        maxChildDepth = rightChildDepth;
    }
    //返回左右子树深度的较大值,然后加上 root 层本身深度
    return maxChildDepth + 1;
}

6.2 获取二叉树节点数量

与获取深度类似,size 也有两个重载方法,其中一个已经在抽象类里实现,我们只需实现计算从某个节点的子树的节点数即可:

1
2
3
4
5
6
7
8
9
@Override
public int size(AbstractNode<T> node) {
    if (node == null) {
        return 0;
    }
    BinaryTreeNode<T> bNode = (BinaryTreeNode<T>) node;
    // 递归调用,返回左右子树节点数 + 自身节点数
    return size(bNode.left) + size(bNode.right) + 1;
}

6.3 二叉树插入数据

由于本文介绍的二叉树是最基础的广义二叉树,因此对插入过程做了简化:插入节点时,被插入位置的原节点默认作为新节点的左子节点存在。

1
2
3
4
5
6
@Override
public BinaryTreeNode<T> insert(T x) {
    // 插入 x 作为根节点,原根节点作为 x 的左孩子,返回 x
    BinaryTreeNode<T> oldRoot = (BinaryTreeNode<T>) this.root;
    return (BinaryTreeNode<T>) (this.root = new BinaryTreeNode<>(x, oldRoot, null));
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * 插入 x 为 p 节点的左、右孩子,将 p 节点的原左、右孩子下移为 x 的左孩子
 * @param p 目标节点
 * @param x 待插入数据
 * @param leftChild 待插入节点是否作为左孩子
 * @return x == null,则不插入返回 null;p == null 则抛出异常;成功插入返回 x 节点
 */
@Override
public AbstractNode<T> insert(AbstractNode<T> p, T x, boolean leftChild) {
    if (x == null)
        return null;
    BinaryTreeNode<T> bp = (BinaryTreeNode<T>) p;
    if (leftChild) {
        BinaryTreeNode<T> old = bp.left;
        bp.left = new BinaryTreeNode<>(x, old, null);
        return bp.left;
    } else {
        BinaryTreeNode<T> old = bp.right;
        bp.right = new BinaryTreeNode<>(x, old, null);
        return bp.right;
    }
}

6.4 二叉树删除子树

在二叉树中删除一个节点,不仅要修改其父母节点的 leftright 域,还要约定如何调整被删除节点子树结构的规则,即删除一个节点,原先以该节点为根的子树则变成由原左子树和原右子树组成的森林,需要约定一种规则使这个森林组成一棵子树。

由于本文介绍的二叉树是最基础的广义二叉树,因此无法约定左右子树的合并规则,只能直接删除以一个节点为根的一棵子树,然后交给 JVM 去回收空间。代码实现如下:

1
2
3
4
5
6
7
8
9
@Override
public void remove(AbstractNode<T> p, boolean leftChild) {
    BinaryTreeNode<T> bp = (BinaryTreeNode<T>) p;
    if (leftChild) {
        bp.left = null;
    } else {
        bp.right = null;
    }
}

6.5 二叉树先根次序遍历

由于先根次序遍历规则是递归的,采用递归算法实现的递归方法必须有参数,通过不同的实际参数区别递归调用执行中的多个方法。而二叉树类必须提供从根节点开始遍历的成员方法,因此,每种递归的遍历算法由两个重载的成员方法实现。

BinaryTree<T> 类声明以下重载的成员方法,以先根次序遍历二叉树,采用递归算法实现递归的先根次序遍历规则:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
@Override
public void preOrder() {
    //先从根节点开始遍历
    preOrder((BinaryTreeNode<T>) this.root);
    System.out.println("");
}
private void preOrder(BinaryTreeNode<T> p) {
    //递归退出条件
    if (p == null) {
        return;
    }
    //先序调用根节点
    System.out.print(p + " ");
    //递归调用左子树
    preOrder(p.left);
    //递归调用右子树
    preOrder(p.right);
}

6.6 二叉树中根次序遍历

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
@Override
public void inOrder() {
    //先传入根节点
    inOrder((BinaryTreeNode<T>) this.root);
    System.out.println("");
}
private void inOrder(BinaryTreeNode<T> p) {
    //递归退出条件
    if (p == null) {
        return;
    }
    //递归调用左子树
    inOrder(p.left);
    //中序遍历根节点
    System.out.print(p + " ");
    //递归调用右子树
    inOrder(p.right);
}

6.7 二叉树后根次序遍历

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
@Override
public void postOrder() {
    //先传入根节点
    postOrder((BinaryTreeNode<T>) this.root);
    System.out.println("");
}
private void postOrder(BinaryTreeNode<T> p) {
    //递归退出条件
    if (p == null) {
        return;
    }
    //递归调用左子树
    postOrder(p.left);
    //递归调用右子树
    postOrder(p.right);
    //后序遍历根节点
    System.out.print(p + " ");
}

6.8 二叉树层次遍历

层次遍历即广度优先遍历,这种算法的特点是通过一个先进先出的 Queue 来控制遍历进程:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
@Override
public void levelOrder() {
    BinaryTreeNode<T> rootNode = (BinaryTreeNode<T>) this.root;
    //判空
    if (rootNode == null) {
        return;
    }
    Queue<BinaryTreeNode<T>> queue = new LinkedList<>();
    //先将 root 加入队列
    queue.offer(rootNode);

    while (!queue.isEmpty()) {
        // 一弹二入
        BinaryTreeNode<T> poll = queue.poll();
        System.out.print(poll + " ");
        if (poll.left != null) {
            queue.offer(poll.left);
        }
        if (poll.right != null) {
            queue.offer(poll.right);
        }
    }
    System.out.println();
}

6.9 二叉树节点查询

查询涉及到两个方法 search(T key)contains(T key),需要从根节点开始,遍历二叉树进行查询。

首先我们声明一个 search 的重载方法然后用递归实现:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
@Override
public AbstractNode<T> search(T key) {
    return search((BinaryTreeNode<T>) root, key);
}
public AbstractNode<T> search(BinaryTreeNode<T> node, T key) {
    if (node == null || key == null) {
        return null;
    }
    //找到则返回
    if (node.data.equals(key)) {
        return node;
    }
    //递归左节点
    AbstractNode<T> search = search(node.left, key);
    if (search != null) {
        return search;
    }
    //递归右节点
    search = search(node.right, key);
    return search;
}

然后 contains(T key) 方法直接调用 search(T key) 即可:

1
2
3
4
@Override
public boolean contains(T key) {
    return search(key) != null;
}

6.10 二叉树节点层数

获取节点层数与获取二叉树深度类似,都可以通过递归重载方法实现,找到了返回层数,找不到返回 -1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
@Override
public int level(T key) {
    BinaryTreeNode<T> rootNode = (BinaryTreeNode<T>) this.root;
    //判空
    if (rootNode == null) {
        return -1;
    }
    return level(rootNode, key, 1);
}

//重载方法
private int level(BinaryTreeNode<T> node, T key, int level) {
    //判空
    if (node == null) {
        return -1;
    }
    //找到了,返回节点层数
    if (node.data == key) {
        return level;
    }
    //递归左子树
    int levelLeft = level(node.left, key, level + 1);
    if (levelLeft != -1) {
        return levelLeft;
    }
    //递归右子树
    return level(node.right, key, level + 1);
}

需要注意,我们给重载方法新增了一个参数 level 来保存当前节点的层数,这样递归实现起来就更加简便了。