python实现树的深度优先遍历与广度优先遍历详解

yipeiwu_com5年前Python基础

本文实例讲述了python实现树的深度优先遍历与广度优先遍历。分享给大家供大家参考,具体如下:

广度优先(层次遍历)

从树的root开始,从上到下从左到右遍历整个树的节点

数和二叉树的区别就是,二叉树只有左右两个节点

广度优先 顺序:A - B - C - D - E - F - G - H - I

代码实现

def breadth_travel(self, root):
    """利用队列实现树的层次遍历"""
    if root == None:
      return
    queue = []
    queue.append(root)
    while queue:
      node = queue.pop(0)
      print node.elem,
      if node.lchild != None:
        queue.append(node.lchild)
      if node.rchild != None:
        queue.append(node.rchild)

深度优先

深度优先有三种算法:前序遍历,中序遍历,后序遍历

先序遍历 在先序遍历中,我们先访问根节点,然后递归使用先序遍历访问左子树,再递归使用先序遍历访问右子树

根节点->左子树->右子树

 #实现 1
 def preorder(self, root):
    """递归实现先序遍历"""
    if root == None:
      return
    print root.elem
    self.preorder(root.lchild)
    self.preorder(root.rchild)

 #实现 2
 def depth_tree(tree_node):
   if tree_node is not None:
     print (tree_node._data)
     if tree_node._left is noe None:
       return depth_tree(tree_node._left)
     if tree_node._right is not None:
       return depth_tree(tree_node._right)

中序遍历 在中序遍历中,我们递归使用中序遍历访问左子树,然后访问根节点,最后再递归使用中序遍历访问右子树

左子树->根节点->右子树

def inorder(self, root):
   """递归实现中序遍历"""
   if root == None:
     return
   self.inorder(root.lchild)
   print root.elem
   self.inorder(root.rchild)

后序遍历 在后序遍历中,我们先递归使用后序遍历访问左子树和右子树,最后访问根节点

左子树->右子树->根节点

def postorder(self, root):
   """递归实现后续遍历"""
   if root == None:
     return
   self.postorder(root.lchild)
   self.postorder(root.rchild)
   print root.elem

更多关于Python相关内容感兴趣的读者可查看本站专题:《Python数据结构与算法教程》、《Python加密解密算法与技巧总结》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程

希望本文所述对大家Python程序设计有所帮助。

相关文章

Python 实现淘宝秒杀的示例代码

新手学习Python,之前在网上看见一位朋友写的40行Python代码搞定京东秒杀,想在淘宝上帮女朋友抢玩偶,所以就照猫画虎的写了下淘宝的秒杀脚本,经自己实验可行。直接上代码: #-...

python异常处理和日志处理方式

今天,总结一下最近编程使用的python异常处理和日志处理的感受,其实异常处理是程序编写时非常重要的一块,但是我一开始学的语言是C++,这门语言中没有强制要求使用try...catch语...

Python实现正则表达式匹配任意的邮箱方法

Python实现正则表达式匹配任意的邮箱方法

首先来个简单的例子,利用Python实现匹配163邮箱的代码: #-*- coding:utf-8 -*- __author__ = '杨鑫' import re text = in...

Python2.7基于淘宝接口获取IP地址所在地理位置的方法【测试可用】

Python2.7基于淘宝接口获取IP地址所在地理位置的方法【测试可用】

本文实例讲述了Python2.7基于淘宝接口获取IP地址所在地理位置的方法。分享给大家供大家参考,具体如下: #!/usr/bin/python import sys, os, u...

使用python脚本自动创建pip.ini配置文件代码实例

这篇文章主要介绍了使用python脚本自动创建pip.ini配置文件代码实例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 运行一下p...