手抄报 安全手抄报 手抄报内容 手抄报图片 英语手抄报 清明节手抄报 节约用水手抄报

知道中序和后序遍历,画二叉树和写出前序遍历

时间:2024-10-11 22:02:31

1、如图,例子来说明。知道中序和后序遍历,画二叉树和写出前序遍历。

知道中序和后序遍历,画二叉树和写出前序遍历

2、从后序遍历知道,最后一个必然是根节点,因此A是根。再结合中序遍历可知HDMIBJNE是A的左子树部分,FKCG是右子树部分。

知道中序和后序遍历,画二叉树和写出前序遍历

3、取A的右子树部分来看先,右子树部分的中序遍历:FKCE,后序遍历:KFGC。接着从后序遍历中看A的右子树部分KFGC,所以C是根。又从中序遍历知,FK是C的左子树部分,G是C右子树。如图所示

知道中序和后序遍历,画二叉树和写出前序遍历

4、使用同样的方法,C的左子树部分,中序:FK,后序:KF。可以得出F是根,那么K只能是F的右子树了。此时如图所示,A的右子树部分都出来了

知道中序和后序遍历,画二叉树和写出前序遍历

5、再看,A的左子树部分HDMIBJE,中序:HDMIBJNE,后序:HMIDNJEB。后序遍历可知,B是根结点,那么再结合中序遍历可知道HDMI是B的左子树部分,JNE是B的右子树部分。

知道中序和后序遍历,画二叉树和写出前序遍历

6、紧接着就是看B的左子树部分HDMI,中序:HDMI,后序:HMID,可知D是根,H是D的左子树,MI是D的右子树部分,如图所示。

知道中序和后序遍历,画二叉树和写出前序遍历

7、看到D的右子树部分,中序后序都是MI,根据后序中序的特性可知道,根只能是I,M是I的左子树。

知道中序和后序遍历,画二叉树和写出前序遍历

8、再接着看看B的右子树部分JNE,中序:JNE,后序:NJE,后序看出E是根,中序看出E无右子树,只有JN是E的左子树部分。

知道中序和后序遍历,画二叉树和写出前序遍历

9、最后看JN的中序:JN,后序:NJ,根据后序特性看出,J是根,中序看出N是J的右子树。那么整体的二叉树就出来了,如图所示。

知道中序和后序遍历,画二叉树和写出前序遍历
© 手抄报圈