python —— 树的遍历 —— 深度优先遍历（先序、中序、后序） —— 非递归方式（使用栈数据结构进行辅助）

代码：（以下示例使用先序遍历）

# 2**n - 1  # 全二叉树
# n=4 2**4 - 1 = 15
import random
node_v = [2,3,5,7,11,0,17,19,23,0,0,0,0,41,43]
# node_v = list(range(0, 15))
# random.shuffle(node_v)
# print(node_v) # [14, 4, 12, 0, 1, 13, 9, 11, 3, 5, 6, 10, 2, 7, 8]# [0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14]
class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = right 
node_list = [TreeNode(i) for i in node_v] # 初始化生成所有节点
node_list[5], node_list[9], node_list[10], node_list[11], node_list[12] = None, None, None, None, None
print(node_list)for i in range(len(node_list)):           # 将父节点与左右节点进行连接node = node_list[i]  # TreeNode对象if 2*i+1 < len(node_list):if node != None:node.left = node_list[2*i+1]  # node.left == Noneif 2*i+2 < len(node_list):if node != None:node.right = node_list[2*i+2]root_node = node_list[0]def preorder_traversal(root):if root is None:return None # return [root.val] + preorder_traversal(root.left) + preorder_traversal(root.right)print(root.val)preorder_traversal(root.left)preorder_traversal(root.right)def midorder_traversal(root):if root is None:return None # return [root.val] + preorder_traversal(root.left) + preorder_traversal(root.right)midorder_traversal(root.left)print(root.val)midorder_traversal(root.right)def postorder_traversal(root):if root is None:return None # return [root.val] + preorder_traversal(root.left) + preorder_traversal(root.right)postorder_traversal(root.left)postorder_traversal(root.right)print(root.val)# preorder_traversal(root_node)
# midorder_traversal(root_node)
# postorder_traversal(root_node)preorder_traversal(root_node)print("---------------------")stack = [root_node, ]while stack:node = stack.pop()print(node.val)if node.right is not None:stack.append(node.right)if node.left is not None:stack.append(node.left)print("---------------------")node = root_nodewhile True:print(node.val)if node.right is not None:stack.append(node.right)if node.left is not None:# stack.append(node.left)node = node.leftelse:if stack:node = stack.pop()else:break

运行效果：