22二叉树基础(上):什么样的二叉树适合用数组来存储

首先,该文章来自于极客时间网站,王争的专栏——《数据结构与算法之美》,我这里只是做最简单的解释、记录并添加自己的见解,只是作为个人笔记,若侵权,马上删除。最后建议直接去该网站上购买该课程看原作者的讲解,一来是支持作者,二来是作者写的确实不错。

之前讲的都是线性表结构,例如栈、队列等。本节主要讲一种非线性表结构,树。树这种数据结构比线性表复杂的多,内容也比较多。主要如下:

img

带着问题学习,是最有效的学习方式之一。首先思考一个问题:二叉树有哪几种存储方式?什么样的二叉树适合用数组来存储?

树(Tree)

树的结构如下图所示:

img

从图中可以发现,“树”这种数据结构真的很像我们现实生活中的“树”,这里面每个元素我们叫作“节点”;用来连线相邻节点之间的关系,我们叫作“父子关系”。像上图中的非树结构,并不能找到“父子关系”,所以也就不是非树结构。

再比如下面这幅图,A 节点就是 B 节点的父节点,B 节点是 A 节点的子节点。B、C、D 这三个节点的父节点是同一个节点,所以它们之间互称为兄弟节点。把像节点E这样没有父节点的节点称为根节点。把没有子节点的节点叫作叶子节点或者叶节点,比如图中的 G、H、I、J、K、L 都是叶子节点。

img

除此之外,关于“树”,还有三个比较相似的概念:高度(Height)、深度(Depth)、层(Level)。它们的定义是这样的:

img

关于这三个概念的例子如下:

img

其实关于这几个概念的理解可以对比在生活中的例子:

  1. 生活中,“高度”这个概念,其实就是从下往上度量,比如我们要度量第 10 层楼的高度,起点是地面。所以,树这种数据结构的高度也是一样,从最底层开始计数,并且计数的起点是 0。
  2. “深度”这个概念在生活中是从上往下度量的,比如水中鱼的深度,是从水平面开始度量的。所以,树这种数据结构的深度也是类似的,从根结点开始度量,并且计数起点也是 0。
  3. “层数”跟深度的计算类似,不过,计数起点是 1,也就是说根节点的位于第 1 层。

二叉树(Binary Tree)

树有很多种类,最常用的是二叉树。

二叉树,顾名思义,每个节点最多有两个“叉”,也就是两个子节点,分别是左子节点和右子节点。不过,二叉树并不要求每个节点都有两个子节点,有的节点只有左子节点,有的节点只有右子节点。下图中都是二叉树

img

上图中,编号2和编号3两个二叉树比较特殊。

编号2的二叉树中,

  1. 叶子节点全部都在底层;
  2. 除了叶子节点之外,每个节点都有左右两个子节点。

这种二叉树就叫作满二叉树

编号3的二叉树中,

  1. 叶子节点都在最底下两层;
  2. 最后一层的叶子节点都靠左排列;
  3. 除了最后一层,其他层的节点个数都要达到最大

这种二叉树叫做完全二叉树

满二叉树比较好理解,也比较好识别,但是对于完全二叉树,有不容易那么区分了。如下图为几个完全二叉树和非完全二叉树的例子。

img

感觉完全二叉树不像满二叉树,特征那么明显。为什么还要把完全二叉树单独命名呢?为什么偏偏把最后一层的叶子靠左排列的叫完全二叉树?而靠右排列的就不叫完全二叉树呢?要想了解这个问题,我们首先要了解一个问题:如何表示(或者存储)一棵二叉树?

存储一颗二叉树,有两种方法:

  1. 基于指针或者引用的二叉链式存储法
  2. 基于数组的顺序存储法

链式存储法比较简单,直观。如下图所示,每个节点都有三个字段,其中一个存储数据,另外两个是指向左右子节点的指针。只要知道根节点,就可以通过左右子节点的指针,把整棵树都串起来。这种存储方式我们比较常用。大部分二叉树代码都是通过这种结构实现的。

img

接着我们再来看看基于数组的顺序存储法。我们把根节点存储在下标 i = 1 的位置,那左子节点存储在下标 2 i = 2 的位置,右子节点存储在 2 i + 1 = 3 的位置。以此类推,B 节点的左子节点存储在 2 i = 2 2 = 4 的位置,右子节点存储在 2 i + 1 = 2 2 + 1 = 5 的位置。

img

总结一下:

  1. 如果节点 X 存储在数组中下标为 i 的位置,下标为 2 i 的位置存储的就是左子节点,下标为 2 i + 1 的位置存储的就是右子节点。
  2. 反过来,下标为 i/2 的位置存储就是它的父节点。

通过这种方式,我们只要知道根节点存储的位置(一般情况下,为了方便计算子节点,根节点会存储在下标为 1 的位置),这样就可以通过下标计算,把整棵树都串起来。

知道了这个之后,我们就可以进一步思考为什么要把完全二叉树单独定义了。对于完全二叉树,在使用基于数组的顺序存储法时,仅仅“浪费”了一个下标为0的存储位置。如果是非完全二叉树,其实会浪费比较多的数组存储空间。例子如下:

img

所以,如果某棵二叉树是一棵完全二叉树,那用数组存储时最省内存的一种方式。因为数组的存储方式不需要像链式存储法那样,要存储额外的左右子节点的指针。这也是为什么完全二叉树会单独定义的原因,也是为什么完全二叉树要求最后一层的子节点都靠左的原因。

二叉树的遍历

前面介绍了二叉树的基本定义和存储方法。对于二叉树的面试而言,还有另外一种特别重要的操作——遍历。

对于二叉树的遍历,经典的方法有三种:前序遍历、中序遍历和后序遍历。其中,前、中、后序,表示的是节点与它的左右子树节点遍历打印的先后顺序。

  1. 前序遍历是指,对于树中的任意节点来说,先打印这个节点,然后再打印它的左子树,最后打印它的右子树。
  2. 中序遍历是指,对于树中的任意节点来说,先打印它的左子树,然后再打印这个节点,最后打印它的右子树。
  3. 后序遍历是指,对于树中的任意节点来说,先打印它的左子树,然后再打印它的右子树,最后打印这个节点。

img

实际上,二叉树的前、中、后序遍历就是一个递归的过程。比如,前序遍历,其实就是先打印根节点,然后再递归地打印左子树,最后递归地打印右子树。

写递归代码的关键点在于能不能写出递推公式。而写递推公式的关键在于:如果要解决问题A,就假设子问题B、C已经解决,然后再看如何利用B、C来解决A。通过这种方式,将前、中、后序的递推公式都写出来:

1
2
3
4
5
6
7
8
前序遍历的递推公式:
preOrder(r) = print r->preOrder(r->left)->preOrder(r->right)

中序遍历的递推公式:
inOrder(r) = inOrder(r->left)->print r->inOrder(r->right)

后序遍历的递推公式:
postOrder(r) = postOrder(r->left)->postOrder(r->right)->print r

有了递推公式,代码就好些了。如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void preOrder(Node* root) {
if (root == null) return;
print root // 此处为伪代码,表示打印root节点
preOrder(root->left);
preOrder(root->right);
}

void inOrder(Node* root) {
if (root == null) return;
inOrder(root->left);
print root // 此处为伪代码,表示打印root节点
inOrder(root->right);
}

void postOrder(Node* root) {
if (root == null) return;
postOrder(root->left);
postOrder(root->right);
print root // 此处为伪代码,表示打印root节点
}

可以看到,二叉树的前、中、后序遍历的递归实现并不是很复杂。从我前面画的前、中、后序遍历的顺序图,可以看出来,每个节点最多会被访问两次,所以遍历操作的时间复杂度,跟节点的个数 n 成正比,也就是说二叉树遍历的时间复杂度是 O(n)。

解答开篇&内容小结

本节主要讲了非线性表数据结构——树。关于树,有几个比较常用的概念需要掌握:根节点、叶子节点、父节点、子节点、兄弟节点,还有节点的高度、深度、层数,以及树的高度。

我们平时最常用的树是二叉树。二叉树的每个节点最多有两个子节点,分别是左子节点和右子节点。二叉树中,有两种比较特殊的树,分别是满二叉树和完全二叉树。满二叉树又是完全二叉树的一种特殊情况。

二叉树既可以用链式存储,也可以用数组顺序存储。数组顺序存储的方式比较适合完全二叉树,其他类型的二叉树用数组存储会比较浪费存储空间。除此之外,二叉树里非常重要的操作就是前、中、后序遍历操作,遍历的时间复杂度是 O(n),你需要理解并能用递归代码来实现。

课后思考

  1. 给定一组数据,比如 1,3,5,6,9,10。请问可以构建出多少种不同的二叉树?

    答:卡特兰数,是C[n,2n] / (n+1)种形状,c是组合数,节点的不同又是一个全排列,一共就是n!*C[n,2n] / (n+1)个二叉树。可以通过数学归纳法推导得出。

  2. 本节讲了三种二叉树的遍历方式,前、中、后序。实际上,还有另外一种遍历方式,也就是按层遍历,你知道如何实现吗?

    答:层次遍历需要借助队列这样一个辅助数据结构。(其实也可以不用,这样就要自己手动去处理节点的关系,代码不太好理解,好处就是空间复杂度是o(1)。不过用队列比较好理解,缺点就是空间复杂度是o(n))。根节点先入队列,然后队列不空,取出头元素,如果左孩子存在就入列队,否则什么也不做,右孩子同理。直到队列为空,则表示树层次遍历结束。树的层次遍历,其实也是一个广度优先的遍历算法。

------ 本文结束------
zdaiot wechat
欢迎您扫一扫上面的微信公众号,订阅我的博客!
坚持原创技术分享,您的支持将鼓励我继续创作!