【数据结构】二叉树

【数据结构】⼆叉树

【⼆叉树】

⼆叉树是最为简单的⼀种树形结构。所谓树形结构，其特征（部分名词的定义就不明确给出了，毕竟不是学术⽂章。。）在于：

1. 如果是⾮空的树形结构，那么拥有⼀个唯⼀的起始节点称之为root（根节点）

2. 除了根节点外，其他节点都有且仅有⼀个“⽗节点”；除此外这些节点还都可以有0到若⼲个“⼦节点”

3. 树中的所有节点都必须可以通过根节点经过若⼲次后继操作到达

4. 节点之间不会形成循环关系，即任意⼀个节点都不可能从⾃⾝出发，经过不重复的径路再回到⾃⾝。说明了树形结构内部蕴含着⼀

种“序”，但是不是线性表那样的“全序”

5. 从树中的任意两个节点出发获取到的两个任意⼦树，要不两者⽆交集，要不其中⼀者是另⼀者的⼦集

限定到⼆叉树，⼆叉树就是任意⼀个节点⾄多只能有两个⼦节点的树形结构。也就是说，某个节点的⼦节点数可以是0,1或2。 由于可以

有两个⼦节点，所以区别两个⼦节点可以将其分别定义为左⼦节点和右⼦节点。但是需要注意的是，若⼀个节点只有⼀个⼦节点，那么也必

须明确这个⼦节点是左⼦节点还是右⼦节点。不存在“中⼦节点”或者“单⼦节点”这种表述。

由于上述规则对所有节点都⽣效，所以⼆叉树也是⼀个递归的结构。事实上，递归就是⼆叉树⼀个⾮常重要的特点，后⾯还会提到很多

通过递归的思想来建⽴的例⼦。

对于左⼦节点作为根节点的那颗⼆叉树被称为相对本节点的左⼦树，右⼦树是同理。

■ 基本概念

空树 不包含任何节点的⼆叉树，连根节点也没有

单点树 只包含⼀个根节点的⼆叉树是单点树

⾄于兄弟关系，⽗⼦关系，长辈后辈关系是⼀⾔既明的就不说了。

树中没有⼦节点的节点被称为树叶（节点），其余的则是分⽀节点。⼀个节点的⼦节点个数被称为“度数”。正如上所说，⼆叉树任意节

点的度数取值可能是0，1或2。

节点与节点之间存在关联关系，这种关联关系的基本长度是1。通过⼀个节点经过若⼲个关联关系到达另⼀个节点，经过的这些关联关

系合起来被称为⼀个路径。路径的长度等于关联关系的个数。为了统⼀，通常把⼀个节点到其⾃⾝的路径长度为0。

⼆叉树是⼀种层级结构，某个节点所在的层数是根节点到达此节点路径的长度。因此根节点所在第0层。所在第k层的节点，⼦节点在第

k+1层。

⼀棵树可以取到的最⼤的路径长度称为树的⾼度or深度。单点树的⾼度为0。

■ 基本性质

下⾯列出⼀些⼆叉树的基本性质，证明就不给了，能⼒有限…

⾮空⼆叉树的第i层最多可以有2^i个节点。⾼度为h的⼆叉树最多可以有2^(h+1) - 1个节点。

对于任何⾮空⼆叉树，若其叶节点个数为m，度数为2的节点个数为n。那么m = n + 1。虽然懒得抄证明了，但是可以感觉到，加上去的

这个1，如果算在根节点上是⽐较合理的。

● 满⼆叉树和扩充⼆叉树

所有分⽀节点的度数都是2的⼆叉树是满⼆叉树。需要强调是分⽀节点。即最终叶节点并⾮⼀定要完全是2^n个那么完整的那种。

对于⼀个⼆叉树T，添加上所有有必要的叶节点，使得T中的所有节点（包括分⽀和叶节点）的度数都变成2，从⽽T变成⼀个满⼆叉

树。得到的这个满⼆叉树相对原树T⽽⾔就是⼀个T的扩充⼆叉树。被新添加上去的这些叶节点被称为外部节点，新扩充⼆叉树中的所有分⽀

节点（包含原树的分⽀节点和叶节点）被称为内部节点。根据上述基本性质的第三条，可知外部节点个数m = 内部结点个数n + 1。

● 完全⼆叉树

对于⾼度为h的⼆叉树T，若0到h-1层所有层都符合，i层的节点个数是2^i个；且第h层节点数⼩于2^h个时，所有h-1层度数为1的节点的

⼦节点都是左⼦节点的话，那么就称T为完全⼆叉树。需要注意区别完全⼆叉树和满⼆叉树之间的区别。⽐如下⾯这个就是⼀个完全⼆叉树

但不是满⼆叉树。

第0层有1个，第1层有2个节点，是完全⼆叉树。但是红圈中的节点度数是1，不符合满⼆叉树要求。

对于总含有n个节点的完全⼆叉树，其⾼度h是log2n向下取整。由于完全⼆叉树在0到h-1层为⽌的完整性，有⼀些很好的性质。⽐如从

根节点开始，把根节点标号为0，之后按从上到下，从左到右依次给树中的所有节点编号，那么可以看到对于编号为i的节点，

1. 其⽗节点的编号是(i-1)/2，这是int除法，⾃动向下取整

2. 若2 * i + 1 < n则其左⼦节点的序号是2 * i + 1，否则没有左⼦节点

3. 若 2 * i + 2 < n则其右⼦节点的序号是2 * i + 2，否则没有右⼦节点

也是因为其完整性，可以将⼀个完整⼆叉树⽐较好地投影成⼀个连续表。如按照上⾯描述的规则那样对树节点进⾏编号的话，那么在表

中仅凭下标就可以轻松得查找到某个特定节点在树中的⽗⼦节点。

从直观的图上来说，完整⼆叉树是很丰满的图形。⼀个⼆叉树越是丰满完整（实际上就是指其分⽀节点中度数为1的节点占⽐⽐较

低），其树的最长路径越接近O(log n)的。相反越是单薄的，最长路径接近O(n)的。极端的情况，当所有的节点都只有⼀个⼦节点，那么⼆

叉树其实就变成了⼀个连续表了。

■ ⼆叉树的抽象数据类型

如果构造⼀个⼆叉树类，可能会需要下⾯这些⽅法和属性：

class BinTree:

BinTree(data,left,right) # 构造⼆叉树

is_empty() # 判断是否是空⼆叉树

num_nodes() # 返回总节点数

data() # 获取根节点数据

left() # 获取左⼦树

right() # 获取右⼦树

setLeft(binTree) # 设置左⼦树为指定树对象

setRight(binTree) # 设置右⼦树为指定树对象

traversal() # 遍历树⽤的⽅法，⽐如python实现就可以让它返回⼀个迭代器

作为⼀个数据结构，⼆叉树的本职⼯作是存储数据。树的节点就是拿来存储数据⽤的。因为根节点在⼀个树⾥处于⽐较特殊的地位，所

以⼀般⽤树的根节点作为特征来指定⼀颗树。根节点作为获取⼆叉树中数据的⼊⼝⽽存在。除了根节点，组成⼀棵树的另外两部分就是左⼦

树和右⼦树。这三者组合起来就可以完整地描述⼀棵树了，这也是为什么构造⽅法中采⽤了这三个参数，并且类中给出了这三个属性各⾃的

get和set⽅法。

除去这些⽅法外，最关键的⽅法就是如何遍历⼆叉树了。

由于⼆叉树是个⼆维结构，遍历时到达⼀个节点之后我们可能有两个前进⽅向，因此遍历⼆叉树分成两种模式，分别是深度优先和⼴度优先。

● 深度优先遍历

深度优先表⽰，从根节点出发遍历时优先向⼀个叶节点⽅向遍历，不撞南墙不回头。

上⾯说过了⼀个⼆叉树有三个要素即根节点，左右⼦树。在遍历到⼀个特定的位置时，这三个要素先后如何处理是个问题。⾸先需要说

明，左⼦树和右⼦树可以经过树中⼼线的镜⾯对称从⽽互换，因此暂规定左⼦树总是先于右⼦树处理。另左右⼦树分别为L,R，根节点为D

的话。那么遍历顺序有下⾯三种可以选择：

DLR 被称为先根序

LDR 称为中根序，也称为对称序

LRD 称为后根序

选定任意⼀种顺序，从根节点开始判断，当L或者R存在时则转⼊相关⼦树判断，否则进⾏顺序规定的下⼀个对象。只要整个遍历过程

选定了⼀个顺序不变化，那么最终就可以⼀个不多也不少地遍历完树的所有节点。

针对下⾯这个⼆叉树实例，根据不同的遍历顺序可以得到三个不同的节点序列：

按照DLR顺序得到的是 A B D H E I C F J K G 序列。这个序列对这个⼆叉树来说也被称为是先根序列

按照LDR顺序得到的是 D H B E I A J F K C G 序列。这个被称为对称序列。

按照LRD顺序得到的是 H D E I B J K F G C A 序列。这个被称为后根序列。在尝试写出序列的过程中就可以感受到，其实⼆叉树的遍历

是具有很强的递归⾊彩思想的。⼆叉树本⾝就可以视为将两个⾃⾝类对象作为属性的类实例。因此递归在所难免。 同样的⼀棵树，我们可以根据遍历顺序的不同⽽写出多种不同的序列。所以得到⼀个序列之后并不能还原出树来。事实上，告诉⼀个序

列并且告诉这个序列的遍历顺序，也⽆法还原树。但是可以证明，如果知道了⼀棵树的对称序列，且知道另⼀个序列的话，是可以唯⼀确定⼀个⼆叉树的。

● 宽度优先遍历

宽度优先遍历时，由于来到⼀个⼦树之后不急着马上处理这个⼦树⽽是回头看还有哪些平级的⼦树。所以宽度优先的遍历不能⽤递归来

做。相对的，我们可以设计⼀个栈，把相关同级的⼦树都压⼊栈，确认已经没有同级的⼦树之后再从栈中取出各个⼦树来处理。

按照宽度优先的顺序遍历得到的序列是层次序列，⽐如上⾯给出的⽰例树，其层次序列是A B C D E F G H I J K，和我们习惯性的编号

顺序⼀致。

很多时候，遍历的⽬的并不在于真的要遍历所有节点，⽽是为了搜索我们⼀个想要的节点。根据树的形状以及实际数据分布不同⽽采⽤

的不同的遍历模式&遍历顺序，有可能会给最终搜索的效率带来很⼤的影响。（⽐如我们想要找上例中的J节点，采⽤两种模式的四种顺

序，J每次出现的时间点都不同）选择⼀个最优的遍历顺序有时候是⾼效解决问题的关键。

■ Python的⼆叉树实现

创建节点类，再据此实现树类，虽然可⾏，但是有些繁琐。⽬前我们仅为了做⼀些简单的演⽰，所以借⽤⼀些现成的数据类型也可以实

现简单的⼆叉树。⽐如⼀个多重嵌套的列表。规定⼀棵树是⼀个三元列表tree。tree[0]保存根节点的值，tree[1]和tree[2]分别是左⼦树和右⼦

树，分别也都可能是三元列表。当没有某个⼦树的时候，就⽤None来代替。

于是我们就可以获得⼀个简单的树了：

['A',

['B',

['C',None,None],

['D',None,None]

],

['E',None,

['F',None,None]

]

]

叶节点是[xxx,None,None]，⽽分⽀节点后两个值中⾄少有⼀个不为None。这整个嵌套列表的维度 = 树的⾼度 + 1。

● 利⽤这个⼆叉树进⾏简单应⽤ —— 表达式⼆叉树

对于简单的数学表达式（⽤加减乘除，⼤于⼩于号等⼆元运算符以及相关数字量组成的表达式），由于每个运算符都是⼆元的，所以表

达式其实是可以很好地对应到⼀颗⼆叉树的。⽽且这是⼀棵满⼆叉树。树中所有叶节点都是数字量，所有分⽀节点加上根节点是运算符。⽐

如以这个算式为例：

( a - b ) * ( c / d + e )　总共包含了5个数字量和4个⼆元运算符（这⾥姑且先不管括号的存在）。在这种情况下，可以将这个表达式转化成⼀个⼆叉树如下：

可以看到，⼆叉树由于其⼆维的层级结构，天然就带来了括号的作⽤，所以括号可以不在树中体现，就能构造出和算数表达式相对应的

⼆叉树了。

然后再来看看如何遍历这棵树。⾸先我们只考虑深度优先模式，然后如果采⽤中根序遍历，得到的是a - b * c / d + e，基本上就是去掉括

号的原表达式。但是也可以看到，由于遍历的过程将⼆维信息⼀维化，原本的⼀些计算顺序的信息丢失。所以中根序并不是好的遍历表达式

⼆叉树的办法。

采⽤前根序得 * - a b + / c d e，采⽤后根序得到 a b - c d / e + * 。这两者分别是之前在学习栈的时候提到过的，算数表达式的前缀表达

法和后缀表达法。根据之前的了解，两者⽆需括号，是⾃带了计算顺序信息的。

在得到⼀个表达式⼆叉树之后，我们当然可以得出其后根序列，然后根据之前说过的利⽤栈的⽅法来求表达式的值。另⼀⽅⾯，着眼于

⼆叉树整体，采⽤递归的办法也是可⾏的。这⾥的递归思想⼤概是这样的: 到达⼀个树的根节点时，判断其两个分⽀是否都是叶节点了。如