二叉树遍历算法

短命女 2023-06-10 10:23 162阅读 0赞

### 文章目录 ###

*   *   *  前言
         *  二叉树遍历方法
         *   *  前序遍历
             *  中序遍历
             *  后序遍历
             *  按层遍历
         *  代码

### 前言 ###

二叉树的遍历是指从根节点触发，按照某种次序依次访问二叉树中所有的节点。  
由于不同于线性结构，二叉树达到一个节点需要选择两个子节点的先后顺序，所有遍历方式有很多。

### 二叉树遍历方法 ###

二叉树遍历方式有很多，所以如下介绍的遍历方式，我们约定从左往右进行遍历。  
我们需要遍历的树结构如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM2MzI3NTU_size_16_color_FFFFFF_t_70]  
下面的遍历算法用Python实现，不会Python的同学不用担心，因为算法逻辑很简单。  
先看下我们的节点对象的定义：

class TreeNode:
    
        def __init__(self, data) -> None:
            self.data = data  # 数据
            self.left = None  # 左子节点
            self.right = None  # 右子节点

#### 前序遍历 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM2MzI3NTU_size_16_color_FFFFFF_t_70 1]  
前序遍历算法，采用递归，先判断节点是否为空，如果为空则返回。先打印当前节点内容，然后依次递归所有左子节点，再依次递归所有右子节点。遍历顺序为：ABDGHCEIF  
递归算法如下：

def pre_order_traverse(_binary_tree):
        """ 前序遍历 :param _binary_tree: 二叉树 :type _binary_tree: TreeNode """
        if _binary_tree is None:
            return
        print(_binary_tree.data, end=',')
        pre_order_traverse(_binary_tree.left)
        pre_order_traverse(_binary_tree.right)

#### 中序遍历 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM2MzI3NTU_size_16_color_FFFFFF_t_70 2]  
中序遍历算法，采用递归，先判断节点是否为空，如果为空则返回。先依次递归所有左子节点，然后打印当前节点内容，再递归所有右子节点。  
遍历顺序为：GDHBAEICF  
递归算法如下：

def in_order_traverse(_binary_tree):
        """ 中序遍历 :param _binary_tree: 二叉树 :type _binary_tree: TreeNode """
        if _binary_tree is None:
            return
        in_order_traverse(_binary_tree.left)
        print(_binary_tree.data, end=',')
        in_order_traverse(_binary_tree.right)

#### 后序遍历 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM2MzI3NTU_size_16_color_FFFFFF_t_70 3]  
后序遍历算法，采用递归，先判断节点是否为空，如果为空则返回。先依次递归所有左子节点，再递归所有右子节点，最后打印当前节点内容。  
遍历顺序为：GHDBIEFCA  
递归算法如下：

def post_order_traverse(_binary_tree):
        """ 后序遍历 :param _binary_tree: 二叉树 :type _binary_tree: TreeNode """
        if _binary_tree is None:
            return
        post_order_traverse(_binary_tree.left)
        post_order_traverse(_binary_tree.right)
        print(_binary_tree.data, end=',')

#### 按层遍历 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM2MzI3NTU_size_16_color_FFFFFF_t_70 4]  
按层遍历算法，我们将每层所有节点作为列表，传入函数进行递归，先传入列表是否为空，如果为空则返回。声明一个下一层级的子集列表。依次循环当前传入的节点列表，并打印节点数据，将当前节点左节点添加到下一层级的子集列表中，然后添加右节点。  
最终遍历顺序为：ABCDEFGHI  
递归算法如下：

def layer_order_traverse(_layer_nodes):
        """ 按层遍历 :param _layer_nodes: 当前层节点集合 :type _layer_nodes: list """
        if _layer_nodes is None or len(_layer_nodes) == 0:
            return
        _childs = []  # 子集
        for _node in _layer_nodes:  # 遍历传入的当前层所有节点
            print(_node.data, end=',')
            if _node.left:
                _childs.append(_node.left)
            if _node.right:
                _childs.append(_node.right)
        layer_order_traverse(_childs)

### 代码 ###

class TreeNode:
    
        def __init__(self, data) -> None:
            self.data = data  # 数据
            self.left = None  # 左子节点
            self.right = None  # 右子节点
    
    
    def fixed_tree():
        """ 返回固定二叉树结构 :return: """
        a = TreeNode('A')
        b = TreeNode('B')
        c = TreeNode('C')
        d = TreeNode('D')
        e = TreeNode('E')
        f = TreeNode('F')
        g = TreeNode('G')
        h = TreeNode('H')
        i = TreeNode('I')
        a.left = b
        a.right = c
        b.left = d
        c.left = e
        c.right = f
        d.left = g
        d.right = h
        e.right = i
        return a
    
    
    def pre_order_traverse(_binary_tree):
        """ 前序遍历 :param _binary_tree: 二叉树 :type _binary_tree: TreeNode """
        if _binary_tree is None:
            return
        print(_binary_tree.data, end=',')
        pre_order_traverse(_binary_tree.left)
        pre_order_traverse(_binary_tree.right)
    
    
    def in_order_traverse(_binary_tree):
        """ 中序遍历 :param _binary_tree: 二叉树 :type _binary_tree: TreeNode """
        if _binary_tree is None:
            return
        in_order_traverse(_binary_tree.left)
        print(_binary_tree.data, end=',')
        in_order_traverse(_binary_tree.right)
    
    
    def post_order_traverse(_binary_tree):
        """ 后序遍历 :param _binary_tree: 二叉树 :type _binary_tree: TreeNode """
        if _binary_tree is None:
            return
        post_order_traverse(_binary_tree.left)
        post_order_traverse(_binary_tree.right)
        print(_binary_tree.data, end=',')
    
    
    def layer_order_traverse(_layer_nodes):
        """ 按层遍历 :param _layer_nodes: 当前层节点集合 :type _layer_nodes: list """
        if _layer_nodes is None or len(_layer_nodes) == 0:
            return
        _childs = []  # 子集
        for _node in _layer_nodes:  # 遍历传入的当前层所有节点
            print(_node.data, end=',')
            if _node.left:
                _childs.append(_node.left)
            if _node.right:
                _childs.append(_node.right)
        layer_order_traverse(_childs)
    
    
    if __name__ == '__main__':
        binary_tree = fixed_tree()
        print('前序遍历：', end='')
        pre_order_traverse(binary_tree)
        print()
        print('中序遍历：', end='')
        in_order_traverse(binary_tree)
        print()
        print('后序遍历：', end='')
        post_order_traverse(binary_tree)
        print()
        print('按层遍历：', end='')
        layer_order_traverse([binary_tree])
        print('\b' * 1, end='')

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM2MzI3NTU_size_16_color_FFFFFF_t_70]: /images/20230531/205c2cc6a5a546459a19a83d381a830e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM2MzI3NTU_size_16_color_FFFFFF_t_70 1]: /images/20230531/949ee0f3db0543d4bf470db63cac428f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM2MzI3NTU_size_16_color_FFFFFF_t_70 2]: /images/20230531/c7f7954b194444ed8089b4600e5507d2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM2MzI3NTU_size_16_color_FFFFFF_t_70 3]: /images/20230531/b5e0cfbd9d9b4a3fb18f44325a7920d0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM2MzI3NTU_size_16_color_FFFFFF_t_70 4]: /images/20230531/c74fb0d1ee484e41adea3b155ec3fdc7.png