二叉树的遍历 python

红太狼 2022-05-17 02:17 172阅读 0赞

从二叉树的根节点出发，节点的遍历分为三个主要步骤：对当前节点进行操作（称为“访问”节点，或者根节点）、遍历左边子节点、遍历右边子节点。访问节点顺序的不同也就形成了不同的遍历方式。需要注意的是树的遍历通常使用递归的方法进行理解和实现，在访问元素时也需要使用递归的思想去理解。实际实现中对于前序和中序遍历可尝试使用递归实现。

按照访问根元素(当前元素)的前后顺序，遍历方式可划分为如下几种：

*  深度优先：先访问子节点，再访问父节点，最后访问第二个子节点。根据根节点相对于左右子节点的访问先后顺序又可细分为以下三种方式。  
    
    
     *  前序(pre-order)：先根后左再右
     *  中序(in-order)：先左后根再右
     *  后序(post-order)：先左后右再根
 *  广度优先：先访问根节点，沿着树的宽度遍历子节点，直到所有节点均被访问为止。

class TreeNode:
        def __init__(self, val):
            self.val = val
            self.left, self.right = None, None
    
    
    class Traversal(object):
        def __init__(self, root):
            self.traversal_path = list()
    
        def preorder(self, root):  # 前序遍历
            if root:
                self.traversal_path.append(root.val)
                self.preorder(root.left)
                self.preorder(root.right)
    
        def inorder(self, root):  # 中序遍历
            if root:
                self.inorder(root.left)
                self.traversal_path.append(root.val)
                self.inorder(root.right)
    
        def postorder(self, root):  # 后序遍历
            if root:
                self.postorder(root.left)
                self.postorder(root.right)
                self.traversal_path.append(root.val)