您好,登錄后才能下訂單哦!
輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果,重建出這棵二叉樹,假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字。例如,輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6},則重建出這棵滿足前序遍歷和中序遍歷的二叉樹并輸出它的頭結(jié)點(diǎn)。
對一棵二叉樹前序遍歷的順序是“根結(jié)點(diǎn)->左結(jié)點(diǎn)->右結(jié)點(diǎn)”,而中序遍歷的順序是“左結(jié)點(diǎn)->根節(jié)點(diǎn)->右結(jié)點(diǎn)”,因此,一般的思路都是醬紫的:
前序遍歷列表中,第一個數(shù)據(jù)肯定是根節(jié)點(diǎn),而中序遍歷列表中,第一個數(shù)據(jù)肯定是樹的最左結(jié)點(diǎn),這樣就可以得知,在前序遍歷中,從根結(jié)點(diǎn)到最左結(jié)點(diǎn)一定是樹的最左分支,也就是“1->2->4”;
接下來,在中序遍歷中,訪問完最左結(jié)點(diǎn)4之后因?yàn)槠渥蠼Y(jié)點(diǎn)為NULL要訪問的就是4的右分支的最左結(jié)點(diǎn)了,為7,而在前序遍歷中訪問到最左結(jié)點(diǎn)之后就要訪問右結(jié)點(diǎn),發(fā)現(xiàn)也為7,說明7就是最左結(jié)點(diǎn)4的右分支上的最左結(jié)點(diǎn),也就是只有7一個右結(jié)點(diǎn);
然后,在中序遍歷中訪問完最左結(jié)點(diǎn)也就是以4為根節(jié)點(diǎn)子樹之后,就要回到4結(jié)點(diǎn)的父節(jié)點(diǎn)了,也就是2,再往下訪問是根節(jié)點(diǎn)1,也就是2并沒有右結(jié)點(diǎn);
至此會發(fā)現(xiàn)1為根節(jié)點(diǎn)的左子樹已經(jīng)全部訪問完了;
上面沒有再繼續(xù)往下分析,是因?yàn)闀l(fā)現(xiàn),上面說的一堆雖然能把樹給重建出來,但是很繁瑣,邏輯上有關(guān)聯(lián)卻難以疏通個條理出來,因此要想轉(zhuǎn)換為代碼來實(shí)現(xiàn)想必又是要大費(fèi)周折;
為什么分析到第四點(diǎn)就停下了,是因?yàn)榈谒狞c(diǎn)的式轉(zhuǎn)換新思路的一個起點(diǎn):
首先前面第一點(diǎn)中加粗的字體肯定是沒有問題的,前序遍歷中第一個數(shù)據(jù)一定是樹的根結(jié)點(diǎn);
再結(jié)合第四點(diǎn),在中序遍歷中找到這個根結(jié)點(diǎn),會發(fā)現(xiàn)以1為根結(jié)點(diǎn)前面的數(shù)據(jù)都是1的左子樹,有三個結(jié)點(diǎn),那么在前序遍歷中1后面的三個結(jié)點(diǎn)都是屬于左子樹的;因此,在1后面的數(shù)據(jù)肯定也都是在1的右子樹上,有四個結(jié)點(diǎn);
接下來看在前序遍歷中跟在1后面的數(shù)據(jù)2是在1的左邊還是右邊,在左邊就是1的左結(jié)點(diǎn),在右邊就是1的右結(jié)點(diǎn);
然后按照前序遍歷列表中的順序?qū)?看為新的根結(jié)點(diǎn),那么在它左邊的數(shù)據(jù)就是它左子樹上的,右邊的數(shù)據(jù)就是右子樹上的,當(dāng)然是截止到前一個根結(jié)點(diǎn)1為止;然后就再次循環(huán)從上一步開始;
可畫圖如下:
是不是會發(fā)現(xiàn)第二次的分析比第一次要簡單明了多了?而且邏輯上有重復(fù)性,這樣的分析用代碼實(shí)現(xiàn)起來會比較容易,可以用遞歸來實(shí)現(xiàn):
#include <iostream> #include <assert.h> using namespace std; typedef int data_type; //首先定義一個樹結(jié)點(diǎn)的結(jié)構(gòu)體并實(shí)現(xiàn)構(gòu)造函數(shù) struct BinaryTreeNode { data_type _data; BinaryTreeNode* _Lnode; BinaryTreeNode* _Rnode; BinaryTreeNode(data_type data) :_data(data) ,_Lnode(NULL) ,_Rnode(NULL) {} }; //重建二叉樹,參數(shù)為兩個遍歷列表,樹結(jié)點(diǎn)的個數(shù),還有遞歸所需要知道子樹的范圍 BinaryTreeNode* RebuildBinaryTree(const data_type* prevlist, const data_type *inlist, const size_t num, size_t head, size_t tail) { assert(prevlist && inlist && num); //判斷參數(shù)有效性 //前序遍歷列表中第一個結(jié)點(diǎn)一定是樹的根結(jié)點(diǎn) BinaryTreeNode *root = new BinaryTreeNode(*prevlist); size_t root_index; //在中序遍歷列表中找出根結(jié)點(diǎn) for(root_index = 0; root_index < num; ++root_index) { if(inlist[root_index] == *prevlist) break; } if(inlist[root_index] != *prevlist) //檢查給出的序列是否為有效的遍歷序列 { cout<<"Invalid parameter..."<<endl; exit(0); } //當(dāng)結(jié)點(diǎn)個數(shù)大于0的時候才表示會有子結(jié)點(diǎn),否則為已經(jīng)初始化過的NULL //傳遞首尾范圍的時候,是不包括根結(jié)點(diǎn)的,因此要注意 size_t left_node_num = root_index - head;//根結(jié)點(diǎn)左邊的結(jié)點(diǎn)個數(shù) if(left_node_num > 0) root->_Lnode = RebuildBinaryTree(prevlist+1, inlist, num, head, root_index-1); size_t right_node_num = tail - root_index;//根結(jié)點(diǎn)右邊的結(jié)點(diǎn)個數(shù) if(right_node_num > 0) root->_Rnode = RebuildBinaryTree(prevlist+left_node_num+1, inlist, num, root_index+1, tail); return root; } //前序遍歷檢查二叉樹是否正確重建 void PreOrder(BinaryTreeNode *root) { if(root != NULL) { cout<<root->_data<<"->"; PreOrder(root->_Lnode); PreOrder(root->_Rnode); } } int main() { data_type PrevOrderList[] = {1, 2, 4, 7, 3, 5, 6, 8}; data_type InOrderList[] = {4, 7, 2, 1, 5, 3, 8, 6}; size_t node_num = sizeof(PrevOrderList)/sizeof(PrevOrderList[0]); //這里的首部和尾部的表示范圍都是在中序遍歷中 size_t head = 0; size_t tail = node_num-1; BinaryTreeNode* root = RebuildBinaryTree(PrevOrderList, InOrderList, node_num, head, tail); cout<<"the root data: "<<root->_data<<endl; PreOrder(root); cout<<"NULL"<<endl; return 0; }
運(yùn)行程序:
因?yàn)橹皇菣z查書是否重建好,用遞歸寫樹的先序遍歷,輸出發(fā)現(xiàn)和給定的先序遍歷序列一樣,則樹重建完成。
《完》
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。