python 二叉树遍历 DFS和BFS

快来打我* 2022-05-10 08:52 156阅读 0赞

检查python 版本

import sys  
    print(sys.version)   
    print(sys.version_info )

*  mac  
    python 自己写的数据结构在 Documents/data\_structure/python中  
    Documents/data\_structure/cpp/LeetCode  
    sublime annaconda 3.6.5  
    pycharm /usr/local/Cellar/python3/3.6.1
 *  linux机器

给出树的节点

class TreeNode:
        def __init__(self,x):
            self.val=x
            self.left=None
            self.right=None

### 题目 ###

输入：
    ###          A
    #        /        \
    #     B            C
    #   /  \          /  \
    #  D     E      F     G
    #       /        \
    #      H           I
    输出：     
    # LayerOrder: 
    # A 
    # BC 
    # DEFG

#### 树的结构存储 ####

python中如何存储树？

#### BFS 广度优先遍历 ####

BFS用到的数据结构是quene

def bfs(self,root): # 传入树的根节点
        quene=[] 
        q.append(root) 
        while len(q)!=0:
            every_layer=[]
            length=len(q)
            for i in range(length):
                r=q.pop(0) 
                if not r.left is None: 
                   q.append(r.left)
                if not r.right is None:
                   q.append(r.right)
                every_layer.append(r.val)
            print every_layer
            print ' '
            result.append(every_layer)

发表评论取消回复

表情：

评论列表（有 0 条评论，156人围观）

还没有评论，来说两句吧...

相关阅读

相关 Python 数据结构之二叉树：二叉树的遍历：DFS 深度优先（先序遍历、中序遍历、后续遍历）和 BFS 广度优先遍历。

1. 二叉树二叉树是一种常用的数据结构，是树这种数据机构的一种特例。它最多只有两个子节点，且如果有两个子节点，两个子节点之间是有顺序的，一个称为左孩子节点，一个称为右孩

朱雀/ 2023年05月22日 04:46/ 0 赞/ 14 阅读

相关二叉树的层次遍历BFS

使用队列实现BFS queue.peek()只获取队首元素不删除 queue.poll()获取并删除队首元素 / // Definition for a No

末蓝、/ 2022年12月15日 11:03/ 0 赞/ 133 阅读

相关二叉树二叉树遍历通过二叉树遍历求得二叉树

什么是二叉树 > > 二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且

偏执的太偏执、/ 2022年12月04日 01:08/ 0 赞/ 285 阅读

相关 BFS和DFS两种方式实现二叉树的层序遍历

二叉树文章系列： 1. [二叉树的前序遍历][Link 1] 2. [二叉树的中序遍历][Link 2] 3. [二叉树的后序遍历][Link 3] 4. [二叉树的

迈不过友情╰/ 2022年11月10日 10:48/ 0 赞/ 89 阅读

相关 python3 二叉树遍历

二叉树遍历（此文用来纪念今天在你好星球面试被技术总监吊打，哈哈，还是要注重基础啊，不能忘）前序遍历：根节点->左子树->右子树

淡淡的烟草味﹌/ 2022年06月16日 07:22/ 0 赞/ 162 阅读

相关广度遍历二叉树（Python）

class TreeNode: def __init__(self, x): self.val = x

た入场券/ 2022年05月18日 04:06/ 0 赞/ 170 阅读

相关二叉树的遍历 python

从二叉树的根节点出发，节点的遍历分为三个主要步骤：对当前节点进行操作（称为“访问”节点，或者根节点）、遍历左边子节点、遍历右边子节点。访问节点顺序的不同也就形成了不同的遍历方式

红太狼/ 2022年05月17日 02:17/ 0 赞/ 177 阅读

相关二叉树遍历——深度优先(DFS)与广度优先(BFS)

二叉树的深度优先遍历（DFS）与广度优先遍历（BFS）深度优先遍历：从根节点出发，沿着左子树方向进行纵向遍历，直到找到叶子节点为止。然后回溯到前一个节点，进行右子树节点

我不是女神ヾ/ 2022年05月16日 12:12/ 0 赞/ 250 阅读

相关 python 二叉树遍历 DFS和BFS

检查python 版本 import sys print(sys.version) print(sys.version_info )

快来打我*/ 2022年05月10日 08:52/ 0 赞/ 157 阅读

相关 DFS和BFS遍历

int n; //结点个数 int mp[N][N]; //邻接矩阵 int vis[N]; //记录此顶点是否遍历过； DFS

谁践踏了优雅/ 2021年11月05日 14:34/ 0 赞/ 268 阅读