数据结构课程设计实验报告-二叉树的实现

1、数据结构实验报告题目：二义树的实现学号:姓名：东南大学成贤学院计算机系实验题目1.实验目的1. 掌握二叉树的基本操作，理解递归算法。2. 实验内容1.将下图所示二叉树采用二叉链表进行存储，然后进行各种操作测试。2. 实验步骤1. 启动 vc6.0：开始菜单一程序一microsoft visual studio 6.0 microsoft visual c+ 6.02. 建立工程：文件(file)新建(new)在弹出的对话框屮选择工程标签(project ) -* 选中选项：win32 console application (不能选别的)输入工程名(project name )选 择工程的存放

2、位置(location) -*单击"确定按钮(0k)-在弹出的対话框中选中选项： an empty project ->单击"完成按钮(finish)在弹出的对话框中单击“确定"按钮(0k )。3. 创建头文件：文件(file)-新建(new)-在弹出的对话框屮选择文件标签(files)- 选中选项：c/c+ header file -*输入头文件名(此处定义为"bin_tree_node.h n) f单击"确 定按钮(ok)obin_tree_node.h 内容如下：二叉树结点类模板template ele mtype>stru

3、ct bintree node数据成员：elemtyp e data;/ 数据域bint reenode<ei emtype> *leftchild; / 左孩子bint reenode<ei emtype> *rightchild ;/ 右孩子； 4 .创建头文件：文件(file)新建(new )在弹出的对话框屮选择文件标签(files ) f选中选项:c/c+ he ader file-*输入头文件名(此处定义为u binary_tree.h ”)单击"确 定按钮(0k )。binary_tree.h定义了链队的类模板，代码如下：#ifndef_binna

4、ry_t ree_h_#de fine _bin nary_tree_h_/二叉树类模板template el emtype>cla ssbinaryt reeprivat e:/二叉树的数据成员：bintr eenode<ele mtype> *ro ot;/二叉树的私有函数：void preorderh elp(bintre enode<elem type> *r);/ 先序遍历voi dlnorderh elp(bintre enode<elem type> *r);/ 中序遍历voi dpostorde rhelp(bint reenode&l

5、t;ei emtype> *r);/ 后序遍历v oid creat(bintreenod e<elemtype > *r, intflag,elemtypee mptelem type end);递归创建子树bi ntreenode elemtype>*getroot(); 返回根指针bintreeno de e> * locate (bintreeno de e> *r, ele mtype e); 査找元素值为 e 的结 点，返回指针.b intreenode *leftchil d(elemtype e);定位指定元素的左孩子，返回其指针。bintr

6、e enode type>*par ent(bintre enode type>*r, e lemtype e); /定位指定元素的 父结点bintre enode type>*lef tsibling(e lemtypee);定位指定元素的左兄弟intsi ze(bintree node ype> *r);intdepth (bintreeno de e> *r);i nt leaf(bi ntreenode elemtype>*r); /统计并返回叶子结点个数vo id clear(b intreenode *r);v oid displa ytreee

7、help (bintreeno de<elemtyp e> *r, int level);按树状形式显示以r为根的二叉树，level为层次数，可设根结点的层次数为1 pu blic:/二叉树公共方法声明：b inarytree( );/无参数的构造函数模板void createbit ree();/ 构造二叉树bintre enode<elem type> *get root();返回二叉树的根voi dlnorder();/二叉树的中序遍历void pr eorder();/二叉树的先序遍历void posto rder();/二叉树的后序遍历vo idlevelor

8、 der();/按层遍历int locate(ele mtype e);查找元素值为e的结点。int ge tleft(elem type e, el emtype ;读取指定元素的左孩子int ge tparent(ei emtypee,elemtype f);读取指定元素的父元素int getleftsib ling(elemt ype e, ele ;读取指定元素的左兄弟int ins ertchild(e lemtype e,elemtype x ,elemtype y);为指定元素e插入左、右孩子int setele m(elemtype e, elemt ype x);更新指定元素

9、int size();intdep th();in t leaf(); 统计并返回叶子结点个数virtua i "binaryt ree();/ 销毁二叉树void d isplaytree ();；函数实现由学生自己完成#end if5.创建源程序文件main.cpp :文件(file)新建(new)在弹出的对话框中选择文件标 签(files)选中选项：c+ source file 输入源程序文件名(main) -*单击"确定"按钮(0k)omain.cpp文件内容如下：#incl ude "binar y_tree.h"/ 二叉树类int

10、main (void)利用swtich构造菜单，对二叉树操作进行测试。(初始化，构造二叉树，图形显示， 前序，中序，后序遍历结果，求结点个数，二叉树深度，叶子结点树，查找结点，找指定 结点的左孩子，双亲，左兄弟，插入新的左、右孩子。注意：1 在编程过程中注意及时保存编写内容。3.实验结果1. binary_tree.h 的代码2. mai n.cpp 的代码3. 运行结果截图(可以有多张)1、binary_tree.h#pragma once ftincludc ” stdafx.h"using namespace std;/二叉树类模板template <class elcm

11、typc>class binarytrecprivate:/二叉树的数据成员：bi ntrccnodc<blcmtype>*root;/二叉树的私有函数：void preorderllelp(bintreexodeelemtype>*r) ;/ 先序遍历void inorderhelp(bintreexodeelemtype>*r) ;/ 中序遍历vo i d postorderhelp (bi ntreenode<elemtype> *r);/ 后序遍历void creat(bintrccnode<hiemtypc> *r,int fla

12、g, elcmtypc empty, elcmtypc end);/递归创建子树bintreenode<elemtype> *getroot () ;/返回根指针bintreenode<elemtype> *locate(bintreenode<elemtype> *r, elemtype e) ;/查找元素值为e 的结点，返回指针.bintrccnoclcelcmtype>*lcftchi.ld (elcmtypcc);定位指定元素的左孩子，返回其指针。bintreenode<elemtype>* parent (bintreexode&

13、lt;elemtype>*r, elemtype e);/定位指定元索的 父结点bi ntrccnode<e1emtype>* leftsib1ing(eiemtypc e):定位指定元素的左兄弟intsize(ihntreexode<elemtype> *r);intdepth(bintreenode<elemtype> *r);intleaf (bintreexode<elemtype> *r) ; /统计并返冋叶了结点个数voidclear(bintrccnodc<hlemtype> *r);void displaytrc

14、cehclp(bintrcexodc<l'lcmtypc> *r, int love.);/按树状形式显示以r为根的二叉树，level为层次数，可设根结点的层次数为1int size;public:/二叉树公共方法声明：binarytreeo ;/无参数的构造函数模板void createbitreeo ;/ 构造二叉树/bintreenode<elen)type> *getroot ();/ 返回二叉树的根void tnorder() ;/二叉树的中序遍历void preorder() ; /二-义树的先斥遍历void postordcro ; /二叉树的后序

15、遍历void levelorder () ;/按层遍历intlocate(：:leintype e);查找元素值为e的结点。int getleft (:- 1 emtypc e, elcmtypc &c):读取指定元素的左孩子int getparent(elemtype e, elemtype &f);/读取指定元索的父元索int getleftsibling(elemtype e, elemtype &s);读取指定元素的左兄弟int inscrtchiid(elemtype c, elemtype x, elemtype y); /为指定元素e插入左、右孩子int

16、setelem(elenitypee, elemtype x);/更新指定元素intsize();intdcptho ;int leaf (); 统计并返回叶子结点个数 virtuapbinarytree();/ 销毁一叉树 void displaytree();；template <class elemtypevoid binarytree<elemtype>:preorderllelp(bintreenodeelemtype>*1)/privateif (r != null)coutr->data，z "/ 访问根结点preorderhelp (r-

17、>leftch订d);/ 遍历左子树 preorderhelp(i>rightchiid) ;/ 遍历右了树templateclass elemtype>void binarytree<elemtype>:preorder()/public(preorderl le 1 p (root);template <class elemtype>void binarytree<elemtype>:inorderhelp(bintreenode<elemtype> *r)/ privateif (r!=null)(inorderhelp(

18、r->leftchild);/ 遍历左子树 cout « r* ”;/访问根结点inorderhelp(r->rightchild);/ 遍历右子树template <class elemtype>void binarytree<k1cmtypc>:inordcr()/ publicinorderhelp(root);template <class elemtype>void binarytree<k 1 cmtypc>:postorderllelp(bintrecnodcelcmtypc>*r)/ private(i

19、f (r != null)postorderhelp(r->leftchiid);/ 遍历左子树postordcrhelp (r->rightchi id);/ 遍丿力右子树cout « r->da/，"/ 访问根结点teniplateclass elemtype>void binarytrcc<elcnitrpc>:postordcr 0/ public(postorderhelp (root);teniplateclass elemtype> voidbinarrtrcc<elcmtypc>: level order

20、 0linkqueue<bintreexode<elemtypt > *>q;bintreeode<elemtype> *t 二 root:if (t !=nill) q. inqueue(t); / 如果根非空，则入队 whilcdq. empty 0)q. outqueue(t);cout" ”；/if (t->leftchild!=nlll)/左孩子非空q. inqueue(t->leftchild);/ 左孩子入队if (t->rightch订dunull)/右孩子非空q. inqueue(t->rightchild

21、);/ 右孩子入队teniplateclass elcmtype>binarytree<elemtype>:binarytree()root = null;template <classelcmtypc>void binarytree<elemtype>:createbitree()bintrccnode<elcmtype>* r;elcmtypccnd, empty, x;cout « 按先序序列的顺序输入-棵二叉树"« endl;cout "输入的结束标志是："；cin>>e

22、nd;cout 输入的空结点标志是：；cin>> empty;cout << "请开始输入："« endl;cin»x;r = newb i nt reeode<elemtype>r>data= x;r->leftchild= r->rightchild = null;root = r;creat (r, 0, empty, end);创建根结点的左子树creat (r, 1, empty, end) ;/创建根结点的右子树template <class elcmtypc>void bin

23、arytree<elemtype>:creat(bintreexode<elemtype> *r, int flag, elemtype empty,elemtype end)bintrccnodc<elemtype>*p;e1emtype x;cin >> x;if(x !=endx !=empty)p 二 newbiritreeode<elemtype> p->data= x; p->leftchild=p->rightchiid = null;if (flag= 0) r->lcftchild=p;/p为

24、左子树 else r->rightchild= p;/p为右子树size+;creat (p, 0, empty, end);递归创建左子树creat (p, 1, empty, end) ;/递归创建右子树template <class elemtype>bintreenode<elemtype>*binary ii .e<eiemtype>:getroot()return root;template <class elemtype>b i nt reenode<elemtype>*b i na iree<eiemtyp

25、e>:locate(bintreeodc<h1cmtypc> *r,elemtype e) /privateif (r=null)return null:if (厂一data 二二e)return r;bintrccnode<eiemtype> *p= locate(r->1eftchi1d, e);if(p =null)p = locate(r->rightchiid,c);returnp;template <class elemtype>int binarytrce<eicmtypc>:locate(eicmtypee) /

26、publicif(locate(root, e) = null)return false;el sereturn true;templateclass elemtype>bintreenode<elemtype>*binarytree<elemtype>:leftchi 1 d(eleintype e) /privatebintrccnoclc<elcmtypc>* cp= locate (root, c);if (ep = null) return null; 找不到结点eif (ep->leftch订d二二null) /e无左孩子return

27、 null;return cp->leftchiid;/返ale左孩了的指针template <class elemtype>int binarytree<elemtype>:getleft(elemtype e, elemtype &c)/public bintrccnode<eiemtype>* p=leftchi1d(e);if(p=null)return false; /c无左孩子c= p->data;return true;template <class elcmtype>elemtype c)bintrccnode

28、<elcmtypc>* binarytrce<elcmtype>:parent(bintrccnoclc<elcmtypc>*r, /privatebintreeode<eleintype>* p;if (r=null)return null;if (r->lcftch订d!=null&&i>lcftch订d->data =c) | (r->rightchild!=xlll&&r->rightchild->data =e) return r;/r是e的父结点，返回结点r的指针p

29、parent (r->leftchi id, e) ;/递归调用r的左 了树if (p = null) p =parent(r->rightchiid, c);return p;template <class elemtype>int binarytree<blemtypo>: :getparent(lilemtype e, elemtypc &f) /public if(root=null|root->data =e)return false;bintreenode<elemtype> *p = parent(root, e);i

30、f (p =null) return false; 树中无元素ef= p->data;return true;template <class elemtype>bintrcc.odc<eleintype>* binarytreo<eleintype>:leftsibling(:jcmtypc c)/private(if (root->data=e) return null;bi ntreenodee 1 enitype>*p 二 parent (root, e);if(p =null)return null;/无e结点if (p->l

31、cftchild->clata =c)/c 是其父亲的左孩子return null;returnp->leftchild; /返回e的左兄弟指针template <classklemtypc>int binarytrcc<elemtype>:getleftsibling(elenitype e, elemtype &s)if(root->data=e)return false; /根结点无兄弟bintrecnode<elemtype> *p =leftsibling(c);if (p = null) rcturnfalsc; /e无

32、左兄弟s= p->data;return true;template <class elemtype>int binarytrcc<elcmtype>:insertchild(elemtype e, elemtype x, elemtype y)b i ntreenodee 1 enitype>*ep, *xp, *yp;ep = locate (root, e) ;/定位元素cif(cp=null)return false; /找不到元素cxp = new bintreexode<elemtype>:xp->data 二x;xp->

33、rightchiid = null;yp = now bintrccode<e1emtypc>:yp->data =y;yp->leftchild = null;xp->leftch订d = ep->leftchild;ep->leftchild = xp; /结点x置为结点e的左孩子 yp->rightchilcl = cp->rightchild;ep->rightchild = yp;/结点y置为结点e的右孩子size 二size + 2;return true;template <class elcmtype>in

34、t binarytree<elemtype>:sete1em(elemtype e, elemtype x)bi ntrccnodceicmtypc>*p = locate(root,e);if(p =null)return false;p->data =x;returntrue;template <class elcmtype>int binarrtrcc<elcmtypc>:size()/public(returnsize(root);template <class elcmtype>int binarrtrcc<elcmt

35、ypc>:size(bi nt reenode<e1emtype>*r) /privateif (r = null)returno;else+ 1；/privatereturn size(r->lcftchild) + size(r->rightchild)二叉树的结点总数为左右子树的结点数之和加1template <class elemtype>int binarylree<e1emtypc>:depth()/pub1icreturndeplh(tool);templateclass elemtype>i ntbi narytree

36、celcmtypc>:depth(bi ntreexodeelemtype>*r) if (r = null)returno;elseintleftl), rightl);lcftd= depth (r->lcftchild);rightd=depth(r->rightchiid);returnl+ (leftd>rightd?leftd : rightd); /二叉树的深度为左右子树的深度的最大值template <class elemtype>int binarytree<elemtype>:leaf()/publicrcturnlca

37、f(root);template <class elemtype>int binarytree<elemtype>:leaf(bintreexode<elemtype> *r)/private if (r=null)return 0：if (r->leftchild = nullr->rightchild = null)return1;returnleaf(r->leftchiid) + leaf(r>rightchiid);递归遍历左子树和右子树template <class elemtype>void binarytr

38、ee<elemtype>:clear(bintreexode<elemtype> *r)/private(if (r != null)clear(r->leftchild); 后序递归clear(r->rightchiid);deleter;size;templateclass elen)type>bin a r y t ree<l: 1 en)t y pe>: : “bin arytree ()clear(root);root=xull;template <class elemtype>void binarytrce<h

39、lemtypp>: :displa3rtreeelielp(bintreeode<h 1 cmtypp> *r, int if (r!=null)di splaytreeehelp(r->r i ghtch ild, 1 eve1+ 1);显示右子树cout << cndl;/显示新行for (int i= 0;i < level- 1;i+)cout « “；/确保在笫level列显示结点coutr->data;/ 显示结点displaytreeehelp(r->leftchild, level-*- 1);template &

40、lt;class elemtype>void binarytrec<elcmtype>:displaytree()displaytreeehelp (root,1);cout endl;#e nd if2、st da fx h#pragma once #includc z，targetvcr h"nclude bin_tree_node.h #include 1k_queue h #includc <iostream> ftincludc <cstdlib>3 main.cppinclude "stdafx. h"usin

41、g namespacestd;intmain() binarytree<int> bl;intc =0;inttmpl, tinp2, tmp3;while(c!= 15) cout « cndl «创建二叉树"cout<< endl "2.中序遍历"；cout « endl « "3.先序遍历"cout « endl<< "4.后序遍历"； cout endl << "5.按层遍历"cout <<

42、; cndl << "6.查找节点"； cout« endl "7.读取左孩子"； cout «endl < "8.读取父元素" cout << endl << "9.读取左兄弟"； cout << endl "10.插入左右孩子"； cout<< endl "11.更新元素"；cout «endl « "12.叶子结点个数"； cout « endl « "13.图形显示"； cout << endl << "14.销毁二叉树"； cout <