本文实例讲述了Python数据结构与算法之二叉树结构定义与遍历方法。分享给大家供大家参考，具体如下：
先序遍历，中序遍历，后序遍历 ，区别在于三条核心语句的位置
层序遍历 采用队列的遍历操作第一次访问根，在访问根的左孩子，接着访问根的有孩子，然后下一层 自左向右一一访问同层的结点
# 先序遍历
# 访问结点，遍历左子树，如果左子树为空，则遍历右子树，
# 如果右子树为空，则向上走到一个可以向右走的结点，继续该过程
preorder(t):
if t:
print t.value
preorder t.L
preorder t.R
# 中序遍历
# 从根开始，一直走向左下方，直到无结点可以走则停下，访问该节点
# 然后走向右下方到结点，继续走向左下方：如果结点无右孩子，则向上走回父亲结点
inorder(t):
inorder(t.L)
print t.value
inorder(t.R)
# 后序遍历
inorder(t):
inorder(t.L)
inorder(t.R)
print t.value
# 二叉树结点类型
class BTNode:
def __init__(self,value,lft=None,rgt=None):
self.value = value
self.lft = lft # 结点左分支 BTNode
self.rgt = rgt # 结点右分支 BTNode
为了方便起见，定义一些打印操作
class BinTree():
def __init__(self):
self.root = None # 创建一个空的二叉树
def isEmpty(self): # 判断二叉树是否为空
if self.root is None: return True
else: return False
def makeBT(self,bt,L=None,R=None): # 从当前结点创建二叉树
bt.lft = L
bt.rgt = R
def returnBTdict(self): # 返回二叉树的字典模式
if self.isEmpty():
return None
def rec(bt=None,R=True):
if R==True:
bt = self.root
return {'root':{'value':bt.value,"L":rec(bt.lft,False),
"R":rec(bt.rgt,False)} }
else:
if bt==None:
return None
else:
return {"value":bt.value,
"L":rec(bt.lft,False) if bt.lft != None else None,
"R":rec(bt.rgt,False) if bt.rgt != None else None}
return None
return rec()
def __repr__(self): # 将二叉树结构打印为字典结构
return str(self.returnBTdict())
下面是各种遍历方法，添加到树的类中
def printT_VLR(self,bt=None,rec_count = 0): # 输出二叉树结构（先序遍历）
# rec_count 用于计算递归深度 以便输出最后的换行符
"""
# 先序遍历
# 访问结点，遍历左子树，如果左子树为空，则遍历右子树，
# 如果右子树为空，则向上走到一个可以向右走的结点，继续该过程
preorder(t):
if t:
print t.value
preorder t.L
preorder t.R
"""
if bt==None:
bt = self.root
print bt.value,
btL, btR = bt.lft, bt.rgt
if btL != None:
print btL.value,; rec_count += 1; self.printT_VLR(btL,rec_count); rec_count -= 1
if btR != None:
print btR.value,; rec_count += 1; self.printT_VLR(btR,rec_count); rec_count -= 1
if rec_count == 0:
print "\n"
def printT_LVR(self,bt=None):
"""
# 中序遍历
# 从根开始，一直走向左下方，直到无结点可以走则停下，访问该节点
# 然后走向右下方到结点，继续走向左下方：如果结点无右孩子，则向上走回父亲结点
inorder(t):
inorder(t.L)
print t.value
inorder(t.R)
"""
if bt==None:
bt = self.root
btL, btR = bt.lft, bt.rgt
if btL != None:
self.printT_LVR(btL)
print bt.value,
if btR != None:
self.printT_LVR(btR)
def printT_LRV(self,bt=None):
"""
# 后序遍历
inorder(t):
inorder(t.L)
inorder(t.R)
print t.value
"""
if bt==None:
bt = self.root
btL, btR = bt.lft, bt.rgt
if btL != None:
self.printT_LRV(btL)
if btR != None:
self.printT_LRV(btR)
print bt.value,
def printT_levelorder(self):
"""
层序遍历 采用队列的遍历操作
第一次访问根，在访问根的左孩子，接着访问根的有孩子，然后下一层
自左向右一一访问同层的结点
"""
btdict = self.returnBTdict()
q = []
q.append(btdict['root'])
while q:
tn = q.pop(0) # 从队列中弹出一个结点(也是一个字典)
print tn["value"],
if tn["L"]!=None:
q.append(tn["L"])
if tn["R"]!=None:
q.append(tn["R"])
测试打印效果
def test(): bt = BinTree() # btns = [BTNode(v) for v in "+*E*D/CAB"] # 层序输入 # bt.root = btns[0] # bt.makeBT(btns[0], L=btns[1], R=btns[2]) # bt.makeBT(btns[1], L=btns[3], R=btns[4]) # bt.makeBT(btns[3], L=btns[5], R=btns[6]) # bt.makeBT(btns[5], L=btns[7], R=btns[8]) btns = [BTNode(v) for v in [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]] bt.root = btns[0] bt.makeBT(btns[0], L=btns[1], R=btns[2]) bt.makeBT(btns[1], L=btns[3], R=btns[4]) bt.makeBT(btns[2], L=btns[5], R=btns[6]) bt.makeBT(btns[3], L=btns[7], R=btns[8]) bt.makeBT(btns[4], L=btns[9], R=btns[10]) bt.makeBT(btns[5], L=btns[11], R=btns[12]) bt.makeBT(btns[6], L=btns[13], R=btns[14])
输出：
复制代码 代码如下:{'root': {'R': {'R': {'R': {'R': None, 'L': None, 'value': 15}, 'L': {'R': None, 'L': None, 'value': 14}, 'value': 7}, 'L': {'R': {'R': None, 'L': None, 'value': 13}, 'L': {'R': None, 'L': None, 'value': 12}, 'value': 6}, 'value': 3}, 'L': {'R': {'R': {'R': None, 'L': None, 'value': 11}, 'L': {'R': None, 'L': None, 'value': 10}, 'value': 5}, 'L': {'R': {'R': None, 'L': None, 'value': 9}, 'L': {'R': None, 'L': None, 'value': 8}, 'value': 4}, 'value': 2}, 'value': 1}}
更多关于Python相关内容感兴趣的读者可查看本站专题：《Python数据结构与算法教程》、《Python加密解密算法与技巧总结》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》
希望本文所述对大家Python程序设计有所帮助。
免责声明：本站文章均来自网站采集或用户投稿，网站不提供任何软件下载或自行开发的软件！ 如有用户或公司发现本站内容信息存在侵权行为，请邮件告知！ 858582#qq.com
《魔兽世界》大逃杀！60人新游玩模式《强袭风暴》3月21日上线
暴雪近日发布了《魔兽世界》10.2.6 更新内容，新游玩模式《强袭风暴》即将于3月21 日在亚服上线，届时玩家将前往阿拉希高地展开一场 60 人大逃杀对战。
艾泽拉斯的冒险者已经征服了艾泽拉斯的大地及遥远的彼岸。他们在对抗世界上最致命的敌人时展现出过人的手腕，并且成功阻止终结宇宙等级的威胁。当他们在为即将于《魔兽世界》资料片《地心之战》中来袭的萨拉塔斯势力做战斗准备时，他们还需要在熟悉的阿拉希高地面对一个全新的敌人──那就是彼此。在《巨龙崛起》10.2.6 更新的《强袭风暴》中，玩家将会进入一个全新的海盗主题大逃杀式限时活动，其中包含极高的风险和史诗级的奖励。
《强袭风暴》不是普通的战场，作为一个独立于主游戏之外的活动，玩家可以用大逃杀的风格来体验《魔兽世界》，不分职业、不分装备（除了你在赛局中捡到的），光是技巧和战略的强弱之分就能决定出谁才是能坚持到最后的赢家。本次活动将会开放单人和双人模式，玩家在加入海盗主题的预赛大厅区域前，可以从强袭风暴角色画面新增好友。游玩游戏将可以累计名望轨迹，《巨龙崛起》和《魔兽世界：巫妖王之怒 经典版》的玩家都可以获得奖励。