二叉树的三种遍历方式

二叉树的三种遍历方式

Scroll Down

1.先序遍历:

按照根节点->左子树->右子树的顺序访问二叉树

先序遍历:(1)访问根节点;(2)采用先序递归遍历左子树;(3)采用先序递归遍历右子树;

(注:每个节点的分支都遵循上述的访问顺序,体现“递归调用”)

先序遍历结果:A BDFE CGHI

思维过程:

  • (1) 先访问根节点A,

  • (2)A分为左右两个子树,因为是递归调用,所以左子树也遵循“先根节点-再左-再右”的顺序,所以访问B节点,

  • (3) 然后访问D节点,

  • (4) 访问F节点的时候有分支,同样遵循“先根节点-再左--再右”的顺序,

  • (5) 访问E节点,此时左边的大的子树已经访问完毕,

  • (6) 然后遵循最后访问右子树的顺序,访问右边大的子树,右边大子树同样先访问根节点C,

  • (7) 访问左子树G,

  • (8) 因为G的左子树没有,所以接下俩访问G的右子树H,

  • (9) 最后访问C的右子树I

2.中序遍历:

按照左子树->根节点->右子树的顺序访问


中序遍历:(1)采用中序遍历左子树;(2)访问根节点;(3)采用中序遍历右子树

中序遍历结果:DBEFAGHCI

3.后序遍历:

按照左子树->右子树-->根节点的顺序访问

后序遍历:(1)采用后序递归遍历左子树;(2)采用后序递归遍历右子树;(3)访问根节点;

后序遍历的结果:DEFB HGIC A