Python 树的深度优先和广度优先

落日映苍穹つ 2022-12-05 05:15 171阅读 0赞

""" 广度优先和深度优先 """
    
    # 树的节点，如果是第一个，则为root节点
    class Node:
        def __init__(self, value):
            self.val = value
            self.left = None
            self.right = None
    
    
    # 定义树
    class Tree:
        def __init__(self):
            self.root = None
    
        # 添加元素
        def add_element(self, node_value):
            node = Node(node_value)  # 生成 node
            if self.root is None:    # 判断root是否存在
                self.root = node
                return 
            queue = [self.root]      # 如果存在了，把root先放到队列queue中
    
            while True:
                pop_node = queue.pop(0)         # 不断从queue队列中pop出node
                if pop_node.left is None:       # 判断pop_node 左键点存在否
                    pop_node.left = node        # 如果不存在，将我们添加的node设置为这个元素的左节点，然后结束循环
                    return
                else:
                    queue.append(pop_node.left) # 如果存在左节点，将pop_node.left 放入queue,等待下一次循环时pop
    
                if pop_node.right is None:      # 同上，左节点如果存在，看看右节点是否存在。
                    pop_node.right = node
                    return
                else:
                    queue.append(pop_node.right)
    
        def bfs(self):
            """ 广度优先，利用队列，原理和添加元素时候一样 """
            if self.root is None:
                return
            queue = [ self.root ]
            while queue:
                pop_node = queue.pop(0)
                print(pop_node.val)
                if pop_node.left is not None:
                    queue.append(pop_node.left)
    
                if pop_node.right is not None:
                    queue.append(pop_node.right)
    
        def dfs_preorder(self, root):
            """ 深度优先-利用递归 ，先序遍历 1 2 3 4 5 6 7 1 2 4 5 3 6 7 """
            if root is None:
                return
            print(root.val, end=' ')
            self.dfs_preorder(root.left)
            self.dfs_preorder(root.right)
    
        def dfs_inorder(self, root):
            """ 深度优先-利用递归 ，中序遍历 1 2 3 4 5 6 7 4 2 5 1 6 3 7 """
            if root is None:
                return
            self.dfs_inorder(root.left)
            print(root.val, end=' ')
            self.dfs_inorder(root.right)
    
        def dfs_postorder(self, root):
            """ 深度优先-利用递归 ，后序遍历 1 2 3 4 5 6 7 4 5 2 6 7 3 1 """
            if root is None:
                return
            self.dfs_postorder(root.left)
            self.dfs_postorder(root.right)
            print(root.val, end=' ')
    
    
    
    tree = Tree()
    tree.add_element(1)
    tree.add_element(2)
    tree.add_element(3)
    tree.add_element(4)
    tree.add_element(5)
    tree.add_element(6)
    tree.add_element(7)
    # tree.bfs()
    # tree.dfs_preorder(tree.root)
    # tree.dfs_inorder(tree.root)
    tree.dfs_postorder(tree.root)