下载
加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 数据结构二叉树

数据结构二叉树.doc

数据结构二叉树

无言的小恋人
2019-06-14 0人阅读 举报 0 0 暂无简介

简介:本文档为《数据结构二叉树doc》,可适用于IT/计算机领域

Treeh声明树中的类以及结点结构,文件名为treeh#ifndefTREEH#defineTREEHtemplate<classT>树中结点采用孩子兄弟表示法structTNode{TdataTNode<T>*firstchild,*rightsib}template<classT>classTree{public:Tree()构造函数,初始化一棵树,其前序序列由键盘输入~Tree(void)析构函数,释放树中各结点的存储空间TNode<T>*Getroot()获得指向根结点的指针voidPreOrder(TNode<T>*root)前序遍历树voidPostOrder(TNode<T>*root)后序遍历树voidLeverOrder(TNode<T>*root)层序遍历树private:TNode<T>*root指向根结点的头指针voidRelease(TNode<T>*root)析构函数调用}#endif定义类中的成员函数,文件名为treecpp#include<iostream>#include<string>#include"treeh"usingnamespacestd**前置条件:树不存在*输入:无*功能:构造一棵树*输出:无*后置条件:产生一棵树*template<classT>Tree<T>::Tree(){constintMaxSize=intend=intfront=intfrontTemp=intrear=采用顺序队列,并假定不会发生上溢intj=TNode<T>*queueMaxSize声明一个队列TNode<T>*tempNode声明指向结点类型的指针TNode<T>*brotherNode工作指针TNode<T>*qTchcout<<"请输入创建一棵树的根结点数据"<<endlcin>>chroot=newTNode<T>root>data=chroot>firstchild=root>rightsib=queuerear=rootwhile(!end)若继续创建树{Tch,chcout<<"请输入父结点数据和孩子结点数据对:"<<endlcin>>ch>>chTNode<T>*p=newTNode<T>生成一个结点p>data=chp>firstchild=p>rightsib=queuerear=ptempNode=queuefront头结点出队,同时对头元素的标识符后移frontTemp=frontfjjaddtempNode=queuefrontTempfjjadd,取出头结点,不是出队while(ch!=tempNode>data){tempNode=queuefronttempNode=queuefrontTempfjjadd}if(tempNode>firstchild==)tempNode>firstchild=pelse{brotherNode=tempNode>firstchild工作指针指向结点的第一个孩子while(brotherNode!=)若第一个孩子有兄弟结点{q=brotherNodebrotherNode=brotherNode>rightsib工作指针指向第一个孩子的右兄弟}q>rightsib=p}cout<<"创建结束如果结束请按否则请按"<<endlcin>>end}}**前置条件:树已存在*输入:无*功能:释放树中各结点的存储空间*输出:无*后置条件:树不存在*template<classT>Tree<T>::~Tree(void){Release(root)}**前置条件:树已存在*输入:无*功能:获取指向树根结点的指针*输出:指向树根结点的指针*后置条件:树不变*template<classT>TNode<T>*Tree<T>::Getroot(){returnroot}**前置条件:树已存在*输入:无*功能:前序遍历树*输出:树中结点的一个线性排列*后置条件:树不变*template<classT>voidTree<T>::PreOrder(TNode<T>*root)前序遍历树{if(root==)return递归调用的结束条件else{cout<<root>data打印根节点PreOrder(root>firstchild)前序递归遍历root的第一个孩子PreOrder(root>rightsib)前序递归遍历root的右兄弟}}**前置条件:树已存在*输入:无*功能:后序遍历树*输出:树中结点的一个线性排列*后置条件:树不变*template<classT>voidTree<T>::PostOrder(TNode<T>*root){if(root==)return递归调用的结束条件else{PostOrder(root>firstchild)后序递归遍历root的第一个孩子cout<<root>data打印出root结点PostOrder(root>rightsib)后序递归遍历root的右兄弟}}**前置条件:树已存在*输入:无*功能:层序遍历树*输出:树中结点的一个线性排列*后置条件:树不变*template<classT>voidTree<T>::LeverOrder(TNode<T>*root){constintMAXQUEUESIZE=intfront=intrear=采用顺序队列,并假定不会发生上溢TNode<T>*queueMAXQUEUESIZE声明一个队列TNode<T>*tempNode声明指向结点类型的指针TNode<T>*brotherNode工作指针if(root==)return循环结束条件queuerear=root否则结点入队while(front!=rear)若队列中有结点{tempNode=queuefront头结点出队,同时对头元素的标识符后移cout<<tempNode>data打印出头结点brotherNode=tempNode>firstchild工作指针指向结点的第一个孩子while(brotherNode!=)若第一个孩子有兄弟结点{queuerear=brotherNode第一个孩子结点入队brotherNode=brotherNode>rightsib工作指针指向第一个孩子的右兄弟}}}**前置条件:树已经存在*输入:无*功能:释放树的存储空间,析构函数调用*输出:无*后置条件:树不存在*template<classT>voidTree<T>::Release(TNode<T>*root){if(root!=){Release(root>firstchild)释放第一个孩子Release(root>rightsib)释放右兄弟deleteroot}}Treemaincpp有关树的实现的主函数,文件名为treemaincpp#include<iostream>#include<string>#include"treecpp"usingnamespacestdvoidmain(){Tree<string>t创建一棵树*f例如对教材P图可按如下方式输入:AABACBDBE继续阅读

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

文档小程序码

使用微信“扫一扫”扫码寻找文档

1

打开微信

2

扫描小程序码

3

发布寻找信息

4

等待寻找结果

我知道了
评分:

/13

数据结构二叉树

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利