二叉樹(shù)的遍歷題目及答案1.二叉樹(shù)的基本組成部分是：根（N）、左子樹(shù)（L）和右子樹(shù)（R）。因而二叉樹(shù)的遍歷次序有六種。最常用的是三種：前序法（即按NLR次序），后序法（即按LRN次序）和中序法（也稱對(duì)稱序法，即按LNR次序）。這三種方法相互之間有關(guān)聯(lián)。若已知一棵二叉樹(shù)的前序序列是BEFCGDH，中序序列是FEBGCHD，則它的后序序列必是FEGHDCB。解：法1：先由已知條件畫圖，再后序遍歷得到結(jié)果；法2：不畫圖也能快速得出后序序列，只要找到根的位置特征。由前序先確定root，由中序先確定左子樹(shù)。例如，前序遍歷BEFCGDH中，根結(jié)點(diǎn)在最前面，是B；則后序遍歷中B一定在最后面。法3：遞歸計(jì)算。如B在前序序列中第一，中序中在中間（可知左右子樹(shù)上有哪些元素），則在后序中必為最后。如法對(duì)B的左右子樹(shù)同樣處理，則問(wèn)題得解。2.給定二叉樹(shù)的兩種遍歷序列，分別是：前序遍歷序列：D，A，C，E，B，H，F(xiàn)，G，I；中序遍歷序列：D，C，B，E，H，A，G，I，F(xiàn)，試畫出二叉樹(shù)B，并簡(jiǎn)述由任意二叉樹(shù)B的前序遍歷序列和中序遍歷序列求二叉樹(shù)B的思想方法。解：方法是：由前序先確定root，由中序可確定root的左、右子樹(shù)。然后由其左子樹(shù)的元素集合和右子樹(shù)的集合對(duì)應(yīng)前序遍歷序列中的元素集合，可繼續(xù)確定root的左右孩子。將他們分別作為新的root，不斷遞歸，則所有元素都將被唯一確定，問(wèn)題得解。3、當(dāng)一棵二叉樹(shù)的前序序列和中序序列分別是HGEDBFCA和EGBDHFAC時(shí)，其后序序列必是A.BDEAGFHCB.EBDGACFHC.HGFEDCBAD.HFGDEABC答案：B4.已知一棵二叉樹(shù)的前序遍歷為ABDECF，中序遍歷為DBEAFC，則對(duì)該樹(shù)進(jìn)行后序遍歷得到的序列為_(kāi)_____。A．DEBAFCB．DEFBCAC．DEBCFAD．DEBFCA[解析]由二叉樹(shù)前序遍歷序列和中序遍歷序列可以唯一確定一棵二叉樹(shù)。由前序遍歷為ABDECF，可以確定二叉樹(shù)的根為A，這樣二叉樹(shù)的左子樹(shù)的前序遍歷為BDE、中序遍歷為DBE。在左子樹(shù)中，可以確定B為根，D為左子樹(shù)，E為右子樹(shù)。同樣的方法可以確定右子樹(shù)。答案：D5.已知一顆二叉樹(shù)的前序（后序）遍歷序列和中序遍歷序列，如何構(gòu)建這棵二叉樹(shù)？前序遍歷序列：ABCDEF中序遍歷序列：CBDAEF前序遍歷先訪問(wèn)根節(jié)點(diǎn)，因此前序遍歷序列的第一個(gè)字母肯定就是根節(jié)點(diǎn)，即A是根節(jié)點(diǎn)；然后，由于中序遍歷先訪問(wèn)左子樹(shù)，再訪問(wèn)根節(jié)點(diǎn)，最后訪問(wèn)右子樹(shù)，所以我們找到中序遍歷中A的位置，然后A左邊的字母就是左子樹(shù)了，也就是CBD是根節(jié)點(diǎn)的左子樹(shù)；同樣的，得到EF為根節(jié)點(diǎn)的右子樹(shù)。6.以下面的例題為例進(jìn)行講解：已知一棵二叉樹(shù)的先序遍歷序列和中序遍歷序列分別是ABDCEF、BDAECF，求二叉樹(shù)及后序遍歷序列。分析：先序遍歷序列的第一個(gè)字符為根結(jié)點(diǎn)。對(duì)于中序遍歷，根結(jié)點(diǎn)在中序遍歷序列的中間，左邊部分是根結(jié)點(diǎn)的左子樹(shù)的中序遍歷序列，右邊部分是根結(jié)點(diǎn)的右子樹(shù)的中序遍歷序列。先序：ABDCEF-->ABDCEF中序：BDAECF-->BDAECF得出結(jié)論：A是樹(shù)根，A有左子樹(shù)和右子樹(shù)，左子樹(shù)有BD結(jié)點(diǎn)，右子樹(shù)有CEF結(jié)點(diǎn)。先序：BD-->BD中序：BD-->BD得出結(jié)論：B是左子樹(shù)的根結(jié)點(diǎn)，B無(wú)左子樹(shù)，有右子樹(shù)(只有D結(jié)點(diǎn))。先序