关闭

关闭

封号提示

内容

首页 二叉树的基本操作.doc

二叉树的基本操作.doc

二叉树的基本操作.doc

上传者: Lambert钟杰 2017-10-19 评分 5 0 167 23 759 暂无简介 简介 举报

简介:本文档为《二叉树的基本操作doc》,可适用于IT/计算机领域,主题内容包含二叉树的基本操作实验七二叉树的基本操作二叉树的遍历实验七二叉树的基本操作一、【实验目的】、掌握二叉树的顺序存储结构、掌握二叉树的链式存储结构、掌握二符等。

二叉树的基本操作实验七二叉树的基本操作二叉树的遍历实验七二叉树的基本操作一、【实验目的】、掌握二叉树的顺序存储结构、掌握二叉树的链式存储结构、掌握二叉树的基本操作(如左结点插入、右结点插入、左子树删除、右子树删除操作)二、【实验内容】、实现二叉树的插入操作并利用先序遍历的实现打印。A如图所示:BC打印的结果为:ABCDFGE以下是部分代码:DEBiTreehFGtypedefstructNode{DataTypedata*数据域*structNode*leftChild*左子树指针*structNode*rightChild*右子树指针*}BiTreeNode*结点的结构体定义**初始化创建二叉树的头结点*voidInitiate(BiTreeNode**root){*root=(BiTreeNode*)malloc(sizeof(BiTreeNode))(*root)>leftChild=(*root)>rightChild=}voidDestroy(BiTreeNode**root){if((*root)!=(*root)>leftChild!=)Destroy((*root)>leftChild)if((*root)!=(*root)>rightChild!=)Destroy((*root)>rightChild)free(*root)}*若当前结点curr非空在curr的左子树插入元素值为x的新结点**原curr所指结点的左子树成为新插入结点的左子树**若插入成功返回新插入结点的指针否则返回空指针*BiTreeNode*InsertLeftNode(BiTreeNode*curr,DataTypex){独立完成}*若当前结点curr非空在curr的右子树插入元素值为x的新结点**原curr所指结点的右子树成为新插入结点的右子树**若插入成功返回新插入结点的指针否则返回空指针*BiTreeNode*InsertRightNode(BiTreeNode*curr,DataTypex){BiTreeNode*s,*tif(curr==)returnt=curr>rightChild*保存原curr所指结点的右子树指针*s=(BiTreeNode*)malloc(sizeof(BiTreeNode))s>data=xs>rightChild=t*新插入结点的右子树为原curr的右子树*s>leftChild=curr>rightChild=s*新结点成为curr的右子树*returncurr>rightChild*返回新插入结点的指针*}*若curr非空删除curr所指结点的左子树**若删除成功返回删除结点的双亲结点指针否则返回空指针*BiTreeNode*DeleteLeftTree(BiTreeNode*curr){if(curr==||curr>leftChild==)returnDestroy(curr>leftChild)curr>leftChild=returncurr}*若curr非空删除curr所指结点的右子树**若删除成功返回删除结点的双亲结点指针否则返回空指针*BiTreeNode*DeleteRightTree(BiTreeNode*curr){if(curr==||curr>rightChild==)returnDestroy(curr>rightChild)curr>rightChild=returncurr}voidPreOrder(BiTreeNode*t,voidvisit(DataTypeitem))*使用visit()函数前序遍历二叉树t*{if(t!=){visit(t>data)PreOrder(t>leftChild,visit)PreOrder(t>rightChild,visit)}}voidvisit(DataTypeitem){printf("c",item)}主程序:#include<stdlibh>#include<stdioh>typedefcharDataType#include"BiTreeh"voidmain(void){插入操作独立完成printf("前序遍历:")PreOrder(root>leftChild,visit)Destroy(root)}三、【实验源代码】四、【实验结果】五、【实验心得】二叉树的遍历声明类BiTree及定义结构BiNode,文件名为bitreeh#ifndefBITREEH#defineBITREEHtemplate<classT>structBiNode二叉树的结点结构{TdataBiNode<T>*lchild,*rchild}template<classT>classBiTree{public:BiTree()构造函数初始化一棵二叉树其前序序列由键盘输入~BiTree(void)析构函数释放二叉链表中各结点的存储空间BiNode<T>*Getroot()获得指向根结点的指针voidPreOrder(BiNode<T>*root)前序遍历二叉树voidInOrder(BiNode<T>*root)中序遍历二叉树voidPostOrder(BiNode<T>*root)后序遍历二叉树voidLeverOrder(BiNode<T>*root)层序遍历二叉树private:BiNode<T>*root指向根结点的头指针BiNode<T>*Creat()有参构造函数调用voidRelease(BiNode<T>*root)析构函数调用}#endif定义类中的成员函数文件名为bitreecpp#include<iostream>#include<string>#include"bitreeh"usingnamespacestd**前置条件:二叉树不存在*输入:无*功能:构造一棵二叉树*输出:无*后置条件:产生一棵二叉树*template<classT>BiTree<T>::BiTree(){this>root=Creat()}**前置条件:二叉树已存在*输入:无*功能:释放二叉链表中各结点的存储空间*输出:无*后置条件:二叉树不存在*template<classT>BiTree<T>::~BiTree(void){Release(root)}**前置条件:二叉树已存在*输入:无*功能:获取指向二叉树根结点的指针*输出:指向二叉树根结点的指针*后置条件:二叉树不变*template<classT>BiNode<T>*BiTree<T>::Getroot(){returnroot}**前置条件:二叉树已存在*输入:无*功能:前序遍历二叉树*输出:二叉树中结点的一个线性排列*后置条件:二叉树不变*template<classT>voidBiTree<T>::PreOrder(BiNode<T>*root){if(root==)returnelse{cout<<root>data<<""PreOrder(root>lchild)PreOrder(root>rchild)}}**前置条件:二叉树已存在*输入:无*功能:中序遍历二叉树*输出:二叉树中结点的一个线性排列*后置条件:二叉树不变*template<classT>voidBiTree<T>::InOrder(BiNode<T>*root){if(root==)return递归调用的结束条件else{InOrder(root>lchild)中序递归遍历root的左子树cout<<root>data<<""访问根结点的数据域InOrder(root>rchild)中序递归遍历root的右子树}}**前置条件:二叉树已存在*输入:无*功能:后序遍历二叉树*输出:二叉树中结点的一个线性排列*后置条件:二叉树不变*template<classT>voidBiTree<T>::PostOrder(BiNode<T>*root){if(root==)return递归调用的结束条件else{PostOrder(root>lchild)后序递归遍历root的左子树PostOrder(root>rchild)后序递归遍历root的右子树cout<<root>data<<""访问根结点的数据域}}**前置条件:二叉树已存在*输入:无*功能:层序遍历二叉树*输出:二叉树中结点的一个线性排列*后置条件:二叉树不变*template<classT>voidBiTree<T>::LeverOrder(BiNode<T>*root){constintMaxSize=intfront=intrear=采用顺序队列并假定不会发生上溢BiNode<T>*QMaxSizeBiNode<T>*qif(root==)returnelse{Qrear=rootwhile(front!=rear){q=Qfrontcout<<q>data<<""if(q>lchild!=)Qrear=q>lchildif(q>rchild!=)Qrear=q>rchild}}}**前置条件:空二叉树*输入:数据ch*功能:初始化一棵二叉树,构造函数调用*输出:无*后置条件:产生一棵二叉树*template<classT>BiNode<T>*BiTree<T>::Creat(){BiNode<T>*rootTchcout<<"请输入创建一棵二叉树的结点数据"<<endlcin>>chif(ch=="#")root=else{root=newBiNode<T>生成一个结点root>data=chroot>lchild=Creat()递归建立左子树root>rchild=Creat()递归建立右子树}returnroot}**前置条件:二叉树已经存在*输入:无*功能:释放二叉树的存储空间析构函数调用*输出:无*后置条件:二叉树不存在*template<classT>voidBiTree<T>::Release(BiNode<T>*root){if(root!=){Release(root>lchild)释放左子树Release(root>rchild)释放右子树deleteroot}}二叉树的主函数文件名为bitreemaincpp#include<iostream>#include<string>#include"bitreecpp"usingnamespacestdvoidmain(){BiTree<string>bt创建一棵树BiNode<string>*root=btGetroot()获取指向根结点的指针cout<<"前序遍历"<<endlbtPreOrder(root)cout<<endlcout<<"中序遍历"<<endlbtInOrder(root)cout<<endlcout<<"后序遍历"<<endlbtPostOrder(root)cout<<endlcout<<"层序遍历"<<endlbtLeverOrder(root)cout<<endl}

类似资料

该用户的其他资料

贝利尼时期的声乐风格及其对歌剧的影响.doc

窦娥冤教案.doc

江淹《别赋》.doc

高调凤姐低调美国生活.doc

帝豪星港湾3期水景别墅营销推广方案-发徐.doc

职业精品

精彩专题

用户评论

0/200
    暂无评论
上传我的资料

精选资料

热门资料排行换一换

  • 思考的艺术 非凡大脑养成手册.p…

  • 人格心理学:人性及其差异的研究 …

  • 热应力竹内一郎.pdf

  • [现代汉语(重订本)].胡裕树.…

  • The Art of Creat…

  • 疲劳可靠性.pdf

  • 形态交易精要 揭秘蜡烛线组合形态…

  • 断裂力学 王铎.pdf

  • 断裂力学引论.pdf

  • 资料评价:

    / 13
    所需积分:0 立即下载

    意见
    反馈

    返回
    顶部