江苏大学-数据结构实验报告-实验二-树操作

上机实验报告课程名称：数据结构A实验题目：二叉树操作专业班级：计算机科学与技术1601学号：3160409053姓名：蒋权完成日期：2017.10.26成绩：一.实验内容、目的和要求1.实验内容二叉树的建立和遍历。2.实验目的（1）进一步掌握指针变量的使用。（2）掌握二叉树的结构特征以及各种存储结构的特点及使用范围。（3）掌握用指针类型描述、访问和处理二叉树的运算。（4）掌握栈或队列的使用。实验要求:本实验要求实现以下功能：（1）按前序次序建立一棵二叉树，以‘＃’表示空。（2）中序、后序遍历该二叉树，输出遍历序列。（3）求出该二叉树的深度并输出，或求出该二叉树的叶子数目并输出。(4)试以栈为辅助存储结构实现二叉树的前序非递归算法或以队列为辅助存储结构实现二叉树的层次遍历算法。【测试数据】输入以下字符串，建立二叉树：ABC##DE#G##F###输出中序遍历序列应为：CBEGDFA输出后序遍历序列应为：CGEFDBA输出二叉树的深度应为：5输出二叉树的叶子数目应为：3二.程序中使用的数据结构及符号说明*leftChild——左孩子指针*rightChild——右孩子指针三.程序的主要流程图四.程序运行时的初值和运行结果【测试数据】输入以下字符串，建立二叉树：ABC##DE#G##F###输出中序遍历序列应为：CBEGDFA输出后序遍历序列应为：CGEFDBA输出二叉树的深度应为：5输出二叉树的叶子数目应为：3最后，经调试运行后最后输出结果如下图所示五.收获及体会纸上得来终觉浅，绝知此事要躬行。六.源程序【这部分要求所列出来的源程序的代码的字号大小为“小五”，行距为“固定值”12磅，字体为TimesNewRoman】#includeiostreamusingnamespacestd;templateclassElemTypestructBinTreeNode{开始输入数据建立二叉树中序遍历输出后序遍历输出输出深度输出叶子数目结束ElemTypedata;BinTreeNodeElemType*leftChild;BinTreeNodeElemType*rightChild;BinTreeNode();BinTreeNode(constElemType&d,BinTreeNodeElemType*lChild=NULL,BinTreeNodeElemType*rChild=NULL);};templateclassElemTypeBinTreeNodeElemType::BinTreeNode(){leftChild=rightChild=NULL;}templateclassElemTypeBinTreeNodeElemType::BinTreeNode(constElemType&d,BinTreeNodeElemType*lChild=NULL,BinTreeNodeElemType*rChild=NULL){data=d;leftChild=lChild;rightChild=rChild;}templateclassElemTypeclassBinaryTree{public:BinTreeNodeElemType*root;BinaryTree();BinTreeNodeElemType*Architecture();voidInOrder(BinTreeNodeElemType*r,void(*Visit)(constElemType&))const;//二叉树的中序遍历voidPostOrder(BinTreeNodeElemType*r,void(*Visit)(constElemType&))const;//二叉树的后序遍历intHeight(BinTreeNodeElemType*r)const;intLeaf(BinTreeNodeElemType*r)const;voidLevelOrder(void(*Visit)(constElemType&))const;};templateclassElemTypeBinaryTreeElemType::BinaryTree(){root=newBinTreeNodeElemType;}templateclassElemTypeBinTreeNodeElemType*BinaryTreeElemType::Architecture(){BinTreeNodeElemType*p=NULL;charx;cinx;if(x=='#')p=NULL;else{p=newBinTreeNodeElemType;p-data=x;p-leftChild=Architecture();//递归构造左子树p-rightChild=Architecture();//递归构造右子树}returnp;}templateclassElemTypevoidBinaryTreeElemType::InOrder(BinTreeNodeElemType*r,void(*Visit)(constElemType&))const{if(r!=NULL){InOrder(r-leftChild,Visit);(*Visit)(r-data);InOrder(r-rightChild,Visit);}}templateclassElemTypevoidBinaryTreeElemType::PostOrder(BinTreeNodeElemType*r,void(*Visit)(constElemType&))const{if(r!=NULL){PostOrder(r-leftChild,Visit);PostOrder(r-rightChild,Visit);(*Visit)(r-data);}}templateclassElemTypeintBinaryTreeElemType::Height(BinTreeNodeElemType*r)const{intdeep=0;if(r){intleftdeep=Height(r-leftChild);//计算左子树的高度intrightdeep=Height(r-rightChild);//计算右子树高度deep=leftdeep=rightdeep?leftdeep+1:rightdeep+1;}returndeep;}templateclassElemTypeintBinaryTreeElemType::Leaf(BinTreeNodeElemType*r)const{if(r==NULL)return0;if(r-leftChild==NULL&&r-rightChild==NULL)return1;elsereturnLeaf(r-leftChild)+Leaf(r-rightChild);}templateclassElemTypevoidBinaryTreeElemType::LevelOrder(void(*Visit)(constElemType&))const{LinkQueueBinTreeNodeElemType*q;BinTreeNodeElemType*p;if(root!=NULL)q.EnQueue(root);while(!q.IsEmpty()){q.DelQueue(p);(*Visit)(p-data);if(p-leftChild!=NULL)q.EnQueue(p-leftChild);if(p-rightChild!=NULL)q.EnQueue(p-rightChild);}}templateclassElemTypestructNode{ElemTypedata;NodeElemType*next;Node(){next=NULL;}Node(ElemTypee,NodeElemType*link=NULL){data=e;next=link;}};templateclassElemTypeclassLinkQueue{protected:NodeElemType*front,*rear;public:LinkQueue(){front=rear=newNodeElemType;}boolIsEmpty()const;intDelQueue(ElemType&e);intEnQueue(constElemType&e);};templateclassElemTypeintLinkQueueElemType::EnQueue(constElemType&e){NodeElemType*p;p=newNodeElemType;if(p){rear-data=e;rear-next=p;rear=rear-next;return1;}elsereturn0;}templateclassElemTypeintLinkQueueElemType::DelQueue(ElemType&e){NodeElemType*p=front;if(p-next!=NULL){e=front-data;front=front-next;deletep;}return0;}templateclassElemTypeboolLinkQueueElemType::IsEmpty()const{if(front==rear)return1;elsereturn0;}templateclassElemTypevoidVisit(constElemType&e){coute;}voidmain(){BinaryTreecharpeng;cout请输入以下字符串，建立二叉树：endl;peng.root=peng.Architecture();cout中序遍历序列为：;peng.InOrder(peng.root,Visit);coutendl;cout后序遍历序列为：;peng.PostOrder(peng.root,Visit);coutendl;cout层序遍历序列为：;peng.LevelOrder(Visit);coutendl;cout二叉树的深度为:peng.Height(peng.root)endl;cout二叉树的叶子数目为：peng.Leaf(peng.root)endl;system(pause);}