二叉树的拷贝

1、实验七：二叉树的拷贝【实验题目】建立二叉树类，实现常用的操作，并且编写二叉树复制成员函数，并在主程序里实现这 个功能。【概要分析】二叉树是一种特殊的树，意思就是如呆一个结点有孩子，孩子最多只能有两个，这样的 树就是二叉树。二叉树是非常重要的树形数据结构。很多从实际问题中抽象出来的数据是二 叉树形的；以后我们将看到任意树或森林可方便地转换成二叉树，从而为一般树和森林的存 储和处理提供了有效方法。【详细设计】类图结构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核心代码在二叉树类里建立一个成员函数BTNode* Copy(BTNode* t);这个函数使用一个已经有的根结点，用递归的方法将这个根卞面的所有结点都拷贝出去，返 回一个新的根结点。但请

4、注意了，返回的不是二叉树。因此，要将一个二叉树拷贝成另一个 二叉树必要做到以下几点：第一点：要有一个已经存在的二叉树，比如说是z第二点：要有一个方法(成员函数，比如说定义GetRoot)能够取得这个已经存在的二叉树 的根。sourRoot=z.GetRoot();第三点：定义一个新的结点desRoot,用来准备保存拷贝函数(Copy)得到的新结点链表的 头。BTNode *desRoot;第四点：定义一个新的 一叉树 BinaryTree desBinaryTree;第五点：为二叉树类编写一个新的成员函数SetRoot,将得到的desRoot赋值给这个对彖的 根，这样的一根崭新的二叉树就形成了

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;请补充代码templatebool BinaryTree:Root(T& x)constif(root)x = root-element;return true;else return false;请完成制造树和分解树的代码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【实验预测结果】二叉树：经过先序遍历显示为：BDCEF故实验正确。【实验调试】 出错信息：error C2601: PushOperand: local function definitions are illegal解决方案：在return 0语句结束后加“”【实验总结】本次实验的核心就是二叉树的拼接与拆解还有拷贝，拼接时要注意的是确保本对彖是空的。 在遍历的过程中注意选择的遍历方式不同，结果会不同。由于在拼树时 z.MakeTree( C ,x,y)的顺序弄错了，导致实验结果与预测结果不同，还有Child的人小 写没注意都导致过错误的出现。【实验