这篇博客来聊一下二叉树。呆萌数据结构系列,终于开始了树型结构的部分。这篇文章你能够学到的内容有 树,有哪些应用二叉树的结构什么是满二叉树什么是完全二叉树二叉树的遍历方式二叉树的构建。二叉树是很基本的结构,在此基本上,会有很多很多变种,变成各种各样的树,理解了二叉树,对于后面学习其他更复杂的树型结构,会有很大的帮助。

这篇文章首先理解文字上的内容,不要管代码,对二叉树的结构,操作,理解原理,最后再看代码。

好了,下面开始吧。

树,有哪些应用

现在学习的目的,已经不是为了考试,而是为了能够用来做一些事情。对于我们来说,知识只有用起来,才是有意义的,所以,我们先说一下树型结构的一些应用。咦?为什么不是二叉树的应用呢,因为很多应用,都不是单纯地使用二叉树来实现的,而是在此基础上,使用了它的变种,所以我们这里直接说一下树型结构的一些应用。

我们使用各种各样的数据结构,本质上似乎就是为了更方便或更高效地去组织数据,操作数据。我们平时用的搜索引擎,当你输入要搜索的内容时,可能在输入了前几个字,下面就已经出现了我们想要的结果,其实背后,就是用了树型结构,才能在这样庞大的数据中,找到与我们输入内容匹配的结构。

我们手机中常用的电话薄,也是这个原理。当你找一个联系人时,输入第一个字,例如李,可能下面的结构是李四,李五,李六,但是输入第二个字时,结果就会更精确。

我们平时用的压缩软件,其数据压缩算法,也离不开树型结构。

操作系统中的文件系统,以及我们使用的数据库软件,也是树型结构的应用。

二叉树的结构

二叉树是由一个一个节点组成,每个节点,有数据部分,以及两个节点指针,一个指向左子树,一个指向右子树。二叉树每一个节点,最多拥有两个子树。就像下面中的图(图中的数字可以理解为要存储的数据)。另外,二叉树的分支,也就是左右子树,是具有左右次序的,不能随意颠倒。

p001701_Binary-Tree

什么是满二叉树

满二叉树就除了最后一层,每一个节点,都拥有左右两个子树,没有空缺。

p001702_Full-Binary-Tree

什么是完全二叉树

在理解了满二叉树的基础上,才能理解完全二叉树。完全二叉树要满足两个条件。首先,如果不看最后一层,那这棵树是满二叉树。其次,最后一层,要尽可能的往左靠,中间不能有空缺。什么意思呢?我们看一张图。

p001703_Complete-Tree

上图中,左边的图是一个完全二叉树。如果去掉最后一层,那这棵树是满二叉树,满足。最后一层,即使缺少了一个节点,但是所有的节点都是尽可能地往左靠了,所以,也满足第二个条件。

而第二个图,不是完全二叉树。首先第一个条件就不满足。其实,最后一层的节点也不是尽可能地往左靠。什么叫尽可能得往左靠呢,如果 B 节点作为 A 节点的左子树,那就叫做尽可能地往左靠了。

二叉树的遍历方式

树的遍历(不限于二叉树),有广度优先遍历,和深度优先遍历。而深度优先遍历,分为前序遍历,中序遍历,后序遍历。

我们以下面这张图为例子,分别说一下这几种遍历方式。

p001704_Full-Binary-Tree

  • 广度优先遍历

    广度优先遍历,其实就是一层一层地遍历,所以又可以称为层次遍历,会先访问离根节点最近的节点。按照广度优先遍历,上面的树中节点访问顺序是这样的。

    8,4,12,2,6,10,14,1,3,5,7,9,11,13,15

  • 深度优先索索
    深度优先搜索,通常采用递归的形式来进行。这里我们用简单的代码去描述,会比文字描述更直观。

    • 前序遍历
      前序遍历的顺序是先访问根节点,然后再访问子树。

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      void pre_order_traversal(Node root) {
      // TODO:操作当前节点

      // 如果左子树不为空,则递归处理左子树
      if(root.left != null){
      pre_order_traversal(root.left);
      }

      // 如果右子树不为空,则递归处理右子树
      if(root.right != null){
      pre_order_traversal(root.right);
      }
      }
    • 中序遍历
      中序遍历的顺序是先访问左(右)子树,然后访问根,然后访问右(左)子树。

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      void in_order_traversal(Node root) {
      // 如果左子树不为空,则递归处理左子树
      if(root.left != null){
      in_order_traversal(root.left);
      }

      // TODO: 处理当前节点

      // 如果右子树不为空,则递归处理右子树
      if(root.right != null){
      in_order_traversal(root.right);
      }
      }
    • 后序遍历
      后序遍历的顺序是先访问子树,然后再访问根。

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      void post_order_traversal(Node root){
      // 如果左子树不为空,则递归处理左子树
      if(root.left != null){
      post_order_traversal(root.left);
      }

      // 如果右子树不为空,则递归处理右子树
      if(root.right != null){
      post_order_traversal(root.right);
      }

      // TODO: 处理当前节点
      }

    仔细看上面的代码已经注释,可以发现三种遍历方式都是递归的方式,基本类似,主要区别,是 什么时候处理当前节点

按层次顺序构建上图中的二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
import queue

class Node:
def __init__(self, data):
self.data = data
self.left = self.right = None

# 二叉树构建函数(按层次构建)
def construct_in_level_order(data_queue):
if data_queue is None or data_queue.empty():
return None

# 创建 Root 节点
root = Node(data_queue.get())

# 创建一个队列,用于按层来构建二叉树
node_queue = queue.Queue()

# 将 Root 节点先放入节点队列中
node_queue.put(root)

while not node_queue.empty():
# 从队列中拿出一个节点作为当前节点
node = node_queue.get()

# 创建当前节点的左子树节点
left_node = None
if not data_queue.empty():
left_node = Node(data_queue.get())
node.left = left_node

# 创建当前节点的右子树节点
right_node = None
if not data_queue.empty():
right_node = Node(data_queue.get())
node.right = right_node

if left_node is not None:
node_queue.put(left_node)

if right_node is not None:
node_queue.put(right_node)

return root

# 二叉树层次遍历函数
def level_order_traversal(root):
q = queue.Queue()

if root is not None:
q.put(root)

while not q.empty():
node = q.get()
if node.left is not None:
q.put(node.left)
if node.right is not None:
q.put(node.right)
print(node.data)

if __name__ == '__main__':
data_queue = queue.Queue()
arr = [8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15]
for item in arr:
data_queue.put(item)

root = construct_in_level_order(data_queue)
level_order_traversal(root)

如何删除一个节点

删除一个节点,就是将某一个节点从整个树中踢除掉,重要的是,踢除某个节点后,需要调整整棵树的结构,这个要根据不同的规则去做。最简单的方法就是,删除某一个节点后,让左子树或右子树,上升成为替换删除掉的节点,改变对应的指针。具体的代码实现,我们将在后面其他树型结构的文章中介绍。

更多内容

二叉树的结构我们先介绍到这里,后面还会有更多更复杂的关于树的结构,我们慢慢来,循序渐进。

还有一些关于二叉树很不错的文章,推荐给大家