数据结构-树-树的前序、中序、后序遍历详解

树的前序遍历、中序遍历、后序遍历详解

zlingyun
遍历是针对根节点的

前序遍历顺序：根节点--左子树--右子树, 根左右

中序遍历顺序：左子树--根节点--右子树, 左根右

后序遍历顺序：左子树--右子树--根节点, 左右根

 

深入一点去理解这个排序顺序是这样的

前序遍历首先访问根结点，然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。
中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。在遍历左、右子树时，仍然先遍历左子树，再访问根结点，最后遍历右子树。

后序遍历首先遍历左子树，然后遍历右子树，最后访问根节点。在遍历左、右子树时，仍然先遍历左子树，再遍历右子树，最后访问根结点。

 

也就是说我们在遍历的时候必然是一层一层去寻找，并且不断递归。

 

说明

已知前序遍历与中序遍历，可确定唯一二叉树；

已知中序遍历与后序遍历，可确定唯一二叉树；

但是已知前序遍历与后序遍历，无法确定唯一二叉树。

确定唯一二叉树

举个例子来看懂树的排序

如果我们已知中序遍历是DBEAFC，前序遍历是ABDECF，求后序遍历。

解：

根据前序遍历ABDECF，A肯定是根节点（第一个遍历根节点）。对照中序遍历，就能知道DBE是左子树，FC是右子树。
左子树：中序DBE，前序是BDE；说明B是左子树的根节点，D是B的左孩子，E是右孩子。
右子树类似：C是右子树的根节点，F是C的左孩子（因为中序遍历中F是在C前面的，所以一定是左孩子；如果F在C的后面，就是右孩子）
后序遍历DEBFCA
 

所以我们已知树去写三种不同的遍历的时候，就是不断的把树拆分成左子树，根节点，右子树，一级一级的拆分下去。最终获得最小的二叉树，可以轻易的写出来顺序。

 

或者我们已知两种遍历结果（前提是可以唯一确定二叉树），我们根据前序遍历或者后续遍历可以立即得到根节点是什么，根据根节点将中序遍历拆分，立即获得左子树与右子树内容。在一级一级的拆分下去。可获得完整的二叉树结构。

算法程序：

https://blog.csdn.net/Su_coding/article/details/70196173

原文链接：https://blog.csdn.net/zlingyun/article/details/81209058