二叉樹(shù)前序、中序、后序

1、二叉樹(shù)前序、中序、后序遍歷相互求法岀處：凡程 作者：西西 日期：2013/1/7 15:37:48 大中小評(píng)論：0 |我要發(fā)表看法今天來(lái)總結(jié)下二叉樹(shù)前序、中序、后序遍歷相互求法，即如果知道兩個(gè)的遍歷，如何求第三種遍歷方法，比較笨的方法是畫出來(lái)二叉樹(shù)，然后根據(jù)各種遍歷不同的特性來(lái)求，也可以編程求出，下面我們分別說(shuō)明。首先，我們看看前序、中序、后序遍歷的特性：前序遍歷：1. 訪問(wèn)根節(jié)點(diǎn)2. 前序遍歷左子樹(shù)3. 前序遍歷右子樹(shù)中序遍歷：1. 中序遍歷左子樹(shù)2. 訪問(wèn)根節(jié)點(diǎn)3. 中序遍歷右子樹(shù)后序遍歷：1. 后序遍歷左子樹(shù)2. 后序遍歷右子樹(shù)3. 訪問(wèn)根節(jié)點(diǎn)一、已知前序、中序遍歷，求后序遍歷例：前序遍

2、歷：GDAFEMHZ中序遍歷：ADEFGHMZ畫樹(shù)求法：第一步，根據(jù)前序遍歷的特點(diǎn)，我們知道根結(jié)點(diǎn)為G第二步，觀察中序遍歷 ADEFGHM其中 root節(jié)點(diǎn)G左側(cè)的ADEF必然是root的左子樹(shù)， G右側(cè)的HMZ必然是root的右子樹(shù)。第三步，觀察左子樹(shù) ADEF左子樹(shù)的中的根節(jié)點(diǎn)必然是大樹(shù)的root的leftchild 。在前序遍歷中，大樹(shù)的root的leftchild 位于root之后，所以左子樹(shù)的根節(jié)點(diǎn)為第四步，同樣的道理，root的右子樹(shù)節(jié)點(diǎn)HMZ中的根節(jié)點(diǎn)也可以通過(guò)前序遍歷求得。在前序遍歷中，一定是先把root和root的所有左子樹(shù)節(jié)點(diǎn)遍歷完之后才會(huì)遍歷右子樹(shù)，并且遍歷的左子樹(shù)的第一

3、個(gè)節(jié)點(diǎn)就是左子樹(shù)的根節(jié)點(diǎn)。同理，遍歷的右子樹(shù)的第一個(gè)節(jié)點(diǎn)就是右子樹(shù)的根節(jié)點(diǎn)。第五步，觀察發(fā)現(xiàn)，上面的過(guò)程是遞歸的。先找到當(dāng)前樹(shù)的根節(jié)點(diǎn)，然后劃分為左子樹(shù)，右子樹(shù)，然后進(jìn)入左子樹(shù)重復(fù)上面的過(guò)程，然后進(jìn)入右子樹(shù)重復(fù)上面的過(guò)程。最后就可以還原一棵樹(shù)了。該步遞歸的過(guò)程可以簡(jiǎn)潔表達(dá)如下：1確定根，確定左子樹(shù)，確定右子樹(shù)。2在左子樹(shù)中遞歸。3在右子樹(shù)中遞歸。4打印當(dāng)前根。那么，我們可以畫出這個(gè)二叉樹(shù)的形狀:那么，根據(jù)后序的遍歷規(guī)則，我們可以知道，后序遍歷順序?yàn)椋篈EFDHZMG前序遍歷：GDAFEMHZ中序遍歷：ADEFGHMZ編程求法：(依據(jù)上面的思路，寫遞歸程序)1 #in elude <ios

4、tream>2 #in elude <fstream>3 #in elude <stri ng>44 struct TreeNode5 6 struct TreeNode* left;7 struct TreeNode* right;8 char elem;9 ；1112 void Bi naryTreeFromOrderi ngs(char* ino rder, char* preorder, i nt len gth)13 14 if(le ngth = 0)15 16 cout«"i nvalid len gth"17 retu

5、rn;18 19 TreeNode* node = new TreeNode;/Noice that new should be writte n out.20 no de->elem = *preorder;21 in t rootI ndex = 0;22 for(;rootl ndex < len gth; rootI ndex+)23 24 if(i no rderrootI ndex = *preorder)25 break;26 27 /Left28 BinaryTreeFromOrderings(inorder, preorder +1, rootIndex);29

6、/Right30 Bin aryTreeFromOrderi ngs(i no rder + rootI ndex + 1, preorder +rootIndex + 1, length - (rootIndex + 1);31 cout< <no de->elem<<e ndl;32 return;33 343534 int main (i nt argc, char* argv)35 36 prin tf("Hello World!n");37 char* pr="GDAFEMHZ"38 char* in="

7、ADEFGHMZ"4139 Bi naryTreeFromOrderi ngs(i n, pr, 8);4340 prin tf("n");41 return 0;42 輸出的結(jié)果為： AEFDHZMG二、已知中序和后序遍歷，求前序遍歷依然是上面的題，這次我們只給出中序和后序遍歷：中序遍歷：ADEFGHMZ后序遍歷：AEFDHZMG畫樹(shù)求法：第一步，根據(jù)后序遍歷的特點(diǎn)， 我們知道后序遍歷最后一個(gè)結(jié)點(diǎn)即為根結(jié)點(diǎn)，即根結(jié)點(diǎn)為 G第二步，觀察中序遍歷 ADEFGHMZ其中 root節(jié)點(diǎn)G左側(cè)的ADEF必然是root的左子樹(shù)，G 右側(cè)的HMZ必然是root的右子樹(shù)。第三步

8、，觀察左子樹(shù) ADEF左子樹(shù)的中的根節(jié)點(diǎn)必然是大樹(shù)的root的leftchild。在前序遍歷中，大樹(shù)的root的leftchild 位于root之后，所以左子樹(shù)的根節(jié)點(diǎn)為D。第四步，同樣的道理，root的右子樹(shù)節(jié)點(diǎn)HMZ中的根節(jié)點(diǎn)也可以通過(guò)前序遍歷求得。在前 后序遍歷中，一定是先把root和root的所有左子樹(shù)節(jié)點(diǎn)遍歷完之后才會(huì)遍歷右子樹(shù)，并且遍歷的左子樹(shù)的第一個(gè)節(jié)點(diǎn)就是左子樹(shù)的根節(jié)點(diǎn)。同理，遍歷的右子樹(shù)的第一個(gè)節(jié)點(diǎn)就是右子樹(shù)的根節(jié)點(diǎn)。第五步，觀察發(fā)現(xiàn)，上面的過(guò)程是遞歸的。先找到當(dāng)前樹(shù)的根節(jié)點(diǎn)，然后劃分為左子樹(shù)，右子樹(shù)，然后進(jìn)入左子樹(shù)重復(fù)上面的過(guò)程，然后進(jìn)入右子樹(shù)重復(fù)上面的過(guò)程。最后就可以還原

9、一棵樹(shù)了。該步遞歸的過(guò)程可以簡(jiǎn)潔表達(dá)如下：1確定根，確定左子樹(shù)，確定右子樹(shù)。2在左子樹(shù)中遞歸。3在右子樹(shù)中遞歸。4打印當(dāng)前根。這樣，我們就可以畫出二叉樹(shù)的形狀，如上圖所示，這里就不再贅述。那么，前序遍歷：GDAFEMHZ編程求法：（并且驗(yàn)證我們的結(jié)果是否正確）#i nclude <iostream>#in clude <fstream>#in clude <stri ng>struct TreeNodestruct TreeNode* left;struct TreeNode* right;char elem;TreeNode* Bi naryTreeFro

10、mOrderi ngs(char* ino rder, char* aftorder, i nt len gth)if(le ngth = 0)return NULL;TreeNode* node = new TreeNode;/Noice that new should be writte n out.no de->elem = *(aftorder+le ngth-1);std:cout< <no de->elem<<std:e ndl;int rootI ndex = 0;for(;rootI ndex < len gth; root In dex+)/a variati on of the loopif(i no rderroot In dex = *(aftorder+le ngth-1)break;no de->left = Bin aryTreeFromOrderi ngs(i no rder, aftorder ,root In dex);no de->right = Bi naryTreeFromOrderi ngs(i no rder + rootI ndex + 1,aftorder + root In dex , le ngth - (root In dex + 1);retur n no de;