python二叉树的遍历

以下是Python中二叉树的遍历方法：

1. 深度优先遍历（DFS）：
深度优先遍历是一种先访问根节点，然后递归地访问左子树和右子树的方式。具体实现可以使用递归或者栈来实现。

class BinTree:
    # 构造函数
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

    # 深度优先遍历
    def dfs(self):
        if self is None:
            return []
        result = []
        result.append(self.data)
        if self.left:
            result += self.left.dfs()
        if self.right:
            result += self.right.dfs()
        return result

# 创建二叉树
tree = BinTree('A', BinTree('B'), BinTree('C', BinTree('D', BinTree('F'), BinTree('G')), BinTree('E', BinTree('H'), BinTree('I'))))

# 深度优先遍历
dfs_result = tree.dfs()
print(dfs_result)  # 输出：['A', 'B', 'C', 'D', 'F', 'G', 'E', 'H', 'I']

2. 宽度优先遍历（BFS）：
宽度优先遍历是一种逐层访问二叉树节点的方式。具体实现可以使用队列来实现。

from collections import deque

class BinTree:
    # 构造函数
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

    # 宽度优先遍历
    def bfs(self):
        if self is None:
            return []
        result = []
        queue = deque()
        queue.append(self)
        while queue:
            node = queue.popleft()
            result.append(node.data)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        return result

# 创建二叉树
tree = BinTree('A', BinTree('B'), BinTree('C', BinTree('D', BinTree('F'), BinTree('G')), BinTree('E', BinTree('H'), BinTree('I'))))

# 宽度优先遍历
bfs_result = tree.bfs()
print(bfs_result)  # 输出：['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I']