vlambda博客
学习文章列表

信息学能够有助于孩子未来工作发展，提升孩子的综合能力。

这一节课，我们走进树形结构的世界，了解树的基本理论，了解二叉树的相关概念和性质，学习二叉树的存储、遍历方式。最后我们简单了解森林的基本知识以及森林和二叉树的相关转换。

在我们前面讲数据结构的时候，我们讲过四种结构：

集合一对一线性结构一对多树形结构多对多图状（网状）结构

我们当时还画了他们的图，其中树形结构的图如下：

今天，我们来具体看一下树形结构的内容。

树是一对多的结构，相比一对一线性结构，更加复杂，考虑的内容也比较多！

1 什么是树

树（tree）T是一个包含n(n>=0)个数据元素的有限集合。并且：

1、当n=0时，T称为空树；2、如果n>0，则树有且仅有一个特定的被称为根（root）的结点，树的根结点只有后继，没有前驱；3、当n>1时,除根结点以外的其余结点可分为m(m>0)个互不相交的非空有限集T1、T2、...、Tm,其中每一个集合本身又是一棵非空树,并且称它们为根结点的子树（subtree）。

树有很多重要的概念：

结点：树上的一个点，包含一个数据元素及若干指向其子树的分支。

结点的度(Degree)：结点拥有的子树的个数。

叶子（Leaf)或终端结点：度为0的结点（没有子结点的结点）。

分支结点或非终端结点：度不为0的结点。

树的度：树内各结点的度的最大值。

孩子（child)（子结点）：结点的子树的根称为该结点的孩子

双亲（Parent)（父结点）：结点是其子结点的双亲结点。

兄弟(Sibling)：同一双亲的孩子之间互称为兄弟。

祖先：结点的祖先是从该结点所经分支上的所有结点。

子孙：以某结点为根的子树中的任一结点都称为该结点的子孙。

层次(Level)：从根开始定义起，根为第一层，根的孩子为第二层。双亲在同一层的结点互为堂兄弟。

树的深度(Depth)：树中结点的最大层次称为树的深度或高度。

有序树：若将树中的结点的各子树看成从左至右是有次序的（即不能互换）则称该树为有序树。

树的表示方法，主要有：

嵌套集合广义表凹入表示

对于下面这棵树，这种方法叫一般表示。我们针对不同的方法可以有不同的表示：

1、嵌套集合

嵌套集合就是双亲结点中会包含所有的孩子结点。图示如下：

2、广义表

广义表是通过括号将子结点包含在一起：

3、凹入表示

凹入表示，其实就是对子结点加缩进。注意，同一层次的结点，缩进相同。

树中最重要的就是二叉树！

1 二叉树的定义

二叉树也是树，不过有两条限制：

每个结点最多只能有两个孩子结点；每个孩子结点有左右之分。

二叉树主要有如下几种形态：

其中：

（a）表示没有当前结点，也没有左右结点；（a）是一棵空树。（b）表示只有当前结点，没有左右结点；（c）表示只有当前结点和左子结点；（d）表示只有当前结点和右子结点；（e）表示既有当前结点，又有左右子结点；这个说明这棵树是满二叉树。

二叉树的性质是树理论中，最重要的！

性质1：有n(n>0)个结点的二叉树的分支数为n-1。

证明：对于每个结点，除了根结点外，剩余的所有结点都是其父结点的分支。也就是除根结点外的n-1个结点，都是分支。所以分支数为n-1。

注：这个性质也可以这么理解，有n个结点的树，有n-1条边，这个因为，除根结点之外，剩下所有结点都有一条边指向其父结点。

性质2：若二叉树的高度为h（h≥0），则该二叉树最少有h个结点，最多有   个结点。

证明：二叉树最少结点是每一层只有一个结点，一共有h层，一共有h个结点。最多情况，每一层都满了，对于第i层，有   。所以有h层，就一共有：  个结点。

性质3：含有n个结点的二叉树的高度最大值为n，最小值为   。

证明：因为在二叉树中，每层至少有一个结点，因此对于含有n个结点的二叉树，其高度不会超过n。根据性质2可以得知，高度为h的二叉树最多有   个结点，即   ，因此   。由于h是整数，所以   。

性质4：具有 n 个结点的完全二叉树的高度为   。

证明：性质4其实就是性质3的推广。高度最小时，就是完全二叉树。

性质5：如果将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号0、1、2、…、n-1。则第i个结点的左孩子结点的编号是   ，右孩子结点的编号是   。

证明：这道题最好的证明方式就是通过画图，总结规律：

这些性质会在竞赛中考到，这些也只是基本性质，考试中会有各种变形。

4 二叉树的存储结构

二叉树在使用过程中，一般有两种方法，一种是顺序结构存储，一种是链式结构存储。

1、数组表示法

顺序结构存储，就是我们要将二叉树存在数组中，这个时候，存放的位置，就是二叉树中结点对应到满二叉树对应位置的索引：

这样的话，我们就可以随机访问每个元素，也可以非常方便的插入和删除树上的结点。但是这种做法可能会非常浪费空间。如果树中结点特别少，但是树的高度特别高，就会有很多浪费。

2、二叉链表表示法

二叉链表表示法是为了解决上面浪费空间的问题，二叉链表需要存放当前结点的数据和两个指向其左右子结点的指针。如果没有对应子结点，就把这个指针设为空。

这种方法需要多少个结点就申请多少个空间。不会造成浪费，但是他会引入链表本身的缺点，不支持随机访问。

3、三叉链表表示法

三叉链表和二叉链表理论完全一致，区别就在于，多了一个指向其父结点的指针。对于根结点来说，一般将其父结点指向自己，所以当我们判断什么是根结点的时候，我们就判断其父结点指针是否指向了自己。

5 二叉树的遍历

1、总述

二叉树有四种遍历。

先序遍历中序遍历后序遍历层次遍历

前三个特别好记，先序、中序和后序强调的是根的访问顺序：

如果先访问根，后访问左右，访问顺序就是根左右，这个叫先序遍历；

如果先访问左，中间访问根，最后访问右，访问顺序就是左根右，这个叫中序遍历；

如果先访问左右，最后访问根，访问顺序就是左右根，这个叫后序遍历。

在具体的过程中，这个过程是递归实现的。例如对于下面的树：

2、先序遍历

先序遍历和我们的常识很像，先访问根结点，然后进入到左子树，访问左子结点，访问完左子结点，就访问右子结点。

遍历顺序为：A、B、D、E、G、H、C、F、I。

3、中序遍历

中序遍历是先访问左，我们可以这样理解。在每个结点的左子树的，都在其左边，在每个结点右子树的，都在其右边，当我们把所有的这些结点看做同一层的时候，从左往右就可以了。例如上面的图，我们可以变为如下：

然后我们按照从左到右的顺序排列：

所以中序遍历为：D、B、G、E、H、A、C、F、I。

4、后序遍历

后序遍历就需要我们认真分析了。后序遍历要先访问左子结点，再访问右子结点，最后访问根结点。当然我们还是要先从根结点出发。

想访问根结点，要先访问左子树，再访问右子树。最后访问根结点。所以顺序为：

{A左子树结点}{A右子树结点}A

对于左右子树结点，还是按照上面的原则：

【A左子树结点】 {B左子树结点}{B右子树结点}B【A右子树结点】 {C左子树结点（空）}{C右子树结点}C

对于B：

【B左子树结点】 D【B右子树结点】 {E左子树结点：G}{E右子树结点：H}E

到这里，B的已经有序：

{D}{{G}{H}E}B去掉括号：DGHEB

对于C：

【C右子树结点】 {F左子树结点（空）}{E右子树结点：I}F

到这里，C的已经有序：

{}{{}{I}F}C去掉括号：IFC

回到A：

{DGHEB}{IFC}A去掉括号：DGHEBIFCA

这个还不是最难的，最难的是根据两种遍历方式，求另一种遍历方式。

5、根据两种遍历求另一种遍历序列

例如：

已知二叉树的中序遍历和后序遍历，求其先序遍历；已知二叉树的中序遍历和先序遍历，求其后序遍历；

注：不能通过二叉树的先序和后序遍历得到其中序遍历。这是因为，当访问过程中，根不在中间时，某个结点只有一个子结点的时候，我们就不能区分这个结点到底是左子结点还是右子结点了。

这种题目，我们要先根据两种遍历恢复二叉树，然后再获取第三种遍历方式。举个例子：

先序+中序->后序

就以我们上面的为例：

先序：A、B、D、E、G、H、C、F、I中序：D、B、G、E、H、A、C、F、I

我们知道，先序的第一个是这个树的根结点。然后我们在中序中找A，将中序分为左右两部分，然后我们要在这个时候写对应的后序，只需要考虑当前部分是按照左右根的顺序就可以了：

先序：A、{B、D、E、G、H}、{C、F、I}中序：{D、B、G、E、H}、A、{C、F、I}顺序为：左右根后序：{B、D、E、G、H}、{C、F、I}、A

对于先序的每一部分，第一个都是当前子树的根结点，然后我们再在中序中对应部分，使用根结点将左右分开。

先序：A、{B、{D}、{E、G、H}}、{C、{F、I}}中序：{{D}、B、{G、E、H}}、A、{C、{F、I}}顺序为：左右根后序：{{D}、{G、E、H}、B}、{{F、I}、C}、A

然后再分，单个的就不用再分了：

先序：A、{B、{D}、{E、{G}、{H}}}、{C、{F、{I}}}中序：{{D}、B、{{G}、E、{H}}}、A、{C、{F、{I}}}

这个时候，每个结点都单独分开了。然后我们就可以考虑后序了，只需要去掉括号就可以了：

先序：A、{B、{D}、{E、{G}、{H}}}、{C、{F、{I}}}顺序为：左右根后序：{{D}、{{G}、{H}、E}、B}、{{{I}、F}、C}、A去掉括号：DGHEBIFCA

中序+后序->先序

然后我们再来看

中序：D、B、G、E、H、A、C、F、I后序：D、G、H、E、B、I、F、C、A

我们知道，后序的最后一个是这个树的根结点。然后我们在中序中找A，将中序分为左右两部分，然后我们要在这个时候写对应的先序，只需要考虑当前部分是按照根左右的顺序就可以了：

中序：{D、B、G、E、H}、A、{C、F、I}后序：{D、G、H、E、B}、{I、F、C}、A顺序为：根左右先序：A、{D、G、H、E、B}、{I、F、C}

对于后序的每一部分，最后一个都是当前子树的根结点，然后我们再在中序中对应部分，使用根结点将左右分开。

中序：{{D}、B、{G、E、H}}、A、{C、{F、I}}后序：{{D}、{G、H、E}、B}、{{I、F}、C}、A顺序为：根左右先序：A、{B、{D}、{G、H、E}}、{C、{I、F}}

然后再分，单个的就不用再分了：

中序：{{D}、B、{{G}、{E}、H}}、A、{C、{F、{I}}}后序：{{D}、{{G}、{H}、E}、B}、{{{I}、F}、C}、A顺序为：根左右先序：A、{B、{D}、{E、{G}、{H}}}、{C、{F、{I}}}

这个时候，每个结点都单独分开了。然后我们就可以考虑先序了，只需要去掉括号就可以了：

后序：{{D}、{{G}、{H}、E}、B}、{{{I}、F}、C}、A顺序为：左右根先序：A、{B、{D}、{E、{G}、{H}}}、{C、{F、{I}}}去掉括号：ABDEGHCFI

6、层次遍历

层次遍历就是按照深度从上往下，按照左右从前往后遍历。上面的那个层次遍历如下：

ABCDEFGHI

然后我们看一下森林！

1 什么是森林

森林：是m（m≥0）棵互不相交的树的集合；不同的树，有自己的根结点，一个森林中，至少有两个树，也就是至少有两个根结点。如图所示：

这是有两棵树的森林。

森林中最重要的森林和二叉树的转换：

森林变为二叉树，有如下两个原则：

森林中的左子结点就是二叉树中的左子结点；森林中的右面第一个兄弟结点，就是该结点的右子结点。

简单来说就是：左孩子还是左孩子，右兄弟变成右孩子。

例如下面这个森林：

转换为二叉树如下：

二叉树转回森林，跟上面的过程是相反的，左孩子还是左孩子，右孩子变成右兄弟。

本节课的作业，就是复习上面的所有知识，并完成下面的竞赛真题！

1 NOIP2011年提高组真题

1、（单选题）右图是一棵二叉树，它的先序遍历是（ ）

A．ABDEFC B．DBEFAC C．DFEBCA D．ABCDEF

2、（不定项选择）如果根结点的深度记为1，则一棵恰有2011 个叶子结点的二叉树的深度可能是（ ）

A．10 B．11 C．12 D．2011

1、（单选题）设根节点深度为0，一棵深度为h的满k（k>1）叉树，即除最后一层无任何子节点外，每一层上的所有结点都有k个子结点的树，共有（ ）个结点：

A. (k^(h+1) - 1) / (k - 1)B. k^(h-1)C. k^hD. (k^(h-1)) / (k - 1)

2、（不定项选择）2-3 树是一种特殊的树，它满足两个条件：

（1）每个内部结点有两个或三个子结点；（2）所有的叶结点到根的路径长度相同。

如果一棵2-3 树有10 个叶结点，那么它可能有（ ）个非叶结点。

A. 5B. 6C. 7D. 8