开心魔法演员表,宇宙少主,橱柜清洁
主要是:前序遍历、中序遍历、后序遍历、层级遍历、非递归前序遍历、非递归中序遍历、非递归后序遍历
class treenode(object):
def __init__(self, data=none, left=none, right=none):
self.data = data
self.left = left
self.right = right
class tree(object):
def __init__(self, root=none):
self.root = none
def maketree(self, data, left, right):
self.root = treenode(data, left, right)
def is_empty(self):
"""是否为空 """
if self.root is none:
return true
return false
def preorder(self, r):
"""前序遍历 """
if not r.is_empty():
print r.root.data
if r.root.left is not none:
r.preorder(r.root.left)
if r.root.right is not none:
r.preorder(r.root.right)
def inorder(self, r):
"""中序遍历 """
if not r.is_empty():
if r.root.left is not none:
r.preorder(r.root.left)
print r.root.data
if r.root.right is not none:
r.preorder(r.root.right)
def postorder(self, r):
"""后续遍历 """
if not r.is_empty():
if r.root.left is not none:
r.preorder(r.root.left)
print r.root.data
if r.root.right is not none:
r.preorder(r.root.right)
def levelorder(self, r):
"""层级遍历 """
if not r.is_empty():
s = [r]
while len(s) > 0:
temp = s.pop(0) # 先弹出最先append到的点
if temp and temp.root is not none:
print temp.root.data
if temp.root.left is not none:
s.append(temp.root.left)
if self.root.right is not none:
s.append(temp.root.right)
def preorder1(self, r):
"""非递归 前序遍历 """
stack = []
current = r
while len(stack) > 0 or (current and not current.is_empty()):
while current and not current.is_empty():
print current.root.data
stack.append(current)
current = current.root.left
if len(stack) > 0:
current = stack.pop()
current = current.root.right
def inorder1(self, r):
"""非递归 中序遍历 """
stack = []
current = r
while len(stack) > 0 or (current and not current.is_empty()):
while current and not current.is_empty():
stack.append(current)
current = current.root.left
if len(stack) > 0:
current = stack.pop()
print current.root.data
current = current.root.right
def postorder1(self, r):
"""非递归 后续遍历 """
stack = []
current = r
pre = none
while len(stack) > 0 or (current and not current.is_empty()):
if current and not current.is_empty():
stack.append(current)
current = current.root.left
elif stack[-1].root.right != pre:
current = stack[-1].root.right
pre = none
else:
pre = stack.pop()
print pre.root.data
def leaves_count(self, r):
"""求叶子节点个数 """
if r.is_empty():
return 0
elif (not r.root.left) and (not r.root.right):
return 1
else:
return r.root.left.leaves_count(r.root.left) + r.root.right.leaves_count(r.root.right)
if __name__ == '__main__':
"""二叉树"""
ra, rb, rc, rd, re, rf = tree(), tree(), tree(), tree(), tree(), tree()
ra.maketree("a", none, none)
rb.maketree("b", none, none)
rc.maketree("c", none, none)
rd.maketree("d", none, none)
re.maketree("e", none, none)
rf.maketree("f", none, none)
r1, r2, r3, r4, r = tree(), tree(), tree(), tree(), tree()
r1.maketree("-", rc, rd)
r2.maketree("*", rb, r1)
r3.maketree("+", ra, r2)
r4.maketree("/", re, rf)
r.maketree("-", r3, r4)
r.preorder(r)
r.inorder(r)
r.postorder(r)
r.levelorder(r)
print r.leaves_count(r)
大学的时候学过kmp算法,最近在看的时候发现竟然忘了,所以去重新看了看书,然后用python写下了这个算法:
如对本文有疑问,请在下面进行留言讨论,广大热心网友会与你互动!! 点击进行留言回复
Python 实现将numpy中的nan和inf,nan替换成对应的均值
python爬虫把url链接编码成gbk2312格式过程解析
网友评论