二叉樹的拷貝

1、實(shí)驗(yàn)七：二叉樹的拷貝【實(shí)驗(yàn)題目】建立二叉樹類，實(shí)現(xiàn)常用的操作，并且編寫二叉樹復(fù)制成員函數(shù)，并在主程序里實(shí)現(xiàn)這 個(gè)功能。【概要分析】二叉樹是一種特殊的樹，意思就是如呆一個(gè)結(jié)點(diǎn)有孩子，孩子最多只能有兩個(gè)，這樣的 樹就是二叉樹。二叉樹是非常重要的樹形數(shù)據(jù)結(jié)構(gòu)。很多從實(shí)際問題中抽象出來的數(shù)據(jù)是二 叉樹形的；以后我們將看到任意樹或森林可方便地轉(zhuǎn)換成二叉樹，從而為一般樹和森林的存 儲(chǔ)和處理提供了有效方法?！驹敿?xì)設(shè)計(jì)】類圖結(jié)構(gòu)class Class Model /T:classT:classBlnaryTreeT:class# root: BTNode*structBTNode+ element: T+ I

2、Child: BTNodeTstructBTNode+ element: T+ IChild: BTNodeT+ rChild: BTNode*+ BTNodeO+ BTNodeCT&)+ BTNode(T& BTNode BTNode*)楊振飛BinaryTreef)-BinaryTreeO+ BreakTree仃& BinaryTree& BinaryTree&): void+ Clear(): voidClear(BTNode*): void+ Copy(BinaryTree&): voidCopy(BTNode*): BTNode*lnOrder(): voidlnOrder(BTNo

3、de*): void+ IsEmptyO : bool query+ MateTree仃& BinaryTree& BinaryTree&): voidPostOrderQ : voidPostOrder(BTNode): voidPreOrder(): void-PreOrder(BTNode*): void+ Root(T&): bool querySize(): intSize但TNode*): int核心代碼在二叉樹類里建立一個(gè)成員函數(shù)BTNode* Copy(BTNode* t);這個(gè)函數(shù)使用一個(gè)已經(jīng)有的根結(jié)點(diǎn)，用遞歸的方法將這個(gè)根卞面的所有結(jié)點(diǎn)都拷貝出去，返 回一個(gè)新的根結(jié)點(diǎn)。但請(qǐng)

4、注意了，返回的不是二叉樹。因此，要將一個(gè)二叉樹拷貝成另一個(gè) 二叉樹必要做到以下幾點(diǎn)：第一點(diǎn)：要有一個(gè)已經(jīng)存在的二叉樹，比如說是z第二點(diǎn)：要有一個(gè)方法(成員函數(shù)，比如說定義GetRoot)能夠取得這個(gè)已經(jīng)存在的二叉樹 的根。sourRoot=z.GetRoot();第三點(diǎn)：定義一個(gè)新的結(jié)點(diǎn)desRoot,用來準(zhǔn)備保存拷貝函數(shù)(Copy)得到的新結(jié)點(diǎn)鏈表的 頭。BTNode *desRoot;第四點(diǎn)：定義一個(gè)新的 一叉樹 BinaryTree desBinaryTree;第五點(diǎn)：為二叉樹類編寫一個(gè)新的成員函數(shù)SetRoot,將得到的desRoot賦值給這個(gè)對(duì)彖的 根，這樣的一根嶄新的二叉樹就形成了

5、。程序代碼BinaryTree.h#ifndef BinaryTree_h#define BinaryTree_h#include templatestruct BTNodeBTNode()IChild = rChild = NULL;BTNode(co nst T& x)eleme nt =x;IChild = rChild = NULL;BTNode(constT& x, BTNode* L BTNode* r)eleme nt = x;IChild = l;rChild = r;T element;BTNode* IChild, *rChild;templateclass BinaryT

6、reepublic:BinaryTree()root = NULL;BinaryTreeOfClearO；bool lsEmpty()const;bool Root仃& x)const;void MakeTree(const T& e, BinaryTree& left,BinaryTree& right);void BreakTree仃& e, BinaryTree& left, BinaryTree& right);void PreOrder();void lnOrder();void PostOrder();int Size();void Clear();void Copy(Binary

7、Tree &des);protected:BTNode* root;private:void PreOrder(BTNode* t);void lnOrder(BTNode* t);void PostOrder(BTNode* t);int Size(BTNode* t);void Clear(BTNode* t);BTNode* Copy(BTNode *t);templatevoid BinaryTree:Copy(BinaryTree &des) des.root=Copy(root);templateBTNode* BinaryTree:Copy(BTNode* t)if(It)ret

8、urn NULL;BTNode* q = new BTNode (t-element); q-IChild = Copy(t-IChild);q-rChild = Copy(t-rChild); return q;請(qǐng)補(bǔ)充代碼templatebool BinaryTree:Root(T& x)constif(root)x = root-element;return true;else return false;請(qǐng)完成制造樹和分解樹的代碼templatevoid BinaryTree:MakeTree(const T& e, BinaryTree& left,BinaryTree& right)

9、if(root 11 &left = &right)return;root = new BTNode (e, I eft. root, right.root);left.root = right, root = NULL;templatevoid BinaryTree:BreakTree(T& e, BinaryTree& left, BinaryTree& right)if(!root 11 &left = &right 11 left.root 11 right.root)return;x = root-eleme nt;left.root = root-IChild;right.root

10、 = root-rChild;delete root;root = NULL;templatevoid BinaryTree:PreOrder()PreOrder(root);templatevoid BinaryTree:PreOrder(BTNode* t)if(t)cout(t-eleme nt);PreOrder(t-IChild);PreOrder(t-rChild);templatevoid BinaryTree:lnOrder()InOrder(root); template void BinaryTree:lnOrder(BTNode* t)if(t)lnOrder(t-ICh

11、ild); cout(t-eleme nt);lnOrder(t-rChild);templatevoid BinaryTree:PostOrder()PostOrder(root);templatevoid BinaryTree:PostOrder(BTNode* t) if(t)PostOrder(t-IChild);PostOrder(t-rChild);cout(t-eleme nt);templateint BinaryTree:Size()return Size(root);templateint BinaryTree:Size(BTNode* t)if(!t) return 0;

12、return Size(t-IChild) + Size(t-rChild) + 1; template void BinaryTree:Clear()Clear(root);templatevoid BinaryTree:Clear(BTNode* t)if(t)Clear(t-IChild);Clear(t-rChild);cout delete 11 t-element endl;delete t;BinaryTreeMain.h#inelude BinaryTree.hHint main()BinaryTree abx“z;y.MakeTree(/E,a,b);z.MakeTree(F

13、ab);MakeTree(/C,/y,z);y.MakeTree(/D,a,b);z.MakeTree(B：%x);z.PreOrder();#endif【實(shí)驗(yàn)預(yù)測(cè)結(jié)果】二叉樹：經(jīng)過先序遍歷顯示為：BDCEF故實(shí)驗(yàn)正確?！緦?shí)驗(yàn)調(diào)試】 出錯(cuò)信息：error C2601: PushOperand: local function definitions are illegal解決方案：在return 0語(yǔ)句結(jié)束后加“”【實(shí)驗(yàn)總結(jié)】本次實(shí)驗(yàn)的核心就是二叉樹的拼接與拆解還有拷貝，拼接時(shí)要注意的是確保本對(duì)彖是空的。 在遍歷的過程中注意選擇的遍歷方式不同，結(jié)果會(huì)不同。由于在拼樹時(shí) z.MakeTree( C ,x,y)的順序弄錯(cuò)了，導(dǎo)致實(shí)驗(yàn)結(jié)果與預(yù)測(cè)結(jié)果不同，還有Child的人小 寫沒注意都導(dǎo)致過錯(cuò)誤的出現(xiàn)。【實(shí)驗(yàn)