Python实现深度遍历和广度遍历的方法

深度遍历：

原则：从上到下，从左到右

逻辑（本质用递归）：

1）、找根节点

2）、找根节点的左边

3）、找根节点的右边

class Node(object):
 def __init__(self, item=None, left=None, right=None):
  self.item = item
  self.left = left
  self.right = right

d = Node("D")
e = Node("E")
b = Node("B", d, e)
f = Node("F")
g = Node("G")
c = Node("C", f, g)
a = Node("A", b, c)

result = []

def deep_search(root):
 # 深度遍历 核心：递归
 result.append(root.item)
 if root.left:
  deep_search(root.left)
 if root.right:
  deep_search(root.right)
 return "-->".join(result)

print deep_search(a)

广度遍历：

核心：队列+递归

def wide_search(root, result=[]):

 if not result:
  result.append(root.item)
 if root.left:
  result.append(root.left.item)
 if root.right:
  result.append(root.right.item)
 if root.left:
  wide_search(root.left)
 if root.right:
  wide_search(root.right)
 return "-->".join(result)

print wide_search(a)

以上这篇Python实现深度遍历和广度遍历的方法就是小编分享给大家的全部内容了，希望能给大家一个参考，也希望大家多多支持我们。

赞 (0)

相关推荐

  • python遍历文件夹,指定遍历深度与忽略目录的方法

    背景 需要在文件夹中搜索某一文件,找到后返回此文件所在目录.用最常规的os.listdir()方式实现了一版,但执行时报错:递归超过最大深度.于是自己添加了点功能,之所有写此函数是为了让它适应不同的项目,因为有项目要找的文件在第一层,有的在第二层. 函数 功能:在文件夹中查找某一文件,找到后返回True与文件所在目录路径. 参数:filepath, 要查找的目录 参数:filename, 要查找的文件 扩展1:find_depth, 查找时指定递归深度: 扩展2:ignore_path, 查找时

  • python深度优先搜索和广度优先搜索

    1. 深度优先搜索介绍 图的深度优先搜索(Depth First Search),和树的先序遍历比较类似. 它的思想:假设初始状态是图中所有顶点均未被访问,则从某个顶点v出发,首先访问该顶点,然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图,直至图中所有和v有路径相通的顶点都被访问到. 若此时尚有其他顶点未被访问到,则另选一个未被访问的顶点作起始点,重复上述过程,直至图中所有顶点都被访问到为止. 显然,深度优先搜索是一个递归的过程. 2. 广度优先搜索介绍 广度优先搜索算法(Breadt

  • 使用 Python 实现文件递归遍历的三种方式

    今天有个脚本需要遍历获取某指定文件夹下面的所有文件,我记得很早前也实现过文件遍历和目录遍历的功能,于是找来看一看,嘿,不看不知道,看了吓一跳,原来之前我竟然用了这么搓的实现. 先发出来看看: def getallfiles(dir): """遍历获取指定文件夹下面所有文件""" if os.path.isdir(dir): filelist = os.listdir(dir) for ret in filelist: filename = dir

  • python 递归深度优先搜索与广度优先搜索算法模拟实现

     一.递归原理小案例分析 (1)# 概述 递归:即一个函数调用了自身,即实现了递归 凡是循环能做到的事,递归一般都能做到! (2)# 写递归的过程 1.写出临界条件 2.找出这一次和上一次关系 3.假设当前函数已经能用,调用自身计算上一次的结果,再求出本次的结果 (3)案例分析:求1+2+3+...+n的数和 # 概述 ''' 递归:即一个函数调用了自身,即实现了递归 凡是循环能做到的事,递归一般都能做到! ''' # 写递归的过程 ''' 1.写出临界条件 2.找出这一次和上一次关系 3.假设

  • Python实现深度遍历和广度遍历的方法

    深度遍历: 原则:从上到下,从左到右 逻辑(本质用递归): 1).找根节点 2).找根节点的左边 3).找根节点的右边 class Node(object): def __init__(self, item=None, left=None, right=None): self.item = item self.left = left self.right = right d = Node("D") e = Node("E") b = Node("B&quo

  • Python定义二叉树及4种遍历方法实例详解

    Python定义二叉树及4种遍历方法实例详解

    本文实例讲述了Python定义二叉树及4种遍历方法.分享给大家供大家参考,具体如下: Python & BinaryTree 1. BinaryTree (二叉树) 二叉树是有限个元素的集合,该集合或者为空.或者有一个称为根节点(root)的元素及两个互不相交的.分别被称为左子树和右子树的二叉树组成. 二叉树的每个结点至多只有二棵子树(不存在度大于2的结点),二叉树的子树有左右之分,次序不能颠倒. 二叉树的第i层至多有2^{i-1}个结点 深度为k的二叉树至多有2^k-1个结点: 对任何一棵二叉

  • python 循环遍历字典元素的简单方法

    一个简单的for语句就能循环字典的所有键,就像处理序列一样: In [1]: d = {'x':1, 'y':2, 'z':3} In [2]: for key in d: ...: print key, 'corresponds to', d[key] ...: y corresponds to 2 x corresponds to 1 z corresponds to 3 在python2.2之前,还只能用beys等字典方法来获取键(因为不允许直接迭代字典).如果只需要值,可以使用d.val

  • Python利用前序和中序遍历结果重建二叉树的方法

    Python利用前序和中序遍历结果重建二叉树的方法

    本文实例讲述了Python利用前序和中序遍历结果重建二叉树的方法.分享给大家供大家参考,具体如下: 题目:输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树.假设输入的前序遍历和中序遍历的结果中都不含重复的数字. 这道题比较容易,前序遍历的结果中,第一个结点一定是根结点,然后在中序遍历的结果中查找这个根结点,根结点左边的就是左子树,根结点右边的就是右子树,递归构造出左.右子树即可.示意图如图所示: 利用前序和中序遍历的结果重建二叉树 Python代码: # coding: utf-8 ''

  • python实现的二叉树定义与遍历算法实例

    python实现的二叉树定义与遍历算法实例

    本文实例讲述了python实现的二叉树定义与遍历算法.分享给大家供大家参考,具体如下: 初学python,需要实现一个决策树,首先实践一下利用python实现一个二叉树数据结构.建树的时候做了处理,保证建立的二叉树是平衡二叉树. # -*- coding: utf-8 -*- from collections import deque class Node: def __init__(self,val,left=None,right=None): self.val=val self.left=l

  • Python解析树及树的遍历

    Python解析树及树的遍历

    解析树 完成树的实现之后,现在我们来看一个例子,告诉你怎么样利用树去解决一些实际问题.在这个章节,我们来研究解析树.解析树常常用于真实世界的结构表示,例如句子或数学表达式. 图 1:一个简单句的解析树 图 1 显示了一个简单句的层级结构.将一个句子表示为一个树,能使我们通过利用子树来处理句子中的每个独立的结构. 图 2: ((7+3)*(5−2)) 的解析树 如图 2 所示,我们能将一个类似于 ((7+3)*(5−2)) 的数学表达式表示出一个解析树.我们已经研究过全括号表达式,那么我们怎样理解

  • python中遍历文件的3个方法

    今天写一个在windows下批量修改文件名的python脚本,用到文件的遍历.用python进行文件遍历有多种方法,这里列举并说明一下. os.path.walk() 这是一个传统的用法. walk(root,callable,args)方法有三个参数:要遍历的目录,回调函数,回调函数的参数(元组形式). 调用的过程是遍历目录下的文件或目录,每遍历一个目录,调用回调函数,并把args作为参数传递给回调函数. 回调函数定义时也有三个参数,比如示例中的func中的三个参数,分别为walk传来的参数.

  • Python二叉树的定义及常用遍历算法分析

    本文实例讲述了Python二叉树的定义及常用遍历算法.分享给大家供大家参考,具体如下: 说起二叉树的遍历,大学里讲的是递归算法,大多数人首先想到也是递归算法.但作为一个有理想有追求的程序员.也应该学学非递归算法实现二叉树遍历.二叉树的非递归算法需要用到辅助栈,算法着实巧妙,令人脑洞大开. 以下直入主题: 定义一颗二叉树,请看官自行想象其形状, class BinNode( ): def __init__( self, val ): self.lchild = None self.rchild =

  • Python实现带下标索引的遍历操作示例

    本文实例讲述了Python实现带下标索引的遍历操作.分享给大家供大家参考,具体如下: 代码如下: #coding=utf-8 #python - 实现带下标索引的遍历． str = 'abcdefghigklmn' #方式一:for i = 0 for ch in str: print('%d\t%s'%(i,ch)) i+=1 print('-'*50) #方式二:enumerate() for i,ch in enumerate(str): print i,ch 运行结果: 0   a 1 

  • python单向链表的基本实现与使用方法【定义、遍历、添加、删除、查找等】

    本文实例讲述了python单向链表的基本实现与使用方法.分享给大家供大家参考,具体如下: # -*- coding:utf-8 -*- #! python3 class Node(): def __init__(self,item): #初始化这个节点,值和下一个指向 self.item = item self.next = None class SingleLinklist(): def __init__(self): #初始化这个单链表的头指针为空 self._head = None def

随机推荐