#M8016. 二叉树遍历
二叉树遍历
二叉树的遍历
所谓的遍历是指按一定的规律和次序访问树中的各个节点,而且每个节点仅被访问一次。遍历一般按照从左到右的顺序,共有 4 种遍历方法:前序遍历、中序遍历、后序遍历、层次遍历。
前序遍历
先序遍历:先访问根节点,再访问左子树,最后访问右子树。
根节点 --> 左子树 --> 右子树
中序遍历
中序遍历:先左子树,再根节点,最后右子树。
左子树 --> 根节点 --> 右子树
后序遍历
后序遍历:先左子树,再右子树,最后根节点。
左子树 --> 右子树 --> 根子树
层次遍历
层次遍历:每一层从左到右访问每一个节点。
例如:求下列二叉树的各种遍历
先序遍历结果:A B D F E C G H I
中序遍历结果:D B E F A G H C I
后序遍历结果:D E F B H G I C A
层次遍历结果:A B C D F G I E H