二叉树实验源代码

《二叉树实验源代码》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第五章树实验目的：1.掌握二叉树的链式存储结构的定义及实现方法。2.掌握二叉树的先序、中序和后序遍历方法。3.掌握二叉树的结点个数和树的深度的计算方法。实验内容：1.建立一棵含有n个结点的二叉树，采用二叉链表存储。2.分别用前序、中序和后序遍历该二叉树，输出访问到的结点。3.计算该二叉树的结点个数和二叉树的深度，输出计算结果。//参考代码#include#include#includetemplatestructBinTreeNode{//二叉树结点类定义Tdata;//数据域BinTreeNode

2、*leftChild,*rightChild;//左子女、右子女链域BinTreeNode():leftChild(NULL),rightChild(NULL){}//构造函数BinTreeNode(Tx,BinTreeNode*l=NULL,BinTreeNode*r=NULL){data=x;leftChild=l;rightChild=r;}};templateclassBinaryTree{//二叉树类定义public:BinaryTree(Tvalue):RefValue(value),root(NULL)//构造函数{CreateBinTree(

3、cin,root);}BinaryTree(BinaryTree&s);//复制构造函数~BinaryTree(){destroy(root);}//析构函数boolIsEmpty(){returnroot==NULL;}//判二叉树空否intHeight(){returnHeight(root);}//求树高度intSize(){returnSize(root);}//求结点数BinTreeNode*getRoot()const{returnroot;}//取根voidpreOrder(void(*visit)(BinTreeNode*p))//前序遍历{preOr

4、der(root,visit);}voidinOrder(void(*visit)(BinTreeNode*p))//中序遍历{inOrder(root,visit);}voidpostOrder(void(*visit)(BinTreeNode*p))//后序遍历{postOrder(root,visit);}protected:BinTreeNode*root;//二叉树的根指针TRefValue;//数据输入停止标志voidCreateBinTree(istream&in,BinTreeNode*&subTree);//从文件读入建树voiddestroy

5、(BinTreeNode*subTree);voidpreOrder(BinTreeNode*subTree,void(*visit)(BinTreeNode*p));//前序遍历voidinOrder(BinTreeNode*subTree,void(*visit)(BinTreeNode*p));//中序遍历voidpostOrder(BinTreeNode*subTree,void(*visit)(BinTreeNode*p));//后序遍历intSize(BinTreeNode*subTree)const;//返回结点数intHe

6、ight(BinTreeNode*subTree);//返回树高度//其他函数略};templatevoidBinaryTree::destroy(BinTreeNode*subTree){//删除根为subTree的子树if(subTree!=NULL){destroy(subTree->leftChild);//删除左子树destroy(subTree->rightChild);//删除右子树deletesubTree;//删除根结点}}templatevoidBinaryTree::CreateBinTree(istream

7、&in,BinTreeNode*&subTree){Titem;if(!in.eof()){//未读完,读入并建树in>>item;//读入根结点的值if(item!=RefValue){subTree=newBinTreeNode(item);//建立根结点if(subTree==NULL){cerr<<"存储分配错!"<leftChild);//递