python实现二叉树(一)

您所在的位置：网站首页 › 写出表达式的二叉树表示什么意思 › python实现二叉树(一)

python实现二叉树(一)

2024-07-14 16:24| 来源: 网络整理| 查看: 265

在数据结构概述的文章中说过，树结构是一种层次结构，也是非线性结构，它描述的是数据间“一对多”的关系，而树中的数据处理也是基于数据间父节点/子节点关系的。树的应用非常多，比如我们的计算机硬盘存储路径(以windows10为例)就可以看做一种树结构：

还有奴隶社会的等级制度；一个家族的家谱；某个公司的等级制度等等都是属于树结构。为什么树结构能够在数据结构中得到广泛的应用，因为分层组织结构在数据管理上的效率更高。

1. 树结构

1.1 树的定义

1.2 树结构的术语

1.3 树的分类

2. 二叉树的操作

2.1 二叉树的顺序存储结构

2.2 二叉树的链式存储结构

2.3 二叉树的插入

2.4 二叉树的遍历

2.4.1 前序遍历(根左右)

2.4.2 中序遍历(左根右)

2.4.3 后序遍历(左右根)

2.4.4 前中后三种遍历方式的小结

2.4.5 层序遍历(广度优先遍历)

2.4.6 遍历二叉树的应用

1. 树结构 1.1 树的定义

树(Tree)： $n(n \geq 0)$ 个节点构成的有限集合。当n = 0时，称为空树。对于任一棵非空树(n>0)，它具备以下性质：

树中有一个称为"根(Root)"的特殊节点，用r表示；其余节点可分为m(m>0)个互不相交的有限集 $T_{1}$ 、 $T_{2}$ ，..., $T_{m}$ ，其中每个集合本身又是一棵树，称为原来树的子树(SubTree)。如下图：

1.2 树结构的术语

树结构中有很多概念术语，在深入讨论树结构之前，我们先来介绍下跟树结构有关的术语。为了方便理解记忆，结合具体的一棵树结构来进行介绍，树结构如下：

节点：树中存储的项。上图中的A-L都是节点。

根节点：树中最顶端的节点。在树结构中只有它没有父节点。上图中的A为根节点。

节点的度：一个节点含有的子树的个数。根节点A的度为3；子节点C的度为1。

树的度：树中最大节点度。树中最大节点度为3(根节点A和子节点B的度均为3)，所以树的度为3。

子节点(孩子节点)：紧邻一个给定的节点之下，并且直接与给定节点相连的一个节点。一个节点可以有多个子节点。上图中B-L都是子节点。

父节点(双亲节点)：紧邻一个给定节点之上，且直接与给定节点相连的一个节点。一个节点只能有一个父节点。上图中A、B、C、D、H都是父节点。

兄弟节点：拥有共同父节点的子节点。上图中B、C、D是兄弟节点，E、F、G也是兄弟节点。

叶子节点：没有子节点的节点。或者说度为0的节点。上图中标绿的几个节点都是叶子节点。

内部节点：至少有一个子节点的节点。B、C、D、H都是内部节点。

边/分支：将一个父节点连接到其子节点的线。上图中的线就是边也称为分支。

后代(子孙)：以某节点为根的子树中任一节点都称为该节点的后代。E、F、G是节点B的后代；H、K、L是节点C的后代，B-L的所有节点都是根节点A的后代。

祖先：从根到该节点所经分支上的所有节点。节点D是I、J的祖先；根节点A是所有节点的祖先。

路径：连接一个节点与其后代节点边的序列。A-B-E和A-C-H-K都可以称作一条路径。

路径长度：路径中边的数目。路径A-B-E的路径长度为2；路径A-C-H-K的路径长度为3。

节点的层次：从根节点定义，根节点为第1层，根节点的子节点为第2层，依次类推。节点的层在上图中已经标出。

深度(高度)：叶子节点所在的最大层次。上图中树的深度为4。

森林：m棵不相交的树的集合。分别以B、C、D为根节点的子树组成的集合可以看做一个森林。

以上就是树结构的一些术语。

1.3 树的分类

树结构可以分为两大类：有序树和无序树。树中任意节点间没有顺序关系，那么称其为无序树，也称自由树。相对的，树中的任意节点有顺序关系，称其为有序树。在有序树中，子节点被视为按照从左到右的顺序排列，最左边的子节点称为第一个子节点，最右边的子节点称为最后一个子节点。我们研究的最多的树结构就是有序树。而有序树中最具代表性的树结构就是二叉树。

二叉树就是度不超过2的有序树结构。二叉树中的每个节点最多只能有两个分支，分别称为左子树和右子树。

根据二叉树的定义，会有如下两种极端的二叉树：

根据二叉树的形状，有以下几种常见的二叉树：

平衡二叉树：当且仅当任意节点的两棵子树的高度差不大于1的二叉树。

完全二叉树：除了最后一层外，其他层的节点数目都达到最大的二叉树。完全二叉树是平衡二叉树的一个特例，完全二叉树最后一层上的节点都是从左到右填充的。对于一颗k层的完全二叉树，其节点总数最少的情况是：最后一层只有一个节点，此时节点数目为： $\large 2^{k-1}$ ；其节点总数最多的情况是：最后一层节点数目达到最大，即满二叉树，此时节点数目为： $\large 2^{k} - 1$ 。对于节点数目为k的完全二叉树，其深度为： $\large log_{2}(k+1)$

满二叉树：所有层的节点数目均达到最大的二叉树。满二叉树是完全二叉树的一个特例。对于深度为k的满二叉树，其节点数目是： $\large 2^{k} - 1$ ；对于节点数目为k的满二叉树，其深度为： $\large log_{2}(k+1)$ 。

几种二叉树的结构图如下：

关于二叉树还有一个性质：二叉树中叶子节点数为 $\large n_{0}$ (因为叶子节点的度为0，所以下标为0)，度为2的节点数为 $\large n_{2}$ ，那么有： $\large n_{0} = n_{2} + 1$ 。

解析：关于上面等式关系的求解我们可以这样考虑。假设二叉树的总节点数为 $\large n$ ，因为二叉树的节点度只有0、1、2三种情况，假设节点度为0、1、2的节点数分别为： $\large n_{0}$ 、 $\large n_{1}$ 和 $\large n_{2}$ 。那么有 $\large {\color{Red} n = n_{0} + n_{1} + n_{2}}$ 。二叉树中节点度为1的节点有1条边连接到其子节点、节点度为2的节点有2条边连接到其子节点，假设二叉树有 $\large E$ 条边，那么 $\large E = n_{1} + 2n_{2}$ 。而我们知道，在二叉树中节点总数和边的数目有这样的关系： $\large {\color{Red} n = E + 1 = n_{1} + 2n_{2} + 1}$ 。联立红色的两个等式，容易得出 $\large n_{0} = n_{2} + 1$ 。

2. 二叉树的操作

在之前的文章中说过，数据结构的常见的存储方式有两种，一种是顺序存储(数组实现)；一种是链式存储(链表实现)。同样的，二叉树也可以通过以上两种方式进行存储。只有对数据结构进行了存储，才能继续下面的插入、删除、遍历和搜索等操作。

2.1 二叉树的顺序存储结构

二叉树的顺序存储是用数组来实现的，但是只有完全二叉树才能使用顺序存储。具体的存储方式如下：

那么对于一般二叉树结构的存储能用二叉树实现吗？不可以。因为在非完全二叉树中，一些层位于其他层之上，但是没有被节点填满。数组中的节点的相对计算，是基于能够将其索引乘以或除以2的假设，当一个以自上而下的方式排列的层级没有被填满的时候，无法做到这一点。如果非得用数组实现非完全二叉树的存储有没有其他办法呢？有。对于一般二叉树结构，需现将其转换为完全二叉树再进行顺序存储，如下图：

上述的方式存储非完全二叉树会造成空间的浪费，所以二叉树一般不采用顺序存储方式，因为并不是所有的二叉树都是完全二叉树。二叉树的数组实现比较少见，主要用于实现堆，在下文将详细进行说明。

2.2 二叉树的链式存储结构

二叉树的存储可以也使用链表实现，这也是常用的实现方式，每个节点包含三个域：Left、Data和Right，分别用来指向左子节点，存储数据项以及指向右孩子节点。一棵二叉树对应的链表存储如下：

二叉树节点结构的代码实现如下：

2.3 二叉树的插入

在上面的二叉树的链式存储中，我们定义了树节点。但是只有树节点是不够的，我们需要往节点里面添加元素，以构成一棵完整的二叉树，以便进行后续的遍历，删除、查找等操作。在数组和链表中，插入操作时时间复杂度是线性的，而在树结构中，插入操作是时间复杂度是对数级的。二叉树的构建，以及向树节点中添加元素的代码实现如下：

如果想向树中添加数据data = [1,2,3,4,5,6,7,8,9,10]，那么可使用如下代码：

通过以上的程序，就形成了如下的树结构：

实际上，上面的程序完成的是完全二叉树的构建。向二叉树节点中添加数据之后，我们就可以对二叉树进行遍历以获取树中的数据元素了。

2.4 二叉树的遍历

遍历是二叉树中最重要的操作之一，因为树的层次结构的特点，使得二叉树的遍历有着较高的效率。常见的二叉输的遍历有四种，分别是：前序遍历、中序遍历、后序遍历以及层序遍历。其中前序遍历、中序遍历和后序遍历又称为深度优先遍历，它会优先访问离根节点最远的节点；层序遍历又称为广度优先遍历，它会优先访问离根节点最近的节点。有关以上四种遍历方式，下面进行具体的说明。

2.4.1 前序遍历(根左右)

二叉树的前序遍历的步骤如下：

访问树的根节点----> 访问当前节点的左子树---->若当前节点无左子树，访问当前节点的右子树。

以上图为例，对其进行前序遍历的步骤为：

1. 先访问根节点，得到1

2. 访问根节点1的左子节点2，发现左子节点2还有左子节点4，继续向下访问，直到最后一个左子节点8，发现8为叶子节点。继续访问其父节点4的右子节点9，发现右子节点9为叶子节点。得到序列2、4、8、9.

3. 根据“根左右”的顺序，访问左子节点2的右子节点5，其有左子节点10，但是10为叶子节点，得到序列：5、10。至此二叉树的左子树遍历完毕，得到以下序列：1、2、4、8、9、5、10。

4. 以类似的方式访问根节点1的右子节点3，访问左子节点6，其为叶子节点，继续访问其兄弟节点的右子节点7。至此，二叉树的右子树遍历完毕，得到以下序列：3、6、7。至此整棵二叉树的遍历完毕。

得到的结果为：1、2、4、8、9、5、10、3、6、7。

实现前序遍历通常有两种方式：递归实现遍历和利用堆栈实现遍历。

利用递归的方法实现二叉树的前序遍历的代码如下：

除了递归的方式之外，遍历还可以通过堆栈的方式实现，其代码实现如下：

可以看到，程序运行结果和我们事先分析的结果一致。

2.4.2 中序遍历(左根右)

二叉树的前序遍历的步骤如下：

访问当前节点的左子树----> 访问根节点---->访问当前节点的右子树。

同样的，以上图为例，对其进行中序遍历的步骤为：

1. 按照“左根右”的顺序，先访问左子节点2，但是2还有左子节点4,4有左子节点8，而8为叶子结点，所以第1个访问的元素为8，接着访问节点8的父节点4，然后访问4的右子节点9.得到序列8、4、9。至此以4为根节点的左子树遍完毕。

2. 访问节点4的父节点2，访问其右子节点5，但是节点5有左子节点10，10为叶子节点，得到的序列为：2、10、5。至此，以2为根节点的左子树的遍历完毕，得到序列：8、4、9、2、10、5。

3. 访问整棵树的根节点1，访问其右子节点3，但其有左子节点6,6为叶子节点。所以最先访问的是6，接着访问其父节点3，再访问3的右子节点7，7为叶子节点，至此以1为根节点的右子树遍历完毕。得到序列1、6、3、7。至此整棵二叉树的遍历完毕。

得到的结果为：8、4、9、2、10、5、1、6、3、7

实现中序遍历同样有两种方式：递归实现遍历和利用堆栈实现遍历。

利用递归的方法实现二叉树的中序遍历的代码如下：

可以看到，中序遍历的递归实现和前序遍历的递归实现基本相同，只不过是把代码的顺序进行了一下调换，按照“左根右”的顺序，先对左子树调用递归函数，再打印当前节点的数据项，最后对右子树调用递归函数。

中序遍历的堆栈实现的代码如下：

最后得到的结果和我们事先分析得到的结果一致。

2.4.3 后序遍历(左右根)

二叉树的后序遍历步骤如下：

访问当前节点的左子树---->访问当前节点的右子树---->访问根节点

同样的，以上图为例，对其进行后序遍历的步骤：

1. 按照“左右根”的顺序，首先访问节点8，接着访问节点9，因为节点8和节点9都为叶子节点，所以接下来访问节点4。至此以2为根节点的左子树遍历完毕，接着遍历以2为根节点的右子树，首先访问节点10，接着访问节点5，最后访问节点2。至此，以1为根节点的左子树的遍历完毕，得到的序列为：8、9、4、10、5。

2. 遍历以1为根节点的右子树，首先访问节点6，接着访问节点7，因为节点6和节点7都是叶子节点，所以接下来访问节点3。最后访问整棵树的根节点1。至此，整棵树的遍历完毕。

得到的结果为：8、9、4、10、5、2、6、7、3、1

实现后序遍历同样有两种方式：递归实现遍历和利用堆栈实现遍历。

利用递归的方法实现二叉树的后序遍历的代码如下：