class BinaryTree:
'''定义一个树'''
def __init__(self):
self.val = None
self.left = None
self.right = None
'''前序遍历建树'''
def bulidTree(self,arrs):
if not len(arrs):
return None
if arrs[0] == None:
self.val = None
arrs.pop(0)
return
else:
self.val = arrs[0]
arrs.pop(0)
self.left = BinaryTree()
self.right = BinaryTree()
self.left.bulidTree(arrs)
self.right.bulidTree(arrs)
'''层序遍历建树'''
def levelBulidTree(self,arrs):
if len(arrs) == 0:
return
queue = []#构建队列
queue.append(arrs[0])
self.val = queue[0]
arrs.pop(0)
def levelTravel(self,arrs,queue): #递归建树
if len(queue) <= 0 or len(arrs) <= 0:
return
if self.left != None and self.right != None:
queue.pop(0) #左右子树均不为空时 pop出去首位
if self.left.val == queue[0]:
levelTravel(self.left, arrs, queue)
if self.right.val == queue[0]:
levelTravel(self.right, arrs, queue)
return
if self.left == None :
self.left = BinaryTree()
self.left.val = arrs[0]
if len(arrs) > 0:
queue.append(arrs[0])
arrs.pop(0)
elif self.right == None:
self.right = BinaryTree()
self.right.val = arrs[0]
if len(arrs) > 0:
queue.append(arrs[0])
arrs.pop(0)
levelTravel(self,arrs,queue)
return
levelTravel(self,arrs,queue)
'''前序遍历树'''
def preTravel(self):
if self.val == None or self.val == 'null':
print(self.val,end = ' ')
return
else:
print(self.val,end = ' ')
if self.left != None:
self.left.preTravel()
if self.right != None:
self.right.preTravel()
a = BinaryTree()
arrs = [5,1,4,'null','null',3,6]
a.levelBulidTree(arrs)
a.preTravel()
