二叉树实验报告

重庆交通大学 综合性性实验报告 班        级： 软件开发 专业 2010级一班 实验项目名称：    二叉树            实验项目性质：    设计性实验            实验所属课程：    数据结构            实验室(中心)：      6教                指 导 教 师 ：        鲁云平          实验完成时间：   2012    年 4 月 29 日 1、实验目的 主要完成以下功能: 1. 建立二叉树 2. 计算结点所在的层次 3 .统计结点数量和叶结点数量 4. 计算二叉树的高度 5. 计算结点的度 6. 找结点的双亲和子女 7. 二叉树的遍历 8. 二叉树的输出等等 2、实验内容及要求 1.二叉树的结点结构,二叉树的存储结构由学生自由选择和设定 2.实验完成后上交打印的实验报告,报告内容与前面所给定的实验相同 3.将实验报告电子版和源代码在网络教学平台提交 3、实验设备及软件 Visual studio 2010 四、设计 ㈠ 题目（老师给定或学生自定） 二叉树的简单应用 ㈡ 设计的主要思路 通过递归原理实现大部分遍历二叉树功能 ㈢ 主要功能 1. 建立二叉树 2. 计算结点所在的层次 3 .统计结点数量和叶结点数量 4. 计算二叉树的高度 5. 计算结点的度 6. 找结点的双亲和子女 7. 二叉树的遍历 8. 二叉树的输出 5、主要代码 栈头文件：stack.h class Stack { public: Stack(int sz=100); ~Stack(){delete[]elements;} void Push(const T &x); bool Pop(T &x); bool getTop(T &x); bool IsEmpty()const{return(top==-1)?true:false;} bool IsFull()const{return(top==maxSize-1)?true:false;} private: T *elements; int top; int maxSize; void overflowProcess(); }; template Stack::Stack(int sz):top(-1),maxSize(sz) { elements=new T[maxSize]; assert(elements!=NULL); }; template void Stack::overflowProcess() { T*newArray=new T[maxSize+stackIncreament]; if(newArray=NULL){cerr<<"存储分配失败！"< void Stack::Push(const T &x) { if(IsFull()==true)overflowProcess(); elements[++top]=x; }; template bool Stack::Pop(T &x) { if(IsEmpty()==true)return false; x=elements[top--]; return true; }; template bool Stack::getTop(T &x) { if(IsEmpty()==true)return false; x=elements[top]; return true; }; 二叉树头文件 tree.h #include #include"stack.h" #include #include using namespace std; template struct BinTreeNode { T data; BinTreeNode *leftChild,*rightChild; BinTreeNode():leftChild(NULL),rightChild(NULL){} BinTreeNode(T x,BinTreeNode *l=NULL,BinTreeNode *r=NULL):data(x),leftChild(l),rightChild(r){} }; template class BinaryTree { public: BinTreeNode *root;//二叉树的根指针 BinTreeNode *current; T RefValue;//数据输入停止标志 BinaryTree():root(NULL){}//构造函数 BinaryTree(T value):RefValue(value),root(NULL){}//构造函数 BinaryTree(BinaryTree&s);//复制构造函数 ~BinaryTree(){destroy(root);}//析构函数 bool IsEmpty(){return (root==NULL)?true:false;}//判断二叉树空否 BinTreeNode *Parent(BinTreeNode *current)//返回父结点 {return(root==NULL || root==current)?NULL:Parent(root,current);} BinTreeNode *LeftChild(BinTreeNode *current)//返回左子女 {return(current!=NULL)?current->leftChild:NULL;} BinTreeNode *RightChild(BinTreeNode *current)//返回右子女 {return(current!=NULL)?current->rightChild:NULL;} int Height(){return Height(root);}//返回树高度 int Size(){return Size(root);}//返回结点数 BinTreeNode *getRoot()const{return root;}//取根 void preOrder(void( *visit)(BinTreeNode *p))//前序遍历 {preOrder(root,visit);}    void CreateBinTree_one(ifstream& in,BinTreeNode *& BT);//从文件读入建树 void CreateBinTree_two(ifstream& in,BinTreeNode *& subTree); void destroy(BinTreeNode *&subTree);//删除 int Height(BinTreeNode *subTree);//返回树高度 int Size(BinTreeNode *subTree);//返回结点数 void Leaf(BinTreeNode *subTree,int &x);//叶结点数目 BinTreeNode *Parent(BinTreeNode *subTree,BinTreeNode *current);//返回父结点 void Traverse(BinTreeNode *subTree);//前序遍历输出 void degree(BinTreeNode *subTree,char &x);//指定结点的度 void level(BinTreeNode *subTree,char &x,int &y);//指定结点的层次 void Search(BinTreeNode *subTree,char &x);//前序遍历搜索并查找指定结点的子女结点和父结点 void PrintBTree(BinTreeNode *subTree);//以广义表的形式输出 void perOrder(BinTreeNode* subTree,void(*visit)(BinTreeNode *p));//前序遍历 }; template void BinaryTree::destroy(BinTreeNode *&subTree) { if(subTree!=NULL) { destroy(subTree->leftChild); destroy(subTree->rightChild); delete subTree; } } template void BinaryTree::CreateBinTree_one(ifstream& in,BinTreeNode *& BT) { Stack *>s; BT=NULL; BinTreeNode *p,*t;int k; char ch; in>>ch; while(ch!='#') { switch(ch) { case '(':s.Push(p);k=1;break; case ')':s.Pop(t);break; case ',':k=2;break; default: p=new BinTreeNode(ch); if(BT==NULL) BT=p; else if(k==1) {s.getTop(t);t->leftChild=p;} else {s.getTop(t);t->rightChild=p;} } in>>ch; } } template void BinaryTree::CreateBinTree_two(ifstream& in,BinTreeNode *&subTree) 继续阅读