二叉树的遍历

T1Am0

发布于 2022-09-13 15:28:03

3420

发布于 2022-09-13 15:28:03

文章被收录于专栏：折腾小记

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

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

数组的遍历如下：

9	2	3	8	4	7

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))

那么，二叉树有哪些遍历方式呢？

从节点的位置关系来看的话，分为四种：

前序遍历
中序遍历
后序遍历
层序遍历

从更宏观的角度来讲的话，分为两大类：

广度优先遍历（层序遍历）
深度优先遍历（前序遍历、中序遍历、后序遍历）

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，放入栈中

1	2

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

1	2	4

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

1	5

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入队

2	3

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

3	4	5

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

4	5	6

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

5	6

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: