知道中序遍歷和后續遍歷,若何畫出二叉樹,并寫出前序遍歷。其實只要知道肆意兩個遍歷,即可畫出應有的二叉樹,與是否是滿二叉樹無關!!!
如圖,例子來申明。知道中序和后序遍歷,畫二叉樹和寫出前序遍歷。
從后序遍歷知道,最后一個必然是根節點,是以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的右子樹。那么整體的二叉樹就出來了,如圖所示。
已知中序遍歷:ACQVLCOJYPRKSXG
后序遍歷:AVQCOCJLRSKPGXY
畫出二叉樹,并寫出前序遍歷。
二叉樹如圖所示,前序遍歷是YLCAQVJCOXPKRSG
0 篇文章
如果覺得我的文章對您有用,請隨意打賞。你的支持將鼓勵我繼續創作!