# encoding=utf-8
# https://www.cnblogs.com/dongyangblog/p/11210820.html
# 0
# 1 2
# 3 4 5 6
class BinaryTree:
def __init__(self, data):
self.data = data
self.lchild = None
self.rchild = None
def get(self):
return self.data
def getlchild(self):
return self.lchild
def getrchild(self):
return self.rchild
def setlchild(self, node):
self.lchild = node
def setrchild(self, node):
self.rchild = node
binaryTree = BinaryTree(0)
binaryTree.setlchild(BinaryTree(1))
binaryTree.setrchild(BinaryTree(2))
binaryTree.getlchild().setlchild(BinaryTree(3))
binaryTree.getlchild().setrchild(BinaryTree(4))
binaryTree.getrchild().setlchild(BinaryTree(5))
binaryTree.getrchild().setrchild(BinaryTree(6))
# def preorder(bitree, result=[]):
# if bitree == None:
# return result
# result.append(bitree.data)
# preorder(bitree.lchild, result)
# preorder(bitree.rchild, result)
# return result
#
#
# def intermediate(bitree, result=[]):
# if bitree == None:
# return result
# intermediate(bitree.lchild, result)
# result.append(bitree.data)
# intermediate(bitree.rchild, result)
# return result
#
#
# def postorder(bitree, result=[]):
# if bitree == None:
# return
# postorder(bitree.lchild, result)
# postorder(bitree.rchild, result)
# result.append(bitree.data)
# return result
# 先序
def preorder(root): # 先序
stack = []
while stack or root:
while root:
print(root.data)
stack.append(root)
root = root.lchild
root = stack.pop()
root = root.rchild
# 中序
def inorder(root): # 中序
stack = []
while stack or root:
while root:
stack.append(root)
root = root.lchild
root = stack.pop()
print(root.data)
root = root.rchild
# 后序
def postorder(root): # 后序
stack = []
while stack or root:
while root:
stack.append(root)
if root.lchild:
root = root.lchild
else:
root = root.rchild
# root = root.lchild if root.lchild else root.rchild
root = stack.pop()
print(root.data)
if stack and stack[-1].lchild == root:
root = stack[-1].rchild
else:
root = None
# 层次遍历
def levelOrder(root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
if not root:
return []
res = []
queue = [root]
while queue:
# 获取当前队列的长度，这个长度相当于 当前这一层的节点个数
size = len(queue)
tmp = []
# 将队列中的元素都拿出来(也就是获取这一层的节点)，放到临时list中
# 如果节点的左/右子树不为空，也放入队列中
for _ in range(size):
r = queue.pop(0)
tmp.append(r.data)
if r.lchild:
queue.append(r.lchild)
if r.rchild:
queue.append(r.rchild)
# 将临时list加入最终返回结果中
res.append(tmp)
return res
# 层次遍历
print(levelOrder(binaryTree))
#非递归 前中后遍历
# print(preorder(binaryTree))
# print(inorder(binaryTree))
# print(postorder(binaryTree))
