二叉树的建立与检索

2017-10-14  本文已影响0人  苟且偷生小屁屁

-- coding: utf-8 --

"""
Created on Mon Apr 03 19:58:58 2017

@author: Administrator
"""

class node(object):
def init(self, data=None, left=None, right=None):
self.data = data
self.left = left
self.right = right

深度

def depth(tree):
if tree == None:
return 0
left, right = depth(tree.left), depth(tree.right)
return max(left, right) + 1

前序遍历

def pre_order(tree):
if tree == None:
return
print tree.data
pre_order(tree.left)
pre_order(tree.right)

中序遍历

def mid_order(tree):
if tree == None:
return
mid_order(tree.left)
print tree.data
mid_order(tree.right)

后序遍历

def post_order(tree):
if tree == None:
return
post_order(tree.left)
post_order(tree.right)
print tree.data

层次遍历

def level_order(tree):
if tree == None:
return
q = []
q.append(tree)
while q:
current = q.pop(0)
print current.data
if current.left != None:
q.append(current.left)
if current.right != None:
q.append(current.right)

按层次打印

def level2_order(tree):
if tree == None:
return
q = []
q.append(tree)
results = {}
level = 0
current_level_num = 1
nextlevelnum = 0
d = []
while q:
current = q.pop(0)
current_level_num -= 1
d.append(current.data)
if current.left != None:
q.append(current.left)
nextlevelnum += 1
if current.right != None:
q.append(current.right)
nextlevelnum += 1
if current_level_num == 0:
current_level_num = nextlevelnum
nextlevelnum = 0
results[level] = d
d = []
level += 1
print results

if name == 'main':
tree = node('D', node('B', node('A'), node('C')), node('E', right=node('G', node('F'))))
print'前序遍历:'
pre_order(tree)
print('\n')
print('中序遍历:')
mid_order(tree)
print('\n')
print '后序遍历:'
post_order(tree)
print('\n')
print '层次遍历'
level_order(tree)
print('\n')
print "层次遍历"
level2_order(tree)

EM,分治法,GMM, 深度优先, 广度优先, 满二叉树, 完全二叉树, 随机森林

上一篇 下一篇

猜你喜欢

热点阅读