二叉树的建立、输出、结点、高度、叶结点的输出

《二叉树的建立、输出、结点、高度、叶结点的输出》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、7二叉树的操作【实验简介】二叉树是树形结构的一种重要类型。通过本次实验，熟悉二叉树结点的结构，掌握二叉树的基本操作以及具体实现，学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。【实验内容】编写程序，实现对二叉树的以下操作：1．建立二叉树。2．按任一种遍历次序输出二叉树中的所有结点。3．求二叉树的深度。4．求二叉树中的所有节点数。5．求二叉树中的所有叶子节点数。6．清除二叉树，使之编程一只空树。【主要代码】#includeusingnamespacestd;templatestructBinTr

2、eeNode//二叉树结点类定义{Tdata;//数据域BinTreeNode*leftChild,*rightChild;//左子女、右子女链域BinTreeNode()//构造函数{leftChild=NULL;rightChild=NULL;}BinTreeNode(Tx,BinTreeNode*left=NULL,BinTreeNode*right=NULL){data=x;leftChild=left;rightChild=right;}};templateclassBinaryTree{//二叉

3、树类定义public:BinaryTree(){root=NULL;}//构造函数BinaryTree(Tvalue)//构造函数{RefValue=value;root=NULL;}~BinaryTree(){destroy(root);}//析构函数boolIsEmpty(){returnroot==NULL;}//判二叉树空否intHeight(){returnHeight(root);}//求树高度intSize(){returnSize(root);}//求结点数BinTreeNode*getRoot(){returnroo

4、t;}BinTreeNode*LeftChild(BinTreeNode*cur)//返回左子女{return(cur!=NULL)?cur->leftChild:NULL;}BinTreeNode*RightChild(BinTreeNode*cur)//返回右子女{return(cur!=NULL)?cur->rightChild:NULL;}voidOutput(BinTreeNode*subtree);//输出结点voidBinaryTreeCount(BinTreeNode*BT,int&m1,

5、int&m2);//输出结点数和叶结点数4voidSetRefValue(T&M){RefValue=M;}//设置数据输入停止标志voidSetroot(BinTreeNode*N){root=N;}//设置根节点voidCreateBinTree(BinTreeNode*&subTree);protected:BinTreeNode*root;//二叉树的根指针TRefValue;//数据输入停止标志//voidCreateBinTree(istream&in,BinTreeNode*&subTree);//从文

6、件读入建树voiddestroy(BinTreeNode*&subTree);//删除intHeight(BinTreeNode*subTree)const;//返回树高度intSize(BinTreeNode*subTree)const;//返回结点数BinTreeNode*Parent(BinTreeNode*subTree,BinTreeNode*cur);//返回父结点friendostream&operator<<(ostream&out,BinaryTree&Tree);};templa

7、tevoidBinaryTree::destroy(BinTreeNode*&subTree)//私有函数:删除根为subTree的子树{if(subTree!=NULL){destroy(subTree->leftChild);//删除左子树destroy(subTree->rightChild);//删除右子树deletesubTree;//删除根结点}};templatevoidBinaryTree::CreateBinTree(BinTreeNode*&subTree){Tit

8、em;cin>>item;//读入根结点的值if(item!=RefValue){subTree=newBinTreeNode(item);//建立根结点if(subTre