二叉树

重庆交通大学综合性设计性实验报告班级：计算机科学与技术专业2010级4班实验项目名称：二叉树实验项目性质：树的实例应用实验所属课程：数据结构实验室(中心)：软件与通信实验中心指导教师：鲁云平实验完成时间：2012年5月11日一、实验目的1.建立并熟悉广义表的内容并应用2.建立树并运用树的功能函数二、实验内容及要求实验内容：1.建立二叉树2.计算结点所在的层次3.统计结点数量和叶结点数量4.计算二叉树的高度5.计算结点的度6.找结点的双亲和子女7.二叉树的遍历8.二叉树的输出等等实验要求:1.二叉树的结点结构,二叉树的存储结构由学生自由选择和设定2.实验完成后上交打印的实验报告,报告内容与前面所给定的实验模板相同3.将实验报告电子版和源代码在网络教学平台提交三、实验设备及软件四、设计方案㈠题目（老师给定或学生自定）二叉树㈡设计的主要思路教师评阅意见：签名：年月日实验成绩：通过对二叉树的理解，运用面向对象的方法，结合链表这一存储方式，实现二叉树的各种基本操作。㈢主要功能返回点的度数，总结点数，树的高度，层次，返回父母，返回子女，输入输出等功能函数五、主要代码#includeiostream.h#includestdlib.htemplateclassTstructBinTreeNode//二叉树结点类定义{Tdata;//数据域BinTreeNodeT*leftChild,*rightChild;//左子女、右子女链域BinTreeNodeT()//构造函数{leftChild=NULL;rightChild=NULL;}BinTreeNode(Tx,BinTreeNodeT*l=NULL,BinTreeNodeT*r=NULL){data=x;leftChild=l;rightChild=r;}};templateclassTclassBinaryTree//二叉树类定义{public:BinaryTree():root(NULL){}//构造函数BinaryTree(Tvalue):root(NULL)//构造函数{RefValue=value;}~BinaryTree(){destroy(root);}//析构函数boolIsEmpty(){returnroot==NULL;}//判二叉树空否intHeight(){returnHeight(root);}//求树高度intSize(){returnSize(root);}//求结点数intdegree(Tx){returndegree(root,x);}//求结点的度intlevel(Tx){returnlevel(root,x);}//求结点的层次BinTreeNodeT*Parent(Tx)//返回双亲结点{return(root==NULL||root-data==x)?NULL:Parent(root,x);}BinTreeNodeT*LeftChild(Tx)//返回左子女{returnLeftChild(root,x);}voidTraverse(ostream&out){Traverse(root,out);}//前序遍历输出voidPrintBTree(){PrintBTree(root);}//以广义表行式输出二叉树BinTreeNodeT*getRoot(){returnroot;}//取根protected:BinTreeNodeT*root;//二叉树的根指针TRefValue;//数据输入停止标志voidCreateBinTree(istream&in,BinTreeNodeT*&subTree);//以前序方式建立二叉树voiddestroy(BinTreeNodeT*&subTree);//删除intHeight(BinTreeNodeT*subTree);//返回树高度intSize(BinTreeNodeT*subTree);//返回结点数intlevel(BinTreeNodeT*subTree,Tx);//求结点的层次intdegree(BinTreeNodeT*subTree,Tx);//求结点的度BinTreeNodeT*Parent(BinTreeNodeT*subTree,Tx);//返回父结点BinTreeNodeT*LeftChild(BinTreeNodeT*subTree,Tx);//返回左子女voidPrintBTree(BinTreeNodeT*subTree);//以广义表行式输出二叉树voidTraverse(BinTreeNodeT*subTree,ostream&out);//前序遍历输出friendistream&operator(istream&in,BinaryTreeT&Tree);//重载操作：输入friendostream&operator(ostream&out,BinaryTreeT&Tree);//重载操作：输出};//私有函数:以递归方式建立二叉树templateclassTvoidBinaryTreeT::CreateBinTree(istream&in,BinTreeNodeT*&subTree){Titem;if(!in.eof())//未读完,读入并建树{cout输入结点值：endl;initem;//读入根结点的值if(item!=RefValue){subTree=newBinTreeNodeT;//建立根结点subTree-data=item;if(subTree==NULL){cerr存储分配错!endl;exit(1);}CreateBinTree(in,subTree-leftChild);//递归建立左子树CreateBinTree(in,subTree-rightChild);//递归建立右子树}elsesubTree=NULL;//封闭指向空子树的指针}}//私有函数:从结点subTree开始,搜索结点t的双//亲,若找到则返回双亲结点地址,否则返回NULLtemplateclassTBinTreeNodeT*BinaryTreeT::Parent(BinTreeNodeT*subTree,Tx){if(subTree==NULL)returnNULL;if((subTree-leftChild!=NULL&&subTree-leftChild-data==x)||(subTree-rightChild!=NULL&&subTree-rightChild-data==x))returnsubTree;//找到,返回父结点地址BinTreeNodeT*p;if((p=Parent(subTree-leftChild,x))!=NULL)returnp;//递归在左子树中搜索elsereturnParent(subTree-rightChild,x);//递归在右子树中搜索delete[]p;}//返回左子女templateclassTBinTreeNodeT*BinaryTreeT::LeftChild(BinTreeNodeT*subTree,Tx){if(subTree==NULL)returnNULL;if(subTree-data==x)return(subTree!=NULL)?(subTree-leftChild):NULL;BinTreeNodeT*p;if((p=LeftChild(subTree-leftChild,x))!=NULL)returnp;elsereturnLeftChild(subTree-rightChild,x);delete[]p;}//前序遍历输出templateclassTvoidBinaryTreeT::Traverse(BinTreeNodeT*subTree,ostream&out){if(subTree!=NULL){coutsubTree-data'';Traverse(subTree-leftChild,out);Traverse(subTree-rightChild,out);}}//私有函数:删除根为subTree的子树templateclassTvoidBinaryTreeT::destroy(BinTreeNodeT*&subTree){if(subTree!=NULL){destroy(subTree-leftChild);//删除左子树destroy(subTree-rightChild);//删除右子树delete[]subTree;//删除根结点}}//私有函数：利用二叉树后序遍历算法计算二叉//树的结点个数templateclassTintBinaryTreeT::Size(BinTreeNodeT*subTree){if(subTree==NULL)return0;//空树elsereturn1+Size(subTree-leftChild)+Size(subTree-rightChild);}//私有函数：利用二叉树后序遍历算法计算二叉//树的高度或深度templateclassTintBinaryTreeT::Height(BinTreeNodeT*subTree){if(subTree==NULL)return0;//空树高度为0else{inti=Height(subTree-leftChild);intj=Height(subTree-rightChild);return(ij)?j+1:i+1;}}templateclassTistream&operator(istream&in,BinaryTreeT&Tree){Tree.CreateBinTree(in,Tree.root);returnin;}templateclassTostream&operator(ostream&out,BinaryTreeT&Tree){out二叉树的前序遍历\n;Tree.Traverse(Tree.root,out);outendl;returnout;}//求结点的度templateclassTintBinaryTreeT::degree(BinTreeNodeT*subTree,Tx){if(subTree==NULL)returnNULL;if(subTree!=NULL&&subTree-data==x){inti=-1;if(subTree-leftChild!=NULL&&subTree-rightChild!=NULL){i=i+3;returni;}if(subTree-leftChild!=NULL||subTree-rightChild!=NULL){i=i+2;returni;}else{i=i+1;returni;}}if(degree(subTree-leftChild,x)!=-1)returndegree(subTree-leftChild,x);elsereturndegree(subTree-rightChild,x);}//求结点的层次templateclassTintBinaryTreeT::level(BinTreeNodeT*subTree,Tx){if(subTree==NULL)returnNULL;if(subTree-data==x)return1;if(level(subTree-leftChild,x))return1+level(subTree-leftChild,x);elsereturn1+level(subTree-rightChild,x);/