算法--解决二叉树遍历问题

第一 实现树的结构

class Node():
    # 构造函数，初始化节点对象，包含数据和左右子节点
    def __init__(self, data=None):
        self.data = data  # 节点存储的数据
        self.left = None  # 左子节点，默认为None
        self.right = None  # 右子节点，默认为None

    # 设置节点数据的方法
    def set_data(self, data):
        self.data = data  # 将传入的数据赋值给节点的data属性

    # 获取节点数据的方法
    def get_data(self):
        return self.data  # 返回节点的data属性

    # 设置左子节点的方法
    def set_left(self, node):
        self.left = node  # 将传入的节点赋值给当前节点的left属性

    # 获取左子节点的方法
    def get_left(self):
        return self.left  # 返回当前节点的left属性，即左子节点

    # 设置右子节点的方法
    def set_right(self, node):
        self.right = node  # 将传入的节点赋值给当前节点的right属性

    # 获取右子节点的方法
    def get_right(self):
        return self.right  # 返回当前节点的right属性，即右子节点

if __name__ == '__main__':
    # 创建根节点，数据为'a'
    root_node = Node('a')
    # 创建左子节点，数据为'b'
    left_node = Node('b')
    # 创建右子节点，数据为'c'
    right_node = Node('c')
    # 将左子节点设置到根节点的左子节点位置
    root_node.set_left(left_node)
    # 将右子节点设置到根节点的右子节点位置
    root_node.set_right(right_node)
    # 打印根节点的数据，左子节点的数据和右子节点的数据
    print(root_node.get_data(), root_node.get_left().data, root_node.get_right().data)

第二  二叉树递归遍历

#实现树的递归遍历(前、中、后以及层次的遍历)，首先定义实现树结构的类Node。编写三个函数proorderO)、posorder0)和mid order0)分别实现先序遍历后序遍历和中序遍历。from collections import dequeclass Node():# 构造函数，初始化节点对象，包含数据和左右子节点def __init__(self, data=None, left=None, right=None):self.data = data  # 节点存储的数据self.left = left  # 左子节点，默认为Noneself.right = right  # 右子节点，默认为None# 前序遍历：先访问根节点，然后递归遍历左子树，最后递归遍历右子树def pro_order(self):print(self.data)  # 访问根节点if self.left:  # 如果存在左子节点，则递归遍历左子树self.left.pro_order()if self.right:  # 如果存在右子节点，则递归遍历右子树self.right.pro_order()# 中序遍历：先递归遍历左子树，然后访问根节点，最后递归遍历右子树def mid_order(self):if self.left:  # 如果存在左子节点，则递归遍历左子树self.left.mid_order()print(self.data)  # 访问根节点if self.right:  # 如果存在右子节点，则递归遍历右子树self.right.mid_order()# 后序遍历：先递归遍历左子树，然后递归遍历右子树，最后访问根节点def pos_order(self):if self.left:  # 如果存在左子节点，则递归遍历左子树self.left.pos_order()if self.right:  # 如果存在右子节点，则递归遍历右子树self.right.pos_order()print(self.data)  # 访问根节点# 层序遍历：使用队列按层次顺序访问节点def row_order(self):queue = deque([self])  # 初始化队列，将根节点加入队列while queue:  # 当队列不为空时，进行遍历current_tree = queue.popleft()  # 从队列前端取出节点print(current_tree.data)  # 访问节点if current_tree.left is not None:  # 如果存在左子节点，则加入队列queue.append(current_tree.left)if current_tree.right is not None:  # 如果存在右子节点，则加入队列queue.append(current_tree.right)# 自定义遍历：使用栈按特定顺序访问节点def custom_order(self):stack = [self]  # 初始化栈，将根节点加入栈while stack:  # 当栈不为空时，进行遍历node = stack.pop()  # 从栈末端取出节点print(node.data)  # 访问节点if node.right is not None:  # 如果存在右子节点，则加入栈stack.append(node.right)if node.left is not None:  # 如果存在左子节点，则加入栈stack.append(node.left)# 主程序入口
if __name__ == '__main__':# 创建二叉树tree = Node('A', Node('B', Node('D'), Node('E')), Node('C', Node('F'), Node('G')))print("自定义遍历:")tree.custom_order()  # 执行自定义遍历

返回结果：

第一

第二