前序遍历:根节点->左子树->右子树(根->左->右)
中序遍历:左子树->根节点->右子树(左->根->右)
后序遍历:左子树->右子树->根节点(左->右->根)
技巧:看根节点打印的顺序,出现在前还是中,后.
前序遍历:GDAFEMHZ
中序遍历: ADEFGHMZ
后序遍历:AEFDHZMG
前序:
第一步:打印该节点(再三考虑还是把访问根节点这句话去掉了)
第二步:访问左子树,返回到第一步(注意:返回到第一步的意思是将根节点的左子树作为新的根节点,就好比图中D是G的左子树但是D也是A节点和F节点的根节点)
第三步:访问右子树,返回到第一步
第四步:结束递归,返回到上一个节点
中序:
第一步:访问该节点左子树
第二步:若该节点有左子树,则返回第一步,否则打印该节点
第三步:若该节点有右子树,则返回第一步,否则结束递归并返回上一节点
(按我自己理解的中序就是:先左到底,左到不能在左了就停下来并打印该节点,然后返回到该节点的上一节点,并打印该节点,然后再访问该节点的右子树,再左到不能再左了就停下来)
后序:
第一步:访问左子树
第二步:若该节点有左子树,返回第一步
第三步:若该节点有右子树,返回第一步,否则打印该节点并返回上一节点
后序遍历的另一种表述:
(1)后序遍历左子树
(2)后序遍历右子树
(3)访问根节点
(在完成1,2步的时候,依然要按照后序遍历的规则来完成)
案例分析
第一种:已知前序遍历、中序遍历求后序遍历
前序遍历:ABCDEF
中序遍历:CBDAEF
求后序遍历?
解题思路
1、前序遍历的第一元素是整个二叉树的根节点
2、中序遍历中根节点的左边的元素是左子树,根节点右边的元素是右子树
3、后序遍历的最后一个元素是整个二叉树的根节点
第一步:先看前序遍历A肯定是根节点
第二步:确认了根节点,再来看中序遍历,中序遍历中根节点A的左边是CBD,右边是EF,所有可以确定二叉树既有左子树又有右子树
第三步:先来分析左子树CBD,那么CBD谁来做A的左子树呢?这个时候不能直接用中序遍历的特点(左->根->右)得出左子树应该是这个样子
因为有两种情况都满足中序遍历为CBD无法直接根据中序遍历来直接得出左子树的结构,这个时候就要返回到前序遍历中去
观察前序遍历ABCDEF,左子树CBD在前序遍历中的顺序是BCD,意味着B是左子树的根节点(这么说可能不太好理解,换个说法就是B是A的左子树),得出这个结果是因为如果一个二叉树的根节点有左子树,那么
这个左子树一定在前序遍历中一定紧跟着根节点(这个是用前序遍历的特点(根->左->右)得出的),到这里就可以确认B是左子树的根节点
第四步:再观察中序遍历CBDAEF,B元素左边是C右边是D,说明B节点既有左子树又有右子树,左右子树只有一个元素就可以直接确定了,不用再返回去观察前序遍历
第五步:到这里左子树的重建就已经完成了,现在重建右子树,因为重建右子树的过程和左子树的过程一模一样,步骤就不像上面写这么细了((┬_┬)),观察中序遍历右子树为EF,再观察前序遍历ABCDEF中右子树
的顺序为EF,所以E为A的右子树,再观察中序便利中E只有右边有F,所有F为E的右子树,最后得到的二叉树是这个样子的
所以求得的后序遍历为:CDBFEA
总结一下上述步骤: 先观察前序遍历找到根节点->观察中序遍历将根节点左边归为左子树元素,右边归为右子树元素(可能会出现只有左子树或者右子树的情况)->观察前序遍历中左\右子树几个元素的顺序,最靠前的为左\右子树的根节点->重复前面的步骤
第二种:已知中序遍历、后序遍历求前序遍历(题还是上面这道)
中序遍历:CBDAEF
后序遍历为:CDBFEA
仍然是根据不同遍历方式结果的特点来重构二叉树,过程很相似这里就不详细说了,后序遍历的最后一个元素A是根节点,在中序遍历中以根节点A作为分界将元素分为左子树(CBD)和右子树(EF),再观察后序遍历中左子树的顺序是CDB
,可以判断出B是左子树的根节点(因为后序遍历是:左->右->根),再观察中序遍历,B元素左边是C右边是D,说明B节点既有左子树又有右子树,左右子树只有一个元素就可以直接确定了,不用再返回去观察后序遍历,左子树重建完成,
现在来看右子树,右子树有两个元素EF,观察后序遍历E在F的后面,所以E是右子树的根节点,然后看中序遍历中E只有右边一个F元素了,即F是E的右子树,此时整个二叉树重构完成
总结一下上述步骤:先观察后序遍历找到根节点->观察中序遍历将根节点左边归为左子树元素,右边归为右子树元素(可能会出现只有左子树或者右子树的情况)->观察后序遍历中左\右子树几个元素的顺序,最靠后的为左\右子树的根节点->重复前面的步骤
注意:已知前序遍历、后序遍历无法求出中序遍历(因为由前序后序重构出来的二叉树不止一种)
前序遍历
1 /* 以递归方式 前序遍历二叉树 */
2 void PreOrderTraverse(BiTree t, int level)
3 {
4 if (t == NULL)
5 {
6 return ;
7 }
8 printf("data = %c level = %d\n ", t->data, level);
9 PreOrderTraverse(t->lchild, level + 1);
10 PreOrderTraverse(t->rchild, level + 1);
11 }
中序遍历
1 /* 以递归方式 中序遍历二叉树 */
2 void PreOrderTraverse(BiTree t, int level)
3 {
4 if (t == NULL)
5 {
6 return ;
7 }
8 PreOrderTraverse(t->lchild, level + 1);
9 printf("data = %c level = %d\n ", t->data, level);
10 PreOrderTraverse(t->rchild, level + 1);
11 }
后序遍历
1 /* 以递归方式 后序遍历二叉树 */
2 void PreOrderTraverse(BiTree t, int level)
3 {
4 if (t == NULL)
5 {
6 return ;
7 }
8 PreOrderTraverse(t->lchild, level + 1);
9 PreOrderTraverse(t->rchild, level + 1);
10 printf("data = %c level = %d\n ", t->data, level);
11 }
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)