tree_0.svg

堆栈实现

  1. def stack_print(root):
  2.     stack = []
  3.     result = []
  5.     while root or stack:
  6.         while root:
  7.             stack.append(root)
  8.             root = root.left
  10.         if stack:
  11.             root = stack.pop()
  12.             result.append(root.val)
  13.             root = root.right
  15.     return result

递归实现

  1. def recursive_print(root):
  2.     result = []
  4.     def inorder(root):
  5.         if not root:
  6.             return
  8.         inorder(root.left)
  9.         result.append(root.val)
  10.         inorder(root.right)
  12.     inorder(root)
  14.     return result

完整代码

  1. class TreeNode(object):
  3.     def __init__(self, val=None, left=None, right=None):
  4.         self.left = left
  5.         self.right = right
  6.         self.val = val
  8. class BinTree(object):
  10.     def __init__(self, root):
  11.         self.root = root
  13.     def stack_print(self, root):
  14.         """堆栈实现"""
  15.         stack = []
  17.         while root or stack:
  18.             while root:
  19.                 stack.append(root)
  20.                 root = root.left
  22.             if stack:
  23.                 root = stack.pop()
  24.                 print(root.val)
  25.                 root = root.right
  27.     def recursive_print(self, root):
  28.         """递归实现"""
  29.         if not root:
  30.             return
  32.         self.recursive_print(root.left)
  33.         print(root.val)
  34.         self.recursive_print(root.right)
  36. def main():
  37.     left = TreeNode(2, left=TreeNode(4), right=TreeNode(5))
  39.     right = TreeNode(3, left=TreeNode(6), right=TreeNode(7))
  41.     root = TreeNode(1, left=left, right=right)
  43.     tree = BinTree(root)
  45.     print('递归 中序遍历:')
  46.     tree.recursive_print(tree.root)
  47.     print('堆栈 中序遍历:')
  48.     tree.stack_print(tree.root)