你的位置:首页 > 数据库

[数据库]遍历二叉树顺序


image

二叉树的遍历顺序有:前向遍历、中序遍历、后续遍历、按层遍历四种。

前向遍历:先根节点再左子树后右子树。

image

中序遍历:先左子树再根节点后右子树。(投影法快速实现遍历)。

image

后续遍历:先左子树再右子树后根节点

image

按层遍历:ABECDFG。

二、二叉树的重构。

已知一棵二叉树的先序遍历和中序遍历序列分别为:

先序: A B C I D E F H G  

中序:C I B E D A H F G

先由先序遍历得知A为根,再由中序得知CIBED为左子树。再由先序得到各节点位置。

image