回覆列表
  • 1 # 子堯木

    知道中序和後序遍歷,以中序遍歷是: HDMIBJNEAFKCG。後續遍歷是HMIDNJEBKFGCA為例,畫二叉樹和寫出前序遍歷的方法和步驟如下1、從後序遍歷知道,最後一個必然是根節點,因此A是根。再結合中序遍歷可知HDMIBJNE是A的左子樹部分,FKCG是右子樹部分;

    2、取A的右子樹部分來看先,右子樹部分的中序遍歷:FKCE,後序遍歷:KFGC。接著從後序遍歷中看A的右子樹部分KFGC,所以C是根,又從中序遍歷知,FK是C的左子樹部分,G是C右子樹;

    3、使用同樣的方法,C的左子樹部分,中序:FK,後序:KF。可以得出F是根,那麼K只能是F的右子樹了。此時如圖所示,A的右子樹部分都出來了;

    4、再看,A的左子樹部分HDMIBJE,中序:HDMIBJNE,後序:HMIDNJEB。後序遍歷可知,B是根結點,那麼再結合中序遍歷可知道HDMI是B的左子樹部分,JNE是B的右子樹部分;

    5、緊接著就是看B的左子樹部分HDMI,中序:HDMI,後序:HMID,可知D是根,H是D的左子樹,MI是D的右子樹部分;

    6、看到D的右子樹部分,中序後序都是MI,根據後序中序的特性可知道,根只能是I,M是I的左子樹;

    7、再接著看看B的右子樹部分JNE,中序:JNE,後序:NJE,後序看出E是根,中序看出E無右子樹,只有JN是E的左子樹部分;

    8、最後看JN的中序:JN,後序:NJ,根據後序特性看出,J是根,中序看出N是J的右子樹,那麼整體的二叉樹就出來了。

  • 中秋節和大豐收的關聯?
  • 臉上有皺紋怎麼辦該怎辦?