您当前位置是:首页>>系统教程>>已知中序和后序遍历,画二叉树,写出前序遍历的详细步骤
已知中序和后序遍历,画二叉树,写出前序遍历的详细步骤
更新时间:2018-12-21浏览:

      很多小伙伴在哥哥学习编程的时候,在二叉树这边遇到问难,各种前中后遍历也分不清,今天小编整理了关于已知中序遍历和后续遍历,如何画出二叉树,并写出前序遍历的详细方法。
      如图,例子来说明。知道中序和后序遍历,画二叉树和写出前序遍历。

已知中序和后序遍历,画二叉树,写出前序遍历的详细步骤
      从后序遍历知道,最后一个必然是根节点,因此A是根。再结合中序遍历可知HDMIBJNE是A的左子树部分,FKCG是右子树部分。
已知中序和后序遍历,画二叉树,写出前序遍历的详细步骤
      取A的右子树部分来看先,右子树部分的中序遍历:FKCE,后序遍历:KFGC。接着从后序遍历中看A的右子树部分KFGC,所以C是根。又从中序遍历知,FK是C的左子树部分,G是C右子树。如图所示
已知中序和后序遍历,画二叉树,写出前序遍历的详细步骤
      使用同样的方法,C的左子树部分,中序:FK,后序:KF。可以得出F是根,那么K只能是F的右子树了。此时如图所示,A的右子树部分都出来了
已知中序和后序遍历,画二叉树,写出前序遍历的详细步骤
      再看,A的左子树部分HDMIBJE,中序:HDMIBJNE,后序:HMIDNJEB。后序遍历可知,B是根结点,那么再结合中序遍历可知道HDMI是B的左子树部分,JNE是B的右子树部分。
已知中序和后序遍历,画二叉树,写出前序遍历的详细步骤
      紧接着就是看B的左子树部分HDMI,中序:HDMI,后序:HMID,可知D是根,H是D的左子树,MI是D的右子树部分,如图所示。
已知中序和后序遍历,画二叉树,写出前序遍历的详细步骤
      看到D的右子树部分,中序后序都是MI,根据后序中序的特性可知道,根只能是I,M是I的左子树。
已知中序和后序遍历,画二叉树,写出前序遍历的详细步骤
      再接着看看B的右子树部分JNE,中序:JNE,后序:NJE,后序看出E是根,中序看出E无右子树,只有JN是E的左子树部分。
已知中序和后序遍历,画二叉树,写出前序遍历的详细步骤
      最后看JN的中序:JN,后序:NJ,根据后序特性看出,J是根,中序看出N是J的右子树。那么整体的二叉树就出来了,如图所示。
已知中序和后序遍历,画二叉树,写出前序遍历的详细步骤
      以上就是关于已知中序和后序遍历,画二叉树,写出前序遍历的详细步骤。小编最后小提示:其实只要知道任意两个遍历,即可画出应有的二叉树,与是否是满二叉树无关!!!记住记住!!!

更多>>Win7主题下载排行
更多>>XP主题下载排行
更多>>系统热门教程