问题

用递归方式遍历二叉树

思路说明

遍历二叉树的方法有广度优先和深度优先两类,下面阐述的是深度优先。

以下图的二叉树为例:

二叉树之递归方法遍历 - 图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. #! /usr/bin/env python
  2. #coding:utf-8
  3. from collections import namedtuple
  4. from sys import stdout
  5. Node= namedtuple('Node','data, left, right')
  6. tree =Node(1,
  7. Node(2,
  8. Node(4,
  9. Node(7,None,None),
  10. None),
  11. Node(5,None,None)),
  12. Node(3,
  13. Node(6,
  14. Node(8,None,None),
  15. Node(9,None,None)),
  16. None))
  17. #前序(pre-order,NLR)
  18. def preorder(node):
  19. if node isnotNone:
  20. print node.data,
  21. preorder(node.left)
  22. preorder(node.right)
  23. #中序(in-order,LNR)
  24. def inorder(node):
  25. if node isnotNone:
  26. inorder(node.left)
  27. print node.data,
  28. inorder(node.right)
  29. #后序(post-order,LRN)
  30. def postorder(node):
  31. if node isnotNone:
  32. postorder(node.left)
  33. postorder(node.right)
  34. print node.data,
  35. #层序(level-order)
  36. def levelorder(node, more=None):
  37. if node isnotNone:
  38. if more isNone:
  39. more =[]
  40. more +=[node.left, node.right]
  41. print node.data,
  42. if more:
  43. levelorder(more[0], more[1:])
  44. if __name__=="__main__"
  45. print' preorder: ',
  46. preorder(tree)
  47. print'\t\n inorder: ',
  48. inorder(tree)
  49. print'\t\n postorder: ',
  50. postorder(tree)
  51. print'\t\nlevelorder: ',
  52. levelorder(tree)
  53. print'\n'