《二叉树的建立与遍历.docx》由会员分享，可在线阅读，更多相关《二叉树的建立与遍历.docx（9页珍藏版）》请在课桌文档上搜索。
1、重庆高校本科同学课程设计任务书课程设计题目二叉树的建立与遍历学院软件学院专业软件工程班级问题描述：建立一棵二叉树，并对其进行遍历(先序、中序、后序)，打印输出遍历结果。基本要求：从键盘接受输入(先序)，以二叉链表作为存储结构，建立二叉树(以先序来建立)，并采纳递归算法对其进行遍历(先序、中序、后序)，将遍历结果打印输出。算法思想：从二叉树的递归定义可知，一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此，在任一给定结点上，可以按某种次序执行三个操作：(1)访问结点本身(N)(2)遍历该结点的左子树(L)(3)遍历该结点的右子树(R)以上三种操作有六种执行次序：NLR、LNR、LRN、
2、NRL、RNL、RLN。前三种次序与后三种次序对称，故只争论先左后右的前三种次序。中序遍历的递归算法定义：若二叉树非空，则依次执行如下操作：遍历左子树、访问根结点、遍历右子树。前序遍历的递归算法定义：若二叉树非空，则依次执行如下操作：访问根结点、遍历左子树、遍历右子树。后序遍历得递归算法定义：若二叉树非空，则依次执行如下操作：遍历左子树、遍历右子树、访问根结点。模块划分：1 .建立二叉树tree*CreatBitree()2 .基本运算voidpush(stack*top,tree*tree)树结点入栈voidpop(stack*top,tree*T)出栈，栈内元素赋值voidgetTop(s
3、tack*s,tree*t)猎取栈顶元素3 .递归遍历函数voidPrerder(tree*bl)前序遍历函数voidMidrder(tree*b2)/中序遍历函数voidLastrder(tree*b3)后序遍历函数数据结构：给出所使用的基本抽象数据类型，所定义的详细问题的数据类型,以及新定义的抽象数据类型。源程序：cppLcppIypedefcharEntry;templatestructBinary_node/datamembers:Entrydata;Binary_node*left;Binary_node*right;/constructors:Binary_node();Binar
4、y_node(constEntry&x);；templateclassBinary_treepublic:Binary_tree();boolempty()const;voidpreorder(void(*visit)(Enlry&);voidinorder(void(*visit)(Enlry&);voidpostorder(void(*visit)(Entry&);intsize()const;voidclear();intheight()const;voidinsert(constEntry&);Binary_tree(constBinary-tree&original);Binary_
5、tree&operator=(constBinary-tree&original);-Binary_tree();protected:/Addauxiliaryfunctionprototypeshere.Binary-node*root;intrecursiveheight(Binarynode*subroot)const;voidrecursive_insert(Binary_node*&sub_root,constEntry&x);voidrecursive_postorder(Binary_node*sub_root,void(*visit)(Entry&);voidrecursive
6、_preorder(Binary_node水SUb_root,VOid(*visit)(Entry&);voidrecursive_inorder(Binary_node*sub_rooLVoid(*visit)(Entry&);voidrecursive_clear(Binary_node*&sub_root);Binary-node*recursive_copy(Binary_node*sub_root);；cpp2.cpp#includecppl.cpp#includeusingnamespacestd;templateintBinary-tree:height()const*Post:
7、Theheightofthebinarytreeisreturned.*/(returnrecursive_height(root);1templateintBinary_tree:recursive_height(Binary_node*sub_root)const*Post:Theheightofthesubtreerootedatsub_rootisreturned.*/(if(sub_root=0)returnO;intL=recursive_height(sub_root-left);intR=recursive_height(sub_root-right);if(LR)return
8、1+L;elsereturn1+R;templateBinary-node:Binary_node(constEntry&x)(data=x;Ieft=O;right=O;templatevoidBinary_tree:insert(constEntry&x)*Post:TheEntryxisaddedtothebinarytree.*/(recursive_insert(root,x);1templatevoidBinary_tree:recursive_insert(Binary_node*&sub_root,constEntry&x)*Pre:sub_rootiseitherNULLor
9、pointstoasubtreeoftheBinary_tree.Post:TheEntryxhasbeeninsertedintothesubtreeinsuchawaythatthepropertiesofabinarysearchtreehavebeenpresen,ed.Uses:Thefunctionsrecursive_insert,recursive_height*/(if(sub_root=0)sub_root=newBinary-node(x);elseif(recursive_height(sub_root-right)left)recursive_insert(sub_r
10、oot-right,x);elserecursive_insert(sub_root-left,x);1templateBinary_tree:Binary_tree()*Post:Anemptybinarytreehasbeencreated.*/(root=0;templateboolBinarjMreeempty()const*Post:Aresultoftrueisreturnedifthebinarytreeisempty.Otherwise,falseisreturned.*/(returnroot=0;templatevoidBinary_tree:inorder(void(*v
11、isit)(Entry&)*Post:Thetreehasbeentraversedininordersequence.Uses:Thefunctionrecursive_inordcr*/(recursive_inorder(root,visit);templatevoidBinary_tree:recursive_inorder(Binary_node*sub_root,void(*visit)(Entry&)*Pre:sub_rootiseitherNULLorpointstoasubtreeoftheBinary_tree.Post:Thesubtreehasbeentraversed
12、ininordersequence.Uses:Thefunctionrecursive_inorderrecursively*/(if(sub_root!=0)recursive_inorder(sub_root-left,visit);(*visit)(sub-root-data);recursive_inorder(sub_root-right,visit);)1templatevoidBinary_tree:preorder(void(*visit)(Entry&)*Post:Thetreehasbeentraversedininordersequence.Uses:Thefunctio
13、nrecursive_inorder*/(recursive_preorder(root,visit);templatevoidBinarjMreerecursive-preorder(Binary-node*sub_root,void(*visit)(Entry&)*Pre:sub_rootiseitherNULLorpointstoasubtreeoftheBinarjMree.Post:Thesubtreehasbeentraversedinpreordersequence.Uses:Thefunctionrecursive-preorderrecursively*/(if(sub_ro
14、ot!=0)(*visit)(sub-root-data);recursive_preorder(sub_root-Ieft,visit);recursive_preorder(sub_root-right,visit);)templatevoidBinarjMree-postorder(void(*visit)(Entry&)*Post:Thetreehasbeentraversedininordersequence.Uses:Thefunctionrecursive_inorder*/(recursive_postorder(root,visit);1templatevoidBinary_
15、tree:recursive_postorder(Binary_node*sub_root,void(*visit)(Entry&)*Pre:sub_rootiseitherNULLorpointstoasubtreeoftheBinary_tree.Post:Thesubtreehasbeentraversedinpostordersequence.Uses:Thefunctionrecursive_postorderrecursively*/(if(sub_root!=0)(recursive_postorder(sub_root-left,visit);recursive_postord
16、er(sub_root-right,visit);(*visit)(sub-root-data);)1templatevoidBinar)Mreerecursive-clear(Binary-node*&sub_root)*Post:Thesubtreerootedatsub_rootiscleared.*/(Binary-node*temp=sub_root;if(subroot=0)return;recursive_clear(sub_root-left);recursive_clear(sub_root-right);sub_root=0;deletetemp;templatevoidB
17、inary_tree:clear()*Post:Allentriesofthebinaytreeareremoved.*/(recursive_clear(root);1templateBinary_tree:-Binary_tree()*Post:Allentriesofthebinarytreeareremoved.Alldynamicallyallocatedmemoryinthestructureisdeleted.*/(clear();1templateBinary_tree:Binary_tree(constBinary_treefeoriginal)*Post:Anewbinar
18、ytreeisinitializedtocopyoriginal.*/(root=recursive_copy(original,root);1templateBinary_node*Binary_tree:recursive_copy(Binary-node*sub_root)*Post:Thesubtreerootedatsub_rootiscopied,andapointertothertofthenewcopyisreturned.*/(if(sub_root=0)return0;Binary-node*temp=newBinary_node(sub_root-data);temp-l
19、eft=recursive_copy(sub_root-left);temp-right=recursive_copy(sub_root-right);returntemp;1templateBinary_tree&Binary_tree:operator=(constBinary_tree&original)*Post:Thebinarytreeisresettocopyoriginal.*/Binary_treenew_copy(original);clear();root=new_copy.root;new_copy.root=0;return*this;1cpp3.cpptypedef
20、chartype;#includecpp2.cpp#includeusingnamespacestd;voidvisitvisit(type&x);intmain()(COUtv输?入“?数y据Y个?数yvendl;Binary_treemytree;intn;cinn;COUtendlv以。?左右,。子树。乐高?度,差?不?超?过y-。?建：立旅二次?树ojAendl输?入2vvn个?type型数y据Yendl;fbr(inti=O;ij;mytree.insert(j);)CoUtVV”树OiA的1?高？度是?:VVmytree.height。endlprcordermytree.preo
21、rder(visitvisit);coutendl,inorder,;mytree.inorder(visitvisit);CoUtendlvpostorder;mytree.postorder(visitvisit);coutendl;returnO;1voidvisitvisit(type&x)coutx,;测试数据：ABCDEGF巾(其中少表示空格字符)则输出结果为：先序：ABCDEGF中序：CBEGDFA后序：CGBFDBA测试状况：GU*e学*DrkopD*StrWiSttSWtW(R*3)0W8JiBS-C同si版M第釐械一啦二叉树Abcdefg输出结果为：先序：ABCDEFG中序：CBEFDGA后序：CFBGDBA
