淘先锋技术网

首页 1 2 3 4 5 6 7

遍历是针对根节点的

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

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

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

 

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

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

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

 

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

 

说明

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

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

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

 

举个例子来看懂树的排序

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

解:

  1. 根据前序遍历ABDECF,A肯定是根节点(第一个遍历根节点)。对照中序遍历,就能知道DBE是左子树,FC是右子树。
  2. 左子树:中序DBE,前序是BDE;说明B是左子树的根节点,D是B的左孩子,E是右孩子。
  3. 右子树类似:C是右子树的根节点,F是C的左孩子(因为中序遍历中F是在C前面的,所以一定是左孩子;如果F在C的后面,就是右孩子)
  4. 后序遍历DEBFCA

 

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

 

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

 

算法程序:

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