二叉樹前序、中序、后序遍歷相互求法

1、二叉樹前序、中序、后序遍歷相互求法 今天來總結(jié)下二叉樹前序、中序、后序遍歷相互求法，即如果知道兩個的遍歷，如何 求第三種遍歷方法， 比較笨的方法是畫出來二叉樹， 然后根據(jù)各種遍歷不同的特性來求， 也 可以編程求出，下面我們分別說明。首先，我們看看前序、中序、后序遍歷的特性： 前序遍歷：1. 訪問根節(jié)點2. 前序遍歷左子樹3. 前序遍歷右子樹 中序遍歷：1. 中序遍歷左子樹2. 訪問根節(jié)點3. 中序遍歷右子樹 后序遍歷：1. 后序遍歷左子樹2. 后序遍歷右子樹3. 訪問根節(jié)點一、已知前序、中序遍歷，求后序遍歷例：前序遍歷 :GDAFEMHZ中序遍歷 :ADEFGHMZ畫樹求法：第一步，根據(jù)前序遍

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

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

4、 elude <fstream>3 #in elude <stri ng>44 struct TreeNode5 6 struct TreeNode* left;7 struct TreeNode* right;8 char elem;9 ；1112 void Bin aryTreeFromOrderi ngs(char* ino rder, char* preorder, i nt len gth)13 14 if(le ngth = 0)15 16 cout<v"invalid length"17 return;18 19 TreeNode

5、* node = new TreeNode;/Noice that new should be writte n out.20 no de->elem = *preorder;21 int rootIndex = 0;22 for(;rootIndex < length; rootIndex+)23 24 if(inorderrootIndex = *preorder)25 break;26 27 /Left28 BinaryTreeFromOrderings(inorder, preorder +1, rootIndex);29 /Right30 BinaryTreeFromOr

6、derings(inorder + rootIndex + 1, preorder + rootIndex + 1, length - (rootIndex + 1);31 cout<<node->elem<<endl;32 return;33 343536 int main(int argc, char* argv)37 38 printf("Hello World!n");39 char* pr="GDAFEMHZ"40 char* in="ADEFGHMZ"4142 BinaryTreeFromOr

7、derings(in, pr, 8);4344 printf("n");45 return 0;46 輸出的結(jié)果為： AEFDHZMG 二、已知中序和后序遍歷，求前序遍歷 依然是上面的題，這次我們只給出中序和后序遍歷： 中序遍歷 : ADEFGHMZ 后序遍歷 : AEFDHZMG畫樹求法：第一步，根據(jù)后序遍歷的特點， 我們知道后序遍歷最后一個結(jié)點即為根結(jié)點， 即根結(jié)點為 G。第二步，觀察中序遍歷 ADEFGHMZ 。其中 root 節(jié)點 G 左側(cè)的 ADEF 必然是 root 的左子樹， G 右側(cè)的 HMZ 必然是 root 的右子樹。第三步，觀察左子樹 ADEF ，左子

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

9、上面的過程。 最后就可以還原 一棵樹了。該步遞歸的過程可以簡潔表達如下：1 確定根 ,確定左子樹，確定右子樹。2 在左子樹中遞歸。3 在右子樹中遞歸。4 打印當前根。 這樣，我們就可以畫出二叉樹的形狀，如上圖所示，這里就不再贅述。那么，前序遍歷 : GDAFEMHZ 編程求法：( 并且驗證我們的結(jié)果是否正確)#include <iostream>#include <fstream>#include <string>struct TreeNodestruct TreeNode* left;struct TreeNode* right;char elem;Tre

10、eNode* BinaryTreeFromOrderings(char* inorder, char* aftorder, intlength)if(length = 0)return NULL;TreeNode* node = new TreeNode;/Noice that new should be written out.node->elem = *(aftorder+length-1); std:cout<<node->elem<<std:endl;int rootIndex = 0;for(;rootIndex < length; rootIndex+)/a variation of the loop if(inorderrootIndex = *(aftorder+length-1) break;node->left = BinaryTreeFromOrderings(inorder, aftorder , rootIndex);node->right = BinaryTreeFromOrderings(inorder + rootIndex + 1, aftorder + rootIndex , length - (rootIndex + 1);return no