二叉树的三种遍历方式
2019-03-05| 程成| 33| 0| other

一、先序遍历


访问顺序:根结点-->左子树-->右子树


image.png


先序遍历:(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



二、中序遍历


访问顺序:左子树-->根结点-->右子树


image.png


中序遍历:(1)中序递归遍历左子树;(2)访问根结点;(3)中序递归遍历右子树;


中序遍历结果:

DBEF A GHCI



三、后序遍历


访问顺序:左子树-->右子树-->根结点


image.png


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


后序遍历的结果:

DEFB HGIC A

 


小结:三种方法遍历过程中经过节点的路线一样;只是访问各个节点的时机不同。


原文地址:https://blog.csdn.net/qq_40772692/article/details/79343914



下一篇:没有下一篇了
×
作者:程成
QQ:492245711