中根與后根構(gòu)造二叉樹與二叉樹的匹配替換-數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

1、.成績南京工程學(xué)院課程設(shè)計(jì)說明書(論文)題 目中根與后根構(gòu)造二叉樹與二叉樹的匹配替換課 程 名 稱 數(shù)據(jù)結(jié)構(gòu) 院（系、部、中心） 計(jì)算機(jī)工程學(xué)院 專 業(yè) 計(jì)算機(jī)科學(xué)與技術(shù) 班 級 計(jì)算機(jī)卓越131 學(xué) 生 姓 名 羌秀君 學(xué) 號 202130404 設(shè) 計(jì) 地 點(diǎn) 信息樓 指 導(dǎo) 教 師 葉核亞 設(shè)計(jì)起止時(shí)間：2016年5月10日至2016年5月20日 一、課程設(shè)計(jì)目的和要求目的：深入理解數(shù)據(jù)結(jié)構(gòu)的基本理論，掌握數(shù)據(jù)存儲結(jié)構(gòu)的設(shè)計(jì)方法，掌握基于數(shù)據(jù)結(jié)構(gòu)的各種操作的實(shí)現(xiàn)方法，訓(xùn)練對基礎(chǔ)知識和基本方法的綜合運(yùn)用能力，增強(qiáng)對算法的理解能力，提高軟件設(shè)計(jì)能力。在實(shí)踐中培養(yǎng)獨(dú)立分析問題和解決問題的作風(fēng)和

2、能力。要求：熟練運(yùn)用C+語言、基本數(shù)據(jù)結(jié)構(gòu)和算法的基礎(chǔ)知識，獨(dú)立編制一個(gè)具有中等難度的、解決實(shí)際應(yīng)用問題的應(yīng)用程序。通過題意分析、選擇數(shù)據(jù)結(jié)構(gòu)、算法設(shè)計(jì)、編制程序、調(diào)試程序、軟件測試、結(jié)果分析、撰寫課程設(shè)計(jì)報(bào)告等環(huán)節(jié)完成軟件設(shè)計(jì)的全過程，不斷地完善程序以提高程序的性能。二、題意說明及分析題目要求采用中根和后根序列構(gòu)造一顆二叉樹，并匹配替換二叉樹的子樹。中根和后根構(gòu)造：由于后根可以確定一顆樹的根，而中根在知道根的情況下可以確定左右子樹的序列，因此這樣遞歸，中根和后根可以確定一顆唯一的二叉樹。匹配替換二叉樹：1. 通過遍歷二叉樹找到關(guān)鍵樹根值在待匹配樹中首次出現(xiàn)的位置，返回節(jié)點(diǎn)地址。2. 判斷以找

3、到的節(jié)點(diǎn)為根的子樹和帶匹配的樹是否相同，采用遞歸算法。3. 確定以找到根節(jié)點(diǎn)的子樹與帶匹配的樹相同，然后刪除以此為根節(jié)點(diǎn)的子樹，然后再將帶替換的樹復(fù)制到刪除的節(jié)點(diǎn)。三、算法設(shè)計(jì)與分析算法設(shè)計(jì)思路、數(shù)據(jù)結(jié)構(gòu)描述、流程圖等中根和后根構(gòu)造算法：設(shè)數(shù)組inlist和lalist分別表示一顆二叉樹的中根和后根序列，兩序列長度均為n。1.由后根遍歷的次序可知，該二叉樹的根是lalistn-1；改節(jié)點(diǎn)必定在中根次序中，設(shè)根節(jié)點(diǎn)在中根次序的第i個(gè)位置即inlisti=lalistn-1。2.由中根遍歷次序知，inlisti節(jié)點(diǎn)前的節(jié)點(diǎn)在根的左子樹上，inlisti后的所有節(jié)點(diǎn)在根節(jié)點(diǎn)的右子樹上。因此，根的左子

4、樹由i個(gè)節(jié)點(diǎn)組成，子序列為：左子樹的后根次序 lalist0.lalisti-1左子樹的中根次序inlist0.inlisti-1根的右子樹由n-j-1個(gè)節(jié)點(diǎn)，子序列為：右子樹的后根次序 lalisti.lalistn-2右子樹的中根次序 inlisti+1.inlistn-13. 以此遞歸，可唯一確定一顆二叉樹。算法實(shí)現(xiàn)：template<class T>BinaryTree<T>:BinaryTree(T lalist,T inlist,int n)this->root=create(lalist,inlist,n-1,n-1,n,root);template

5、<class T>BinaryNode<T>* BinaryTree<T>:create(T lalist,T inlist,int end,int inend,int n,BinaryNode<T>*parent)BinaryNode<T>*p=NULL;if (n>0)p=new BinaryNode<T>(lalistend);int i=0;while(i<n&&lalistend!=inlistinend-i)i+;p->parent=parent;p->right=cre

6、ate(lalist,inlist,end-1,inend,i,p);p->left=create(lalist,inlist,end-i-1,inend-i-1,n-i-1,p);return p;匹配替換二叉樹算法：通過遍歷二叉樹找到關(guān)鍵樹根值在待匹配樹中首次出現(xiàn)的位置，返回節(jié)點(diǎn)地址。判斷以找到的節(jié)點(diǎn)為根的子樹和帶匹配的樹是否相同，采用遞歸算法。確定以找到根節(jié)點(diǎn)的子樹與帶匹配的樹相同，然后刪除以此為根節(jié)點(diǎn)的子樹，然后再將帶替換的樹復(fù)制到刪除的節(jié)點(diǎn)。算法實(shí)現(xiàn)：/查找根節(jié)點(diǎn)template<class T>BinaryNode<T>* BinaryTree<

7、T>:searchhead(BinaryNode<T>*q,BinaryNode<T>*p)BinaryNode<T>*m=NULL;if(q!=NULL&&p!=NULL)if(q->data=p->data) return p;if(m=searchhead(q->left,p)=NULL)m=searchhead(q->right,p);returnm;/查找子樹template<class T>BinaryNode<T>* BinaryTree<T>:searchone

8、(BinaryTree<T>&bintree)BinaryNode<T>*p=searchhead(root,bintree.root);if(p!=NULL)if (matchtree(p,bintree.root)return p;elsereturn NULL;elsereturn p;/匹配子樹template<class T>bool BinaryTree<T>:matchtree(BinaryNode<T>*p,BinaryNode<T>*q)return (p = NULL && q

9、= NULL)|(q != NULL && p != NULL)&&(p->data = q->data)&&(matchtree(p->left,q->left)&&matchtree(p->right,q->right);四、源程序1.二叉樹節(jié)點(diǎn)類template<class T>class BinaryNodepublic:T data;/數(shù)據(jù)域BinaryNode<T>*left,*right,*parent;/指針域，分別指向左右孩子節(jié)點(diǎn)/構(gòu)造函數(shù)BinaryN

10、ode(T data,BinaryNode<T>*left=NULL,BinaryNode<T>*right=NULL,BinaryNode<T>*parent=NULL)this->data=data;this->left=left;this->right=right;this->parent =parent;二叉樹類#include <iostream>using namespace std;#include "BinaryTreeNode.h"template<class T>clas

11、s BinaryTreepublic:BinaryNode<T>* root;BinaryTree();/構(gòu)造空二叉樹BinaryTree(T lalist, T inlist, int n);/以中根和后根序列構(gòu)造二叉樹BinaryTree();/析構(gòu)bool empty();/判斷是否為空二叉樹friend ostream & operator<<<>(ostream& out, BinaryTree<T>&);/輸出void preOrder();/輸出先根次序遍歷序列string getinOrder(Binary

12、Node<T>*);/獲得中根次序遍歷的字符串string getpostOrder(BinaryNode<T>*);/獲得后根次序遍歷的字符串void remove(BinaryNode<T>*parent, bool leftchild);/刪除parent節(jié)點(diǎn)的左或右子樹BinaryNode<T>* searchone(BinaryTree<T>&);/查找子樹BinaryNode<T>* searchhead(BinaryNode<T>*q,T key);/查找頭結(jié)點(diǎn)bool matchtree

13、(BinaryNode<T>*p, BinaryNode<T>*q);void destroy(BinaryNode<T>*p);bool replace(BinaryTree<T>&key, BinaryTree<T>&re);private:void preOrder(BinaryNode<T>*p);/先根次序遍歷以p節(jié)點(diǎn)為根的子樹void postOrder(BinaryNode<T>*p, string &str);/后根void inOrder(BinaryNode<T

14、>*p, string &str);/中根次序遍歷以p節(jié)點(diǎn)為根的子樹BinaryNode<T>* create(T lalist, T inlist, int end, int inend, int n, BinaryNode<T>*);BinaryNode<T>* copy(BinaryNode<T>*);/析構(gòu)template<class T>BinaryTree<T>:BinaryTree()destroy(root);/判斷樹是否為空template<class T>bool Binary

15、Tree<T>:empty()return this->root = NULL;/構(gòu)造空二叉樹template<class T>BinaryTree<T>:BinaryTree()this->root = NULL;/輸出先根次序遍歷的序列template<class T>ostream& operator<<<>(ostream & out, BinaryTree<T>& btree)out << "先根次序遍歷二叉樹"btree.preOr

16、der(btree.root);out << endl;return out;template<class T>void BinaryTree<T>:preOrder(BinaryNode<T>*p)if (p = NULL)cout << ""elsecout << p->data << " "preOrder(p->left);preOrder(p->right);/中根和后根構(gòu)造二叉樹template<class T>BinaryTre

17、e<T>:BinaryTree(T lalist, T inlist, int n)this->root = create(lalist, inlist, n - 1, n - 1, n, root);template<class T>BinaryNode<T>* BinaryTree<T>:create(T lalist, T inlist, int end, int inend, int n, BinaryNode<T>*parent)BinaryNode<T>*p = NULL;if (n>0)p = n

18、ew BinaryNode<T>(lalistend);int i = 0;while (i<n&&lalistend != inlistinend - i)i+;p->parent = parent;p->right = create(lalist, inlist, end - 1, inend, i, p);p->left = create(lalist, inlist, end - i - 1, inend - i - 1, n - i - 1, p);return p;/刪除子樹template<class T>void

19、BinaryTree<T>:destroy(BinaryNode<T>*p)if (p != NULL)destroy(p->left);destroy(p->right);delete p;/查找根節(jié)點(diǎn)template<class T>BinaryNode<T>* BinaryTree<T>:searchhead(BinaryNode<T>*q, T key)BinaryNode<T>*m = NULL;if (q != NULL)if (q->data = key)return q;if

20、(m = searchhead(q->left, key) = NULL)m = searchhead(q->right, key);returnm;/查找子樹template<class T>BinaryNode<T>* BinaryTree<T>:searchone(BinaryTree<T>&bintree)BinaryNode<T>*p = searchhead(root, bintree.root->data);if (p != NULL)if (matchtree(p, bintree.root)

21、return p;elsereturn NULL;elsereturn p;/匹配子樹template<class T>bool BinaryTree<T>:matchtree(BinaryNode<T>*p, BinaryNode<T>*q)if (q = NULL&&p = NULL)return true;if (p = NULL | q = NULL)return false;if (p->data != q->data)return false;return(matchtree(p->left, q-&

22、gt;left) && matchtree(p->right, q->right);/替換template<class T>bool BinaryTree<T>:replace(BinaryTree<T>&key, BinaryTree<T>&re)BinaryNode<T>*p = searchone(key);if (p != NULL)/替換(搜到的頭不銷毀)destroy(p->left);destroy(p->right);p->data = re.root-&g

23、t;data;p->left = copy(re.root->left);p->right = copy(re.root->right);return true;elsereturn NULL;/二叉樹復(fù)制template<class T>BinaryNode<T>* BinaryTree<T>:copy(BinaryNode<T>*p)BinaryNode<T>*q = NULL;if (p != NULL)q = new BinaryNode<T>(p->data);q->paren

24、t = p->parent;q->left = copy(p->left);q->right = copy(p->right);return q;/獲得中根遍歷下的字符串template<class T>string BinaryTree<T>:getinOrder(BinaryNode<T>*p)string str;inOrder(p, str);return str;template<class T>void BinaryTree<T>:inOrder(BinaryNode<T>*p,

25、string &str)if (p != NULL)inOrder(p->left, str);str += p->data;inOrder(p->right, str);/獲得后根遍歷下的字符串template<class T>string BinaryTree<T>:getpostOrder(BinaryNode<T>*p)string str;postOrder(p, str);return str;template<class T>void BinaryTree<T>:postOrder(Binary

26、Node<T>*p, string &str)if (p != NULL)postOrder(p->left, str);postOrder(p->right, str);str += p->data;主cpp文件#include "BinaryTree.h"#include <iostream>#include <Windows.h>#include <string>using namespace std;int main()char lalist="GDBEHFCA"char

27、inlist="DGBAECHF"char inkey="ECHF"char lakey="EHFC"char inrep="LJMIK"char larep="LMJKI"BinaryTree<char> tree(lalist,inlist,8);BinaryTree<char> keytree(lakey,inkey,4);BinaryTree<char> reptree(larep,inrep,5);cout<<tree;cout<<"二叉關(guān)鍵子樹"<<endl<<keytree;cout<<"待替換的子樹"<<endl<<reptree;cout&