【bf88必发唯一官网】Python2叉树定义与遍历方法实例解析,Python数据结构之哈夫曼树定义与使用办法言传身教

by admin on 2019年5月30日

本文实例讲述了Python数据结构之哈夫曼树定义与行使情势。分享给我们供我们参照他事他说加以考察,具体如下:

正文实例讲述了Python达成的多叉树寻找最短路线算法。分享给我们供大家参谋,具体如下:

本文实例为大家分享了Python深度优先算法生成迷宫,供我们参谋,具体内容如下

本文实例讲述了Python2叉树定义与遍历方法。分享给大家供大家参谋,具体如下:

HaffMan.py

多叉树的最短路径:

import random 

#warning: x and y confusing 

sx = 10 
sy = 10 
dfs = [[0 for col in range(sx)] for row in range(sy)] 
maze = [[' ' for col in range(2*sx+1)] for row in range(2*sy+1)] 
#1:up 2:down 3:left 4:right 
operation = {1:(0,-1),2:(0,1),3:(-1,0),4:(1,0)} 
direction = [1, 2, 3, 4] 
stack = [] 

for i in range(2*sx+1): 
 if i%2 == 0: 
  for j in range(2*sx+1): 
   maze[i][j] = '#' 
for i in range(2*sy+1): 
 if i%2 == 0: 
  for j in range(2*sy+1): 
   maze[j][i] = '#' 

def show(graph): 
 for i in graph: 
  for j in i: 
   print j, 
  print 

def showRouter(stack): 
 RGragh = [[0 for col in range(sx)] for row in range(sy)] 
 for (x, y) in stack: 
  RGragh[y][x] = 1 
 show(RGragh) 
 print 

def generateMaze(start): 
 x, y = start 
 dfs[y][x] = 1 
 random.shuffle(direction) 
 for d in direction: 
  px, py = (x + y for x, y in zip(start, operation[d])) 
  if px < 0 or px >= sx or py < 0 or py >= sy: 
   pass 
  else: 
   if dfs[py][px] is not 1: 
    mx = 2*x + 1 
    my = 2*y + 1 
    if d == 1: 
     maze[my-1][mx] = ' ' 
    elif d == 2: 
     maze[my+1][mx] = ' ' 
    elif d == 3: 
     maze[my][mx-1] = ' ' 
    elif d == 4: 
     maze[my][mx+1] = ' ' 
    generateMaze((px,py)) 

generateMaze((0,0)) 
show(dfs) 
show(maze) 

贰叉树基本概述:

#coding=utf-8
#考虑权值的haff曼树查找效率并非最高,但可以用于编码等使用场景下
class TreeNode:
  def __init__(self,data):
    self.data=data
    self.left=None
    self.right=None
    self.parent=None
class HaffTree:
  def __init__(self):
    self.root=None
  def set_root(self,rootNode):
    self.root=rootNode
  def run(self,lis):
    i=0
    lis=[[lis[j][0],lis[j][1],TreeNode(lis[j][1])]for j in range(len(lis))]
    while len(lis)>1:
      i+=1
      lis=sorted(lis)
      name='N'+str(i)
      temp=TreeNode(name)
      #结果与大话数据结构书上略有不同 因为lis[0][2]=lis[1][2] 无影响
      #这里使用parent 替代深度优先/广度优先 算法
      temp.left=lis[0][2]
      temp.right=lis[1][2]
      lis[0][2].parent=temp
      lis[1][2].parent=temp
      #print lis[0][0],lis[1][0],len(lis)
      value=lis[0][0]+lis[1][0]
      lis=lis[1:]
      lis[0]=[value,name,temp]
    #print temp.data,temp.left.data,temp.right.data
    self.set_root(temp)
  def code(self,lis):
    self.codeList=[]
    stack=[]
    Node=self.root
    stack.append(Node)
    res=[]
    while(stack):
      node=stack.pop()
      res.append(node)
      if node.right:
        stack.append(node.right)
      if node.left:
        stack.append(node.left)
    for li in lis:
      codeL=[]
      for re in res:
        if re.data==li[1]:
          parent=re
          print '\n',parent.data,
          codeL.append(parent)
          while parent.parent:
            parent=parent.parent
            print parent.data,
            codeL.append(parent)
          codeLL=[int(codeL[len(codeL)-2-i]==codeL[len(codeL)-1-i].right) for i in range(len(codeL)-1)]
          self.codeList.append([li[1],codeLL])
    return self.codeList
  def list_all(self,method):
    lis=[]
    res=[]
    if method=='before':
      Node=self.root
      lis.append(Node)
      while(lis):
        node=lis[-1]
        lis=lis[:-1]
        if node:
          res.append(node.data)
        if node.right:
          lis.append(node.right)
        if node.left:
          lis.append(node.left)
    elif method=='mid':
      node = self.root
      while lis or node:
        while node:
          lis.append(node)
          node = node.left
        if len(lis)>0:
          node = lis[-1]
          lis=lis[:-1]
          if node:
            res.append(node.data)
          node= node.right
    else:
      pass
    return res

思想:

以上就是本文的全体内容,希望对大家的上学抱有援助,也愿意我们多多援救脚本之家。

二叉树是零星个因素的多少个,假如为空则为空二叉树,只怕有三个结点称之为根节点,分列根节点两侧的为2叉树的左右子节点,二叉树有如下的性质:

HaffMantest.py

    传入start 和 end 两个 目标值
    1 找到从根节点到目的节点的路线
    2 从所在路子,搜索这段日子的公共祖先节点,
    三 对近来公共祖先根节点 拼接路线

您可能感兴趣的小说:

  • Python中的二叉树查找算法模块使用指南
  • 【bf88必发唯一官网】Python2叉树定义与遍历方法实例解析,Python数据结构之哈夫曼树定义与使用办法言传身教。python完成的2叉树定义与遍历算法实例
  • python完结的贰叉树算法和kmp算法实例
  • Python数据结构与算法之2叉树结构定义与遍历方法详解
  • Python算法之求n个节点区别2叉树个数
  • Python2叉树的定义及常用遍历算法深入分析
  • Python完结基于2叉树存款和储蓄结构的堆排序算法示例
  • Python编程求解2叉树如月为某1值的路子代码示例
  • python数据结构之图深度优先和广度优先实例详解
  • Python数据结构与算法之图的广度优先与深度优先搜索算法示例
  • python深度优先寻找和广度优先寻觅
  • Python完毕的多叉树搜索最短路线算法示例
  1. 2叉树的每种结点不存在度大于2的结点
  2. 二叉树的第i层至多有2^{i-一}个结点
  3. 深度为k的二叉树至多有2^k – 1个结点
  4. 2叉树中,度为0的结点数N0比度为2的结点数N贰大一,即存在N二 + 一 = N0
#coding=utf-8
from HaffMan import HaffTree
tree=HaffTree()
lis=[
    [5,'A'],
    [15,'B'],
    [40,'C'],
    [30,'D'],
    [10,'E'],
   ]
print lis[2:]
print sorted(lis)
tree.run(lis)
print tree.list_all('before')
#应用 HaffMan编码,比如字母分布不均匀的情况下比较适合,可减少传输的信息量(二进制),不会出现干涉。:
tree=HaffTree()
lis2=[
    [27,'A'],
    [8,'B'],
    [15,'C'],
    [15,'D'],
    [30,'E'],
    [5,'F'],
   ]
tree.run(lis2)
print tree.code(lis2)

Python代码:

Python代码:

运行结果:

# -*- coding:utf-8 -*-
import copy
#节点数据结构
class Node(object):
  # 初始化一个节点
  def __init__(self,value = None):
    self.value = value # 节点值
    self.child_list = []  # 子节点列表
  # 添加一个孩子节点
  def add_child(self,node):
    self.child_list.append(node)
# 初始化一颗测试二叉树
def init():
  '''
  初始化一颗测试二叉树:
      A
    B  C  D
   EFG    HIJ
  '''
  root = Node('A')
  B = Node('B')
  root.add_child(B)
  root.add_child(Node('C'))
  D = Node('D')
  root.add_child(D)
  B.add_child(Node('E'))
  B.add_child(Node('F'))
  B.add_child(Node('G'))
  D.add_child(Node('H'))
  D.add_child(Node('I'))
  D.add_child(Node('J'))
  return root
# 深度优先查找 返回从根节点到目标节点的路径
def deep_first_search(cur,val,path=[]):
  path.append(cur.value) # 当前节点值添加路径列表
  if cur.value == val:  # 如果找到目标 返回路径列表
    return path
  if cur.child_list == []:  # 如果没有孩子列表 就 返回 no 回溯标记
    return 'no'
  for node in cur.child_list: # 对孩子列表里的每个孩子 进行递归
    t_path = copy.deepcopy(path)  # 深拷贝当前路径列表
    res = deep_first_search(node,val,t_path)
    if res == 'no': # 如果返回no,说明找到头 没找到 利用临时路径继续找下一个孩子节点
      continue
    else :
      return res # 如果返回的不是no 说明 找到了路径
  return 'no' # 如果所有孩子都没找到 则 回溯
# 获取最短路径 传入两个节点值,返回结果
def get_shortest_path( start,end ):
  # 分别获取 从根节点 到start 和end 的路径列表,如果没有目标节点 就返回no
  path1 = deep_first_search(root, start, [])
  path2 = deep_first_search(root, end, [])
  if path1 == 'no' or path2 == 'no':
    return '无穷大','无节点'
  # 对两个路径 从尾巴开始向头 找到最近的公共根节点,合并根节点
  len1,len2 = len(path1),len(path2)
  for i in range(len1-1,-1,-1):
    if path1[i] in path2:
      index = path2.index(path1[i])
      path2 = path2[index:]
      path1 = path1[-1:i:-1]
      break
  res = path1+path2
  length = len(res)
  path = '->'.join(res)
  return '%s:%s'%(length,path)
# 主函数、程序入口
if __name__ == '__main__':
  root = init()
  res = get_shortest_path('F','I')
  print(res)
#coding:utf-8
'BiTree'
class Node(object):
  'Node Defination'
  def __init__(self,item):
    self.item = item
    self.left = None
    self.right = None
class Tree(object):
  'Bitree Defination'
  def __init__(self):
    self.root = None
  def add(self,item):
    node = Node(item)
    if self.root is None:
      self.root = node
    else:
      q = [self.root]
      while True:
        pop_node = q.pop(0)
        if pop_node.left is None:
          pop_node.left = node
          return
        elif pop_node.right is None:
          pop_node.right = node
          return
        else:
          q.append(pop_node.left)
          q.append(pop_node.right)
  def traverse(self):#层次遍历
    if self.root is None:
      return None
    q = [self.root]
    res = [self.root.item]
    while q != []:
      pop_node = q.pop(0)
      if pop_node.left is not None:
        q.append(pop_node.left)
        res.append(pop_node.left.item)
      if pop_node.right is not None:
        q.append(pop_node.right)
        res.append(pop_node.right.item)
    return res
  def preorder(self,root): #先序遍历
    if root is None:
      return []
    result = [root.item]
    left_item = self.preorder(root.left)
    right_item = self.preorder(root.right)
    return result + left_item + right_item
  def inorder(self,root): #中序遍历
    if root is None:
      return []
    result = [root.item]
    left_item = self.inorder(root.left)
    right_item = self.inorder(root.right)
    return left_item + result + right_item
  def postorder(self,root): #后序遍历
    if root is None:
      return []
    result = [root.item]
    left_item = self.postorder(root.left)
    right_item = self.postorder(root.right)
    return left_item + right_item + result
if __name__=='__main__':
  t = Tree()
  for i in range(10):
    t.add(i)
  print "层序遍历:",t.traverse()
  print "先序遍历:",t.preorder(t.root)
  print "中序遍历:",t.inorder(t.root)
  print "后序遍历:",t.postorder(t.root)

bf88必发唯一官网 1

运作结果:

输出结果:

【bf88必发唯一官网】Python2叉树定义与遍历方法实例解析,Python数据结构之哈夫曼树定义与使用办法言传身教。更加的多关于Python相关内容感兴趣的读者可查看本站专项论题:《Python数据结构与算法教程》、《Python函数使用本事计算》、《Python字符串操作技艺汇总》、《Python入门与进级精湛教程》及《Python文件与目录操作才具汇总》

5:F->B->A->D->I

层序遍历: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
先序遍历: [0, 1, 3, 7, 8, 4, 9, 2, 5, 6]
中序遍历: [bf88必发唯一官网,7, 3, 8, 1, 9, 4, 0, 5, 2, 6]
后序遍历: [7, 8, 3, 9, 4, 1, 5, 6, 2, 0]

指望本文所述对我们Python程序设计有所支持。

越多关于Python相关内容感兴趣的读者可查阅本站专项论题:《Python数据结构与算法教程》、《Python编码操作本事总计》、《Python函数使用技艺总括》、《Python字符串操作工夫汇总》及《Python入门与进级优良教程》

此地对于

您大概感兴趣的小说:

  • python数据结构之图深度优先和广度优先实例详解
  • python数据结构之图的贯彻情势
  • Python数据结构与算法之图结构(Graph)实例分析
  • Python数据结构与算法之图的最短路线(Dijkstra算法)完整实例
  • Python数据结构与算法之图的广度优先与深度优先寻觅算法示例
  • Python数据结构与算法之图的主导落到实处及迭代器实例详解
  • Python数据结构之双向链表的定义与运用办法言传身教
  • Python数据结构与算法之使用队列消除喵咪钓鱼难点
  • Python数据结构与算法之2叉树结构定义与遍历方法详解
  • Python数据结构之图的施用示范

目的在于本文所述对大家Python程序设计具有支持。

if __name__=='__main__':
“Make a script both importable and executable”

您恐怕感兴趣的小说:

  • Python中的贰叉树查找算法模块使用指南
  • python完成的2叉树定义与遍历算法实例
  • python达成的二叉树算法和kmp算法实例
  • Python数据结构与算法之二叉树结构定义与遍历方法详解
  • Python算法之求n个节点差异二叉树个数
  • Python2叉树的定义及常用遍历算法深入分析
  • Python达成基于2叉树存款和储蓄结构的堆排序算法示例
  • Python编制程序求解2叉树竹秋为某1值的路子代码示例
  • python数据结构之图深度优先和广度优先实例详解
  • Python数据结构与算法之图的广度优先与深度优先搜索算法示例
  • Python深度优先算法生成迷宫
  • python深度优先搜索和广度优先搜索

意思正是让您写的本子模块既能够导入到别的模块中用,别的该模块自个儿也可实行。

此处经过二个演示实行疏解:

#test.py
def func():
 print "we are in %s"%__name__
if __name__ == '__main__':
 func()

出口结果:

we are in __main__

表达if语句中的内容被实施了,调用了
func()函数,以后在另1个模块中调用func函数

#testtest
from test import func
func()

输出结果:

we are in moudle

也正是说 if 条件中的内容尚未施行。

总结:

借使直白施行某些*.py文件,该文件中
if __name__ == '__main__'是True,相当于调式本模块的代码;假若是从另2个模块(testtest.py)通过import导入该公文的时候,那时__name__正是以此模块的名字(test)而不是__main__,综上说述在调式代码的时候增加if __name__ == '__main__'中投入调节和测试代码,能够迁就模块调用的时候不举办调式代码,假设想排查本模块代码的题目时,直接开展调解推行

更加多关于Python相关内容感兴趣的读者可查看本站专项论题:《Python数据结构与算法教程》、《Python加密解密算法与本领总结》、《Python编码操作本事计算》、《Python函数使用技能总括》、《Python字符串操作手艺汇总》及《Python入门与升级杰出教程》

可望本文所述对大家Python程序设计有着支持。

你也许感兴趣的稿子:

  • python数据结构之贰叉树的遍历实例
  • python二叉树遍历的贯彻格局
  • Python达成2叉树结构与开展2叉树遍历的办法详解
  • Python利用前序和中序遍历结果重建二叉树的法门
  • python完毕的二叉树定义与遍历算法实例
  • Python编制程序达成二叉树及多种遍历方法详解
  • python达成2叉树的遍历
  • Python数据结构与算法之2叉树结构定义与遍历方法详解
  • Python2叉树的概念及常用遍历算法剖析
  • Python定义2叉树及④种遍历方法实例详解
  • Python完结输入贰叉树的先序和中序遍历,再出口后序遍历操作示例

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图