常用数据结构之二叉树及树的四种遍历方式

悠悠 2022-12-11 03:26 14阅读 0赞

# 1.树 #

我们选择一种数据结构，不仅要能存储数据，而且要能体现数据之间的关系。目前数据主要有是三种关系一对一、一对多、多对多；之前我们讨论了线性表(数组、链表、栈、队列),其中的元素具有一对一的关系，通过元素之间左右相连来表达数据。为了表达具有**一对多**关系的数据，我们引进了树的概念。掌握树的关键就在于掌握这种不断延伸的**一对多**的关系。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dhb2JpbmcxOTkz_size_16_color_FFFFFF_t_70][]

下面我们介绍几种约定俗称的概念：

**节点**：树中的每一个元素称为节点

**父节点（双亲节点）**：产生其它节点的节点(即一对多中的一)，其往往是一种局部相对的关系，如图A、B、C、D中的A就是B、C、D的父节点

**子节点**：由其它节点产生的节点(即一对多中的多)，这也是一种局部相对关系，如图A、B、C、D中的B、C、D就是A的子节点

**根节点**：一棵树中最顶层节点(没有任何的父节点)，这是一种绝对的关系，相对于整棵树而言。如图中的A。

**叶子节点**：没有任何子节点的节点，这也是一种绝对的关系，相对于整棵树而言。如图中的K、L、F、G、M、I、J

**子树**：大树中所包含的小树，比如上面的树中B、E、F、K、L也构成了一棵树，称为子树。一棵树往往由多棵子树构成。

**空树**：没有任何节点的树

**度**：一个节点所拥有的子树数量，称为节点的度。即节点对应的分支树。各接节点中最大的度，称为树的度。

**层次**：从根节点到最远子节点，经过的节点数量。比如上图中的A、B、E、K为最远路径，该树的层次为4

**有序树和无序树**：兄弟节点之间是有顺序，称为有序树。否则是无序树。如上面的图就是一棵有序树。请注意这里的有序并不表示兄弟节点间的大小关系，更多表示的是这种树是对兄弟元素间**顺序敏感**的，如果兄弟节点以不同的顺序排列，那么就代表不同的树。举个例子：12和21是不同的，虽然都有1、2两个元素，但是它们对顺序是敏感的，那就是有序；1+2和2+1，如果单以结果来评价，那么它是无序的。还有，不管是有序还是无序都是针对兄弟节点而言，父子节点都是有序的。

**森林**：多棵不想交的树称为森林，如上图中以B、C、D各自为节点的子树组成的集合就是一个森林。多棵树组成一个森林，大树中又往往包含着森林。

**总结：**树是一种存储一对多数据的数据结构，因为其形状类似于一颗倒挂的树而得名。一棵树中的第一个元素，我们称之为根节点，没有子节点的元素称之为叶子节点。多棵不想交的树形成的集合叫做森林。森林中有多棵树，一棵树中也可以包含森林。这些都是为了统一，人们约定俗成的一些概念。最核心的我们需要掌握一对多这个点，可以把它当做树的种子，所有的形式都是由他发出。

# 2.二叉树定义 #

二叉树是目前应用最广泛的树结构，没有之一。在面试中往往也是必考题，送分题或者送命题！二叉不是二愣子的意思，而是指其描述的是**一对二**的数据关系。并且其必须是**有序树**！ 如下图所示，将其具体的表示出来就是图a的样子。每个节点最后有两个度(即两个分支)。可以看出每一层最多有![2^\{n-1\}][2_n-1]个节点。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dhb2JpbmcxOTkz_size_16_color_FFFFFF_t_70 1][]

# 3.满二叉树定义 #

所谓的满二叉树，就是说这棵二叉树满了(即所有的位置都有元素)。其实记住上面的就够了，如果实在要推的话还可以得到几个特性。1.叶子节点的个数为![2^\{n-1\}][2_n-1] ；2.除过最后一层，其它的节点数为![2^\{n-1\}][2_n-1]\-1；

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dhb2JpbmcxOTkz_size_16_color_FFFFFF_t_70 2][]

# 4.完全二叉树定义 #

完全二叉树就是一棵有点残缺的满二叉树，满二叉树是十全十美的话，它就是十全九美或十全八美、七美等。我们看到完全二叉树的最后一层节点并不要求填满。可以这么想满二叉树就是一种特殊的完全二叉树。

前几节中我们提到的[数据结构堆][Link 1]，就是一棵完全二叉树。再唠叨一下其节点计算逻辑，我们定义下标是从0开始，一直父节点的下标为i,那么左子节点下标为![2i+1][2i_1],右子节点下标为![2i+2][2i_2]。已知子节点下标为i，那么父节点的下标为![floor((i-1)/2)][floor_i-1_2]。

![20200928140017384.png][]

# 5.二叉树基本构造python实现 #

实现二叉树的方式有两种，顺序结构(一块固定大小的内存空间)和链式结构。本篇使用python中的列表来实现一个简单的二叉树。基本的思路：1.创建一个节点类，包含三个属性val(节点的值),left(左子节点),right(右子节点) 2.将所有的节点加入一个列表 3.遍历列表，找到每个元素的左右节点，并赋值。

class Node:
        def __init__(self,value,left=None,right=None):
            self.val = value
            self.left = left
            self.right = right
        def show(self):
            print(self.val,end='\t')

# 6.二叉树的前序遍历 #

前序遍历是一种从左往右的深度优先的遍历算法，遍历的顺序是根节点——>左子树——>右子树。之所以称为前序遍历是因为根节点是最先被遍历到的(个人理解)我们采用两种方式来实现。第一种递归方式,理解起来比较简单。如果是左子节点的话，输出当前节点并且继续穷尽其子节点。然后再穷尽右子节点。第二种方式是使用栈，先将右子节点入栈，再将左子节点入栈，弹出左子节点，继续遍历，直到没有左子节点再将右子节点弹出。

# 前序遍历 递归实现
        # 根节点——>左子节点——>右子节点
        def pre_order_recursion(self,Node):
            Node.show()
            if Node.left:
                self.pre_order_recursion(Node.left)
            if Node.right:
                self.pre_order_recursion(Node.right)
        # 前序遍历 使用栈来实现
        def pre_order(Node):
            result = []
            stack = [Node]
            while stack:
                node = stack.pop()
                if node:
                    result.append(node.val)
                    stack.append(node.right)
                    stack.append(node.left)
            return result

# 7.二叉树的中序遍历 #

中序遍历也是一种深度优先的算法，它的顺序是，左子树——>根节点——>右子树，因为跟节点是在中间被输出，所以称为中序遍历(个人理解)。具体的代码实现，我们只需要将前序遍历稍微的修改一下就可以了，具体如下。

def mid_order_recursion(Node):
        if Node.left:
            mid_order_recursion(Node.left)
        Node.show()
        if Node.right:
            mid_order_recursion(Node.right)

# 8.二叉树的后序遍历 #

后序遍历同样是一种深度优先算法，它的顺序是左子树——>右子树——>根节点，因为根节点最后输出所以称为后序遍历(个人理解)，具体代码如下，也是将上面的稍微修改即可。

def post_order_recursion(Node):
        if Node.left:
            post_order_recursion(Node.left)
        if Node.right:
            post_order_recursion(Node.right)
        Node.show()

# 8.二叉树的层次遍历 #

层次遍历是一种广度优先的算法，即从根节点开始从上到下，每一层从左到右遍历。实现的思路是，从上到下将当前层节点加入列表中，然后再将其左子节点、右子节点加入列表，不断进行循环。

def lever_order_recursion(Node):
        result = []
        current_node = [Node]
        while len(current_node) > 0:
            next_node = []
            for node_c in current_node:
                result.append(node_c.val)
                if node_c.left is not None:
                    next_node.append(node_c.left)
                if node_c.right is not None:
                    next_node.append(node_c.right)
            current_node = next_node
        return  result

# 总结： #

本篇中我们首先讲到了树的概念，一种表示一对多数据关系的数据结构；由它推出了二叉树，每个节点最多有两个子节点的有序树。然后介绍了两种特殊的二叉树：完全二叉树和满二叉树，满二叉树也是一种特殊的完全二叉树。最后介绍二叉树的构建，以及常用的四种遍历方式：前序遍历(先遍历根节点，再遍历左子树、最后是右子树)、中序遍历(先遍历左子树，再遍历根节点，最后遍历右子树)、后续遍历(先遍历左子树，再遍历右子树，最后遍历根节点)，这三种算法都是深度优先的算法。最后我们介绍了层次遍历，一种广度优先的算法，从上到下，从左到右的顺序遍历数据。本篇的代码均使用python实现。

# 茶话： #

推荐一首我偶像的诗给大家，能感动中国人民一千多年的文字，极为平淡的语言，却每每让人泪流满面。

十年生死两茫茫，不思量，自难忘**。**千里孤坟，无处话凄凉。纵使相逢应不识，尘满面，鬓如霜。

夜来幽梦忽还乡，小轩窗，正梳妆。相顾无言，惟有泪千行。料得年年肠断处，明月夜，短松冈。

《江城子·乙卯正月二十日夜记梦》苏轼

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dhb2JpbmcxOTkz_size_16_color_FFFFFF_t_70]: /images/20221123/fc9128a7a4544aed812a7920559afe18.png
[2_n-1]: https://private.codecogs.com/gif.latex?2%5E%7Bn-1%7D
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dhb2JpbmcxOTkz_size_16_color_FFFFFF_t_70 1]: /images/20221123/7babf4b3049449c1a0bc0ae6c360d017.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dhb2JpbmcxOTkz_size_16_color_FFFFFF_t_70 2]: /images/20221123/cf1f7c449f1b41708d6784818e50cd51.png
[Link 1]: https://blog.csdn.net/gaobing1993/article/details/108768791
[2i_1]: https://private.codecogs.com/gif.latex?2i&plus;1
[2i_2]: https://private.codecogs.com/gif.latex?2i&plus;2
[floor_i-1_2]: https://private.codecogs.com/gif.latex?floor%28%28i-1%29/2%29
[20200928140017384.png]: /images/20221123/9a7b23dc98c14fb6a8a750b52a3ac6c9.png