新手易懂：已知二叉樹先序和中序繪制二叉樹和已知中序和后序繪制二叉樹，
1：先序和中序
例題：
先序：ABDFCEGHI
中序：BFDACHGIE
第一步：先序第一個結點是根結點，在中序中找到根點（此題中是A），以A為分界將中序分為BFD（左子樹）和CHGIE（右子樹）兩部分，
第二步：看BFD序列中誰第一個出現在先序序列中，此題是B；同理可知CHGIE中第一個是C；
可得到下圖：
第三步：需知道相鄰序列同序和逆序的圖形，
當先序和中序出現相鄰的序列逆序，是下圖：
相鄰序列同序，如下圖
實戰演練環節：(我們一般是走先序的）
先序：ABDFCEGHI
中序：BFDACHGIE
畫二叉樹：
結合上文易得：
再看先序和后序可知出現逆序DF和FD，便可再畫一步：
DF連接如下：
而在中序序列中DF與B相鄰且在其后面，可得到DF在B的右面(中序前面是左子樹，后面是右子樹），
再由先序知C后面是E,我們再看CE再先序和中序中是同序還是逆序可知CE是同序,則CE便是右連接:
接著走先序出現先序和中序出現GH逆序情況，
先序接著往下走，我們由中序可知i在G的右側，即如下
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/235586.html
標籤：其他