0x00 为什么要研究二叉树的遍历

在计算机中,遍历本身是一个线性操作。所以遍历同样具有线性结构的数组或链表,是一件轻而易举的事情。

数组的遍历如下:

923847
graph LR;
    9 --> 2;
    2 --> 3;
    3 --> 8;
    8 --> 4;
    4 --> 7;

链表的遍历如下,很简单,和链表的指向结构一致:

graph LR
    6((6)) --> 3((3))
    3((3)) --> 4((4))
    4((4)) --> 5((5))
    5((5)) --> 1((1))

反观二叉树,是典型的非线性数据结构,遍历时我们需要把非线性关联的节点转换成一个线性的序列。以不同的方式来遍历,得到的结果序列顺序也不同。

graph TB
    1((1)) --> 2((2))
    1((1)) --> 3((3))
    2((2)) --> 4((4))
    2((2)) --> 5((5))
    3((3)) --> 6((6))

那么,二叉树有哪些遍历方式呢?

从节点的位置关系来看的话,分为四种:

  1. 前序遍历
  2. 中序遍历
  3. 后序遍历
  4. 层序遍历

从更宏观的角度来讲的话,分为两大类:

  1. 广度优先遍历(层序遍历)
  2. 深度优先遍历(前序遍历、中序遍历、后序遍历)

0x01 深度优先遍历

1.前序遍历

口诀:根左右。具体来说就是每次遍历都遵循根节点、左子树、右子树的顺序。我们来举一个栗子:

graph TB
    1((1)) --> 2((2))
    1((1)) --> 3((3))
    2((2)) --> 4((4))
    2((2)) --> 5((5))
    3((3)) --> 6((6))

这科二叉树的遍历序列可以简化成如下:

graph LR
    1 --> 2
    2 --> 4
    4 --> 5
    5 --> 3
    3 --> 6

2.中序遍历

口诀:左根右。

graph TB
    1((1)) --> 2((2))
    1((1)) --> 3((3))
    2((2)) --> 4((4))
    2((2)) --> 5((5))
    3((3)) --> 6((6))    
graph LR
    4 --> 2
    2 --> 5
    5 --> 1
    1 --> 3
    3 --> 6

3.后序遍历

口诀:左右根。

graph TB
    1((1)) --> 2((2))
    1((1)) --> 3((3))
    2((2)) --> 4((4))
    2((2)) --> 5((5))
    3((3)) --> 6((6))
graph LR
    4 --> 5
    5 --> 2
    2 --> 6
    6 --> 3
    3 --> 1

4.代码环节

在我们熟悉了二叉树的几种遍历方式的思想后,能实现它才是最重要的,不能光说不做对吧。

递归式遍历
# 先声明一个节点类
class TreeNode:
  def __init__(self, data):
        self.data = data
    self.left = None
    self.right = None
    
  def create_binary_tree(input_list=[]):
    """
    构建二叉树
    :param input_list: 输入数列
    """
    if input_list is None or len(input_list) == 0:
      return None
    data = input_list.pop(0)
    if data is None:
      return None
    node = TreeNode(data)
    node.left = create_binary_tree(input_list)
    node.right = create_binary_tree(input_list)
    return node
  
  def pre_order_traversal(node):
    """
    前序遍历
    :param node: 二叉树节点
    """
    if node is None:
      return
    print(node.data)
    pre_order_traversal(node.left)
    pre_order_traversal(node.right)
    return node
  
  def in_order_traversal(node):
    """
    中序遍历
    :param node:    二叉树节点
    """
    if node is None:
       return
    in_order_traversal(node.left)
    print(node.data)
    in_order_traversal(node.right)
    return node
    
   def post_order_traversal(node):
      """
      后序遍历
      :param node: 二叉树节点
      """
      if node is None:
        return
      post_order_traversal(node.left)
      post_order_traversal(node.right)
      print(node.data)
      return node

然后我输入一个测试序列来检测是否符合结果:

my_input_list = [3, 2, 9, None, None, 10, None, None, 8, None, 4]
root = create_binary_tree(my_input_list)
print("前序遍历:")
pre_order_traversal(root)
print("中序遍历:")
in_order_traversal(root)
print("后序遍历")
post_order_traversal(root)

在这里,二叉树的构建流程如下,需要注意的是,列表中的None代表儿子节点为空的情况:

graph TB
    3((3)) --1--> 2((2))
    2((2)) --2--> 9((9))
    9((9)) --3--> None_1((None))
    9((9)) --4--> None_2((None))
    2((2)) --5--> 10((10))
    10((10)) --6--> None_3((None))
    10((10)) --7--> None_4((None))
    3((3)) --8--> 8((8))
    8((8)) --9--> None_5((None))
    8((8)) --10--> 4((4))
非递归式遍历(栈)

到这里所有代码的思想都是递归的方式进行遍历比较简单和顺畅,当然也可以利用这种数据结构来进行非递归遍历。我们还是利用这颗树来进行前序遍历说明:

graph TB
    1((1)) --> 2((2))
    1((1)) --> 3((3))
    2((2)) --> 4((4))
    2((2)) --> 5((5))
    3((3)) --> 6((6))    

1、首先遍历二叉树的根节点,放入栈中

1

2、遍历根节点1的左孩子节点2,放入栈中

12

3、遍历节点2的左孩子节点4,放入栈中

124

4、节点4没有左孩子也没有右孩子,出栈,回溯到其父节点2,2此时左孩子已访问,还有右孩子未访问,所以节点2出栈,她的右孩子节点5入栈。

15

5、节点五没有孩子节点,那么我们需要回溯,此时只有根节点1,节点5出栈,节点1出栈,节点1的右孩子节点3入栈。

3

6、节点三无左孩子,只有右孩子节点6,所以节点3出栈,节点6入栈

6

7、节点6无孩子,节点6出栈,此时栈为空,遍历结束。

def pre_order_teaversal_with_stack(node):
  stack = []
  while node is not None or len(stack) > 0:
    while node is not None:
      print(node.data)
      stack.append(node)
      node = node.left
    if len(stack) > 0:
      node = stack.pop()
      node = node.right

0x02 广度优先遍历

我们通过学习层序遍历来了解广度优先遍历是怎么回事。

层序遍历就是按照从根节点到叶子节点的层次关系,一层一层横向遍历各个节点。

graph TB
    1((1)) --> 2((2))
    1((1)) --> 3((3))
    2((2)) --> 4((4))
    2((2)) --> 5((5))
    3((3)) --> 6((6))    
graph LR
    1((1)) --> 2((2))
    2((2)) --> 3((3))
    3((3)) --> 4((4))
    4((4)) --> 5((5))
    5((5)) --> 6((6))

思路:

怎么样,是不是很简单呢?一层一层从向往下从左往右就可以了。可是在同一层的节点之间是没有直接关联的,那我们该怎么去代码实现呢,这里我们借助队列来辅助遍历。

详细遍历步骤如下:

1、根节点1进入队列

1

2、节点1出队,输出节点1,并得到节点1的左孩子节点2、右孩子节点3.让节点2、3入队

23

3、节点2出队,并得到其孩子节点4、5,节点4、5入队

345

4、节点3出队,并得到节点3的右孩子节点6,节点6入队

456

5、节点4出队,输出节点4,但是节点4没有孩子节点,所以没有新节点入队

56

6、节点5出队,输出节点5,但是节点5没有孩子节点,故无新节点入队

6

7、节点6出队,输出节点6,但是节点6没有孩子节点,故无新节点入队,此时队列为空,遍历结束

代码实现:

from queue import Queue

def level_order_traversal(node):
  queue = Queue()
  queue.put(node)
  while not queue.empty():
    node = queue.get()
    print(node.data)
    if node.left is not None:
      queue.put(node.left)
     if node.right is not None:
      queue.put(node.right)

Todo:

  • [ ] 二叉堆相关