c++中树的后序的第一个结点

c++中树的后序的第一个结点

娜样滴歌杰出肤 · 2018-4-30 01:48:55

二叉树的遍历是指按照一定次序访问树中所有结点，并且每个节点仅被访问一次的过程。
1、先序遍历（前序）
（1）访问根节点；
（2）先序遍历左子树；
（3）先序遍历右子树。
2、中序遍历
（1）中序遍历左子树；
（2）访问根节点；
（3）中序遍历右子树。
3、后序遍历
（1）后序遍历左子树；
（2）后序遍历右子树‘
（3）访问根节点。
记住访问根结点的时机就可以区分三种遍历方法了。
同时知道一棵二叉树的先序序列和中序序列，或者同时知道中序序列和后序序列，就能确定这棵二叉树的结构。构造算法相信你已经学习过，在任一本介绍数据结构的书上应该也有描述的。由于涉及到算法细节，这里就不细说了。
下面根据你例子中给出的序列来介绍确定二叉树结构的步骤：
（1）后序序列中最后一个为树的根节点，即c为二叉树的根结点；
（2）中序遍历中根节点把序列分为左右子树的中序遍历序列两个部分，在你的例子在右子树没有中序遍历序列（中序遍历序列中c右边没有序列），故可知二叉树的左子树的后序遍历序列为dabe，中序遍历序列为deba；
（3）应用（1）的方法，确定c的左子树的根结点为e，并把以e为根结点的子树的中序遍历序列划分为d（以e为根结点的左子树的中序遍历序列）和ba（以e为根结点的右子树的中序遍历序列）两个部分，后序遍历序列为dab；
（4）应用（1）的方法，可确定e的左结点为b；
（5）应用（1）的方法，可确定e的右结点为a；
（6）最后，可确定a无左结点，右结点为d。
构造的二叉树如图中所示。
那么可获得前序遍历序列为cedba

c++中树的后序的第一个结点

1 个回复