apk电子书,无限之天魔魅影,朱晓琳深v
遍历方案
从二叉树的递归定义可知,一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此,在任一给定结点上,可以按某种次序执行三个操作:
1).访问结点本身(n)
2).遍历该结点的左子树(l)
3).遍历该结点的右子树(r)
有次序:
nlr、lnr、lrn
遍历的命名
根据访问结点操作发生位置命名:
nlr:前序遍历(preordertraversal亦称(先序遍历)) ——访问结点的操作发生在遍历其左右子树之前。
lnr:中序遍历(inordertraversal) ——访问结点的操作发生在遍历其左右子树之中(间)。
lrn:后序遍历(postordertraversal) ——访问结点的操作发生在遍历其左右子树之后。
注:由于被访问的结点必是某子树的根,所以n(node)、l(left subtlee)和r(right subtree)又可解释为根、根的左子树和根的右子树。nlr、lnr和lrn分别又称为先根遍历、中根遍历和后根遍历。
遍历算法
1).先序遍历的递归算法定义:
若二叉树非空,则依次执行如下操作:
a.访问根结点
b.遍历左子树
c.遍历右子树
2).中序遍历的递归算法定义:
若二叉树非空,则依次执行如下操作:
a.遍历左子树
b.访问根结点
c.遍历右子树
3).后序遍历得递归算法定义:
若二叉树非空,则依次执行如下操作:
a.遍历左子树
b.遍历右子树
c.访问根结点
一、二叉树的递归遍历:
class treenode(object):
def __init__(self, left=0, right=0, data=0):
self.left = left
self.right = right
self.data = data
class btree(object):
def __init__(self, root=0):
self.root = root
def is_empty(self):
if self.root is 0:
return true
else:
return false
def preorder(self, treenode):
'前序(pre-order,nlr)遍历'
if treenode is 0:
return
print treenode.data
self.preorder(treenode.left)
self.preorder(treenode.right)
def inorder(self, treenode):
'中序(in-order,lnr'
if treenode is 0:
return
self.inorder(treenode.left)
print treenode.data
self.inorder(treenode.right)
def postorder(self, treenode):
'后序(post-order,lrn)遍历'
if treenode is 0:
return
self.postorder(treenode.left)
self.postorder(treenode.right)
print treenode.data
node1 = treenode(data=1)
node2 = treenode(node1, 0, 2)
node3 = treenode(data=3)
node4 = treenode(data=4)
node5 = treenode(node3, node4, 5)
node6 = treenode(node2, node5, 6)
node7 = treenode(node6, 0, 7)
node8 = treenode(data=8)
root = treenode(node7, node8, 'root')
bt = btree(root)
print u'''
#生成的二叉树
# ------------------------
# root
# 7 8
# 6
# 2 5
# 1 3 4
#
# -------------------------
'''
print '前序(pre-order,nlr)遍历 :\n'
bt.preorder(bt.root)
print '中序(in-order,lnr) 遍历 :\n'
bt.inorder(bt.root)
print '后序(post-order,lrn)遍历 :\n'
bt.postorder(bt.root)
二、.二叉树的非递归遍历
下面就用非递归的方式实现一遍。主要用到了 stack 和 queue维护一些数据节点:
如对本文有疑问,请在下面进行留言讨论,广大热心网友会与你互动!! 点击进行留言回复
Python 实现将numpy中的nan和inf,nan替换成对应的均值
python爬虫把url链接编码成gbk2312格式过程解析
网友评论