2023年C++二叉树基本操作实验报告

一、实验目的选择二叉链式存储结构作为二叉树的存储结构，设计一个程序实现二叉树的基本操作(涉及建立、输出、前序遍历、中序遍历、后序遍历、求树高、记录叶子总数等)实验开发环境Windows8．１中文版ＭicrosofｔViｓｕａlStｕｄio6.0三、实验内容程序的菜单功能项如下:１－--－－-建立一棵二叉树2－----－前序遍历递归算法3-－-－-－前序遍历非递归算法４-－----中序遍历递归算法5--－－--中序遍历非递归算法6－-----后序遍历递归算法7----－-后序遍历非递归算法8--－--－求树高９-----－求叶子总数１0-----输出二叉树11-－-－-退出四、实验分析１、建立一棵二叉树2、输入二叉树各节点数据ｃｏut<<＂请按对的顺序输入二叉树的数据:";cｉn．geｔｌｉne(ｔ，１0００）;//先把输入的数据输入到一个t数组3、递归前序遍历vｏidBL1(ＥＣS_ｄatａ＊t){ｉf(NULL!＝ｔ)｛cout＜<t-＞data<<＂,";BL1(t->l）;BL1(t->r);}}4、非递归前序遍历ﻩvoiｄprｅOｒｄｅr2(ECS_dａｔa＊t)ﻩ{ stａck<ECS_dａta*＞s; ﻩECＳ_data*p=ｔ;ﻩﻩｗhilｅ(ｐ!=NUＬL｜|！s．empty（)) ﻩ｛ﻩﻩﻩｗhile（ｐ!＝ＮＵＬＬ) {ﻩ ﻩﻩcｏut<<p->dａｔa＜<""; ﻩﻩ s.ｐush(p);ﻩﻩ p=p-＞l;ﻩﻩ } if(!s.empｔy()) ｛ﻩ ﻩｐ=s．ｔop(）； ﻩﻩ s.poｐ(); ﻩ p=p->r;ﻩﻩﻩ｝ ｝ﻩ｝５、递归中序遍历voiｄBL2(ECS_dａta＊ｔ){if(NＵLL!＝ｔ）{BL2(ｔ－>l）;cout<<t->ｄata＜<",";BL2(t->r);}}６、非递归中序遍历ﻩvoidinOｒdeｒ２（ECS_datａ*t)／／非递归中序遍历 {ﻩ stack<ECS＿daｔa＊>s； ﻩECS_datａ*p=t;ﻩﻩwhile(p!=NULL||!ｓ.ｅmｐｔy(）)ﻩ {ﻩ whiｌe(p！=NUＬL）ﻩﻩ ｛ ﻩﻩﻩs.pusｈ(p); ﻩﻩ p=p-＞l;ﻩ }ﻩ if(！s．emｐty（))ﻩ ﻩ{ ﻩ ｐ=s.toｐ()； ﻩcout<＜ｐ－>daｔａ<<"＂; ﻩ s.pop（); ﻩ ﻩp=p->r; ﻩ}ﻩﻩ}ﻩ｝7、递归后序遍历voｉｄＢL３(ＥCＳ＿ｄata*t)｛if(ＮULL！=ｔ){BＬ3（t-＞l）;ＢＬ３（t->r);coｕt＜<t->dａｔa<<","；}}8、非递归后序遍历 voｉdｐostOrdeｒ3(ECS_dａta*ｔ)ﻩ{ stack<EＣS＿dａｔa*>s;ﻩ ECＳ_ｄata＊cur;//当前结点ﻩ EＣS_ｄａtａ＊pre=NULL;//前一次访问的结点 ﻩs.push(t）；ﻩ whｉle（!s.eｍｐｔy()）ﻩﻩ{ ｃur=s.top(); ﻩﻩif((cur－>l＝=NULＬ&＆ｃur->r==NULL)|| ﻩ ﻩ(pre!=NＵＬL&＆(pｒe==ｃuｒ-＞ｌ||pre==cｕr->ｒ))) ﻩ {ﻩ ﻩﻩcout<＜ｃuｒ->dａtａ＜<＂";／／假如当前结点没有孩子结点或者孩子节点都已被访问过 ﻩﻩs.pｏp(); ﻩ pre=cur; ﻩﻩ}ﻩﻩﻩelseﻩ ﻩ｛ ﻩﻩif（cur->r!=NＵLL)ﻩ ﻩ s.pusｈ（cur->r);ﻩ ﻩﻩiｆ(cur-＞l!=NＵＬL) ﻩ s.ｐush(cur-＞ｌ）; } }ﻩ}9、求树高ﻩintHｅiｇht（ECS_dａｔa*ｔ) ｛if(t==NＵＬL)reｔurｎ0;ﻩﻩelsｅ {ﻩﻩﻩiｎtm＝Ｈeigｈt(t－>l); ﻩﻩｉntn＝Heighｔ(t->r); ﻩ rｅturn（m>ｎ)?(m+１):(n+1);ﻩﻩ｝ ｝10、ﻩ求叶子总数inｔCountLeaf(ＥCS_dａta*t) ｛ sｔａｔｉｃintLeaｆNum＝0;//叶子初始数目为0,使用静态变量ﻩﻩif(ｔ）／／树非空ﻩﻩ{ﻩ ﻩｉf（ｔ－>l==ＮULL&＆t->r==NULL)／/为叶子结点ﻩ ﻩLeafＮuｍ+＋；//叶子数目加1ﻩ ｅlsｅ//不为叶子结点 ﻩ { ﻩﻩCountLeaf(t->l);//递归记录左子树叶子数目ﻩ ﻩ CountLｅaf(t->ｒ)；//递归记录右子树叶子数目 }ﻩ ｝ﻩﻩreturnLeafＮｕm; }五、运营结果附：完整程序源代码://二叉树链式存储的实现#incｌｕｄe<ｉoｓtreaｍ>#ｉnclude<cｓtｒinｇ＞#include<stａｃk>uｓingｎameｓpａｃestd;ｓtruｃtＥＣS_data／/先定义好一个数据的结构{ｃharｄata;ECS_ｄａｔa*ｌ;ECS_ｄatａ*r;};clａｓsECS｛ｐｒivate://iｎtleｖｅｌ;//树高intn;//表达有多少个节点数intｎ1;//表达的是数组的总长度值，（涉及#）,由于后面要进行删除判断ECＳ_datａ*temp[1000];pｕbｌｉc:ECS_data＊ｒoot；ECS(）/／初始化｛ＥＣS_dａta*ｐ;cｈart[１00０］;inｔi；ｉntｆront=０,rear＝1;//fronｔ表达有多少个节点,rear表达当前插入的点的父母coｕｔ<<"请按对的顺序输入二叉树的数据:";ｃin.geｔline（t，１０00);//先把输入的数据输入到一个t数组//cout<<t<＜＂"<<eｎdl;intｎ1＝ｓｔrlen（t);/／测量数据的长度ｎ=0；ｆｏr（ｉ=0;i<ｎ1;i++)｛if(t[i]！='#'){p=NULＬ;if(ｔ[i]！=','）//满足条件并开辟内存{n＋+;ｐ=newEＣS_ｄatａ;p->data＝t[i］;p->ｌ＝NULL;ｐ－>ｒ=NUＬL;}frｏnt++;temp[frｏnt]=p;iｆ（1==fｒｏnｔ){root=p；}else｛iｆ((p!=NULL)＆＆(０==frｏnt%2））｛tｅmｐ[rear］->l=p;／/刚开始把这里写成了＝＝}if（（p!=ＮULL)＆&(1==front%2)）{teｍp[rear]->r=p;｝if(1＝=ｆrｏｎｔ%2）ｒｅａr+＋;//就当前的数据找这个数据的父母}}}｝~ＥCS（)//释放内存｛inｔi;ｆoｒ（i＝1;i＜=n;ｉ++)iｆ（temp[ｉ]！=NULL)dｅletｅtｅmp［i］;}ｖoidJS()/／记录节点的个数{intｓ;ｓ＝n；couｔ<＜＂该二叉树的节点数为:＂<＜ｓ<<enｄl;}voiｄBＬ1(ECS_data＊t)/／递归前序遍历{ｉｆ(ＮUＬＬ!＝t)｛coｕｔ＜＜ｔ－＞ｄata＜<＂，";BL1(ｔ-＞l);ＢＬ１（t->ｒ)；}}ﻩｖoidpreOrｄer2(ECS＿datａ*t)//非递归前序遍历 { stacｋ＜ＥCS_datａ*>s;ﻩﻩＥCS_data*ｐ=t；ﻩ while(p！=NＵＬL||!s.eｍpty())ﻩ ｛ ﻩｗｈile(ｐ!=NＵLＬ)ﻩﻩ { ﻩ ﻩcout<<p－>daｔａ<＜""；ﻩﻩ ﻩｓ．pｕsh（ｐ）;ﻩ ﻩ p=p->ｌ;ﻩ }ﻩ ｉf（!ｓ．empty())ﻩ ﻩ{ﻩ p=s.ｔoｐ()；ﻩﻩ ｓ.poｐ();ﻩﻩﻩﻩp=ｐ->r;ﻩﻩﻩ} ﻩ} }ｖｏidBL２(ECS＿ｄａta*t)//递归中序遍历{if(NＵLＬ!=t)｛BL2（t－>l);coｕt<＜t->data＜<＂,＂;ＢL２（t->ｒ）；}}ﻩvoidinOｒdeｒ2（ECＳ_datａ*t)／/非递归中序遍历 { ﻩsｔaｃk<ＥＣS_data＊>s;ﻩ ECＳ＿ｄata*p=t;ﻩ whilｅ(p!=ＮULL|｜！s.ｅmptｙ()) { ﻩwｈile(ｐ!=NULＬ)ﻩﻩ ｛ﻩﻩﻩﻩs．push(p）；ﻩ ﻩp=ｐ－>ｌ; }ﻩ if(!s．ｅmpty()) { ﻩﻩ p=ｓ.top（);ﻩﻩﻩ coｕt<<p->data<＜"＂；ﻩ ﻩｓ.ｐop(); ﻩﻩ p=p－＞ｒ；ﻩ ﻩ} ｝ﻩ}ｖoidBL3(ＥCS_ｄata*ｔ）/／递归后序遍历{if（ＮUＬL!=ｔ){ＢＬ３(t－>l）；BL３(ｔ-＞r）;couｔ＜＜t->data<<",";｝} vｏiｄｐosｔOrder3(ＥＣS＿ｄata*t)//非递归后序遍历ﻩ{ﻩﻩｓtacｋ<EＣS＿daｔa＊＞s；ﻩ ECS_dａta*cuｒ；//当前结点 ＥCS_datａ*pｒｅ=ＮUＬL;//前一次访问的结点 s.puｓh(t);ﻩ wｈile(！s.emｐｔｙ()) ｛ ﻩcｕｒ=s.ｔoｐ（);ﻩﻩ if((cur->l=＝NULＬ&＆cｕr->r＝=NＵLＬ）|| ﻩﻩﻩ(prｅ!＝NUＬL&&(ｐrｅ=＝ｃur->l||prｅ==cuｒ->r)))ﻩ ﻩ{ﻩﻩﻩ cout＜<cuｒ->dａta<<＂＂;//假如当前结点没有孩子结点或者孩子节点都已被访问过ﻩﻩﻩﻩｓ.pop()； ﻩﻩﻩpre＝cur;ﻩ ｝ﻩ ﻩelsｅﻩﻩﻩ｛ﻩﻩ ﻩif(cｕｒ->r！=NＵＬL)ﻩﻩ ﻩs.pｕｓｈ(cｕr->r); ﻩif(cｕｒ->l！＝NULL) ﻩﻩ ｓ.push（cur->l);ﻩ ﻩ}ﻩ ｝ﻩ}ﻩintHｅiｇhｔ(EＣS＿data*ｔ)//求树高ﻩ{if(ｔ==NUＬＬ)reｔuｒn0; ﻩelse {ﻩﻩ intm＝Heｉght(t->l）；ﻩﻩﻩiｎｔn=Ｈｅight(t->r);ﻩﻩﻩｒeturｎ(m>n)?(ｍ＋１):(n+１);ﻩ ｝ }ﻩiｎtCｏuｎtLeaｆ(ECS_data*ｔ）／/求叶子总数ﻩ{ﻩﻩstａtiｃinｔLeａfNum=0;//叶子初始