问题

用递归方式遍历二叉树

思路说明

遍历二叉树的方法有广度优先和深度优先两类，下面阐述的是深度优先。 以下图的二叉树为例： 二叉树之递归方法遍历 - 图1 先定义三个符号标记：

  • 访问结点本身（N）
  • 遍历该结点的左子树（L）
  • 遍历该结点的右子树（R）

有四种方式：

  1. 前序遍历(PreorderTraversal,NLR):先访问根结点，然后遍历其左右子树
  2. 中序遍历(InorderTraversal,LNR):先访问左子树，然后访问根节点，再访问右子树
  3. 后序遍历(PostorderTraversal,LRN):先访问左右子树，再访问根结点
  4. 层序遍历(levelorderTraversal):按照从上到下的层顺序访问

上面的数，按照以上四种方式遍历，得到的结果依次是：

  1. preorder: 1 2 4 7 5 3 6 8 9
  2. inorder: 7 4 2 5 1 8 6 9 3
  3. postorder: 7 4 5 2 8 9 6 3 1
  4. level-order: 1 2 3 4 5 6 7 8 9

下面用递归的方式，解决此题。

解决(Python)

  1.   1. #! /usr/bin/env python
  2.     2. #coding:utf-8
  3.     3.   4. from collections import namedtuple
  4.     5. from sys import stdout
  5.     6.   7. Node = namedtuple('Node', 'data, left, right')
  6.     8. tree = Node(1,
  7.     9.             Node(2,
  8.     10.                  Node(4,
  9.     11.                       Node(7, None, None),
  10.     12.                       None),
  11.     13.                  Node(5, None, None)),
  12.     14.             Node(3,
  13.     15.                  Node(6,
  14.     16.                       Node(8, None, None),
  15.     17.                       Node(9, None, None)),
  16.     18.                  None))
  17.     19.   20.   21. #前序（pre-order，NLR）
  18.     22.   23. def preorder(node):
  19.     24.     if node is not None:
  20.     25.         print node.data,
  21.     26.         preorder(node.left)
  22.     27.         preorder(node.right)
  23.     28.   29.   30. #中序（in-order，LNR）
  24.     31.   32. def inorder(node):
  25.     33.     if node is not None:
  26.     34.         inorder(node.left)
  27.     35.         print node.data,
  28.     36.         inorder(node.right)
  29.     37.   38.   39. #后序（post-order，LRN）
  30.     40.   41. def postorder(node):
  31.     42.     if node is not None:
  32.     43.         postorder(node.left)
  33.     44.         postorder(node.right)
  34.     45.         print node.data,
  35.     46.   47.   48. #层序（level-order）
  36.     49.   50. def levelorder(node, more=None):
  37.     51.     if node is not None:
  38.     52.         if more is None:
  39.     53.             more = []
  40.     54.         more += [node.left, node.right]
  41.     55.         print node.data,
  42.     56.     if more:    
  43.     57.         levelorder(more[0], more[1:])
  44.     58.   59. if __name__=="__main__"
  45.     60.     print '  preorder: ',
  46.     61.     preorder(tree)
  47.     62.     print '\t\n   inorder: ',
  48.     63.     inorder(tree)
  49.     64.     print '\t\n postorder: ',
  50.     65.     postorder(tree)
  51.     66.     print '\t\nlevelorder: ',
  52.     67.     levelorder(tree)
  53.     68.     print '\n'

整理人：豆包AI助手