class Node: # 定义树节点
def __init__(self, value, left=None, right=None): # 节点的值及左子树、右子树
self.value = value
self.left = left
self.right = right
class Tree: # 定义二叉树
def __init__(self, list):
self.list = list
self.build_tree()
def build_tree(self): # 构建二叉树，从上到下，从左往右
nodelist = [] # 构建节点列表
for i in range(len(list)):
nodelist.append(Node(list[i])) # 将列表元素添加至节点列表
self.root = nodelist[0] # 树的根节点
for i in range(len(list) // 2): # 遍历节点，构建二叉树
nodelist[i].left = nodelist[i * 2 + 1]
if i * 2 + 2 < len(nodelist):
nodelist[i].right = nodelist[i * 2 + 2]
def recursive_pre_order(self, nodelist, node): # 递归前序遍历，输出顺序：父节点，左子树，右子树
if node is not None:
nodelist.append(node.value)
self.recursive_pre_order(nodelist, node.left)
self.recursive_pre_order(nodelist, node.right)
return nodelist
def recursive_in_order(self, nodelist, node): # 递归中序遍历，输出顺序：左子树，父节点，右子树
if node is not None:
self.recursive_in_order(nodelist, node.left)
nodelist.append(node.value)
self.recursive_in_order(nodelist, node.right)
return nodelist
def recursive_post_order(self, nodelist, node): # 递归后序遍历，输出顺序：左子树，右子树，父节点
if node is not None:
self.recursive_post_order(nodelist, node.left)
self.recursive_post_order(nodelist, node.right)
nodelist.append(node.value)
return nodelist
@staticmethod
def not_recursive_pre_order(self, node): # 非递归前序遍历，输出顺序：父节点，左子树，右子树
if node is not None:
stack = [node] # 将根节点压入栈
while len(stack) > 0:
print(node.value, end=" ")
if node.right is not None: # 根据栈先进后出的特点，将子节点压栈的时候，先将右子树压入栈
stack.append(node.right)
if node.left is not None: # 将左子树压入栈
stack.append(node.left)
node = stack.pop() # 将栈顶元素弹出
@staticmethod
def not_recursive_in_order(self, node): # 非递归中序遍历，输出顺序：左子树，父节点，右子树
if node is not None:
stack = []
temp = node # 将根节点复制给中间变量
while temp is not None or len(stack) > 0:
if temp is not None:
stack.append(temp)
temp = temp.left # 中序遍历先遍历节点的左子树
else:
temp = stack.pop() # 将栈顶元素弹出
print(temp.value, end=" ") # 输出栈顶元素的值
temp = temp.right # 检查右子树
@staticmethod
def not_recursive_post_order(self, node): # 非递归后序遍历，输出顺序：左子树，右子树，父节点
stack1 = [node] # 栈 1 遍历二叉树
stack2 = [] # 栈 2 存储输出顺序
while len(stack1) > 0:
node = stack1.pop()
stack2.append(node) # 将父节点压入栈底
if node.left is not None:
stack1.append(node.left) # 左子树压入栈
if node.right is not None:
stack1.append(node.right) # 右子树压入栈
while len(stack2) > 0:
print(stack2.pop().value, end=" ") # 输出顺序
if __name__ == '__main__':
list = [1, 2, 3, 4]
tree = Tree(list)
print("递归前序排列")
retList = tree.recursive_pre_order([], tree.root)
print(retList)
print("非递归前序排列")
tree.not_recursive_pre_order(tree, tree.root)
print("
递归中序排列")
retList = tree.recursive_in_order([], tree.root)
print(retList)
print("非递归中序排列")
tree.not_recursive_in_order(tree, tree.root)
print("
递归后序排列")
retList = tree.recursive_post_order([], tree.root)
print(retList)
print("非递归后序排列")
tree.not_recursive_post_order(tree, tree.root)
递归的方法即不断调用自身，非递归采用入栈出栈完成二叉树的遍历