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

Python  /  管理员 发布于 7年前   206

深度遍历：

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

逻辑（本质用递归）：

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实现深度遍历和广度遍历的方法就是小编分享给大家的全部内容了，希望能给大家一个参考，也希望大家多多支持。