二叉树的应用_数据结构课程设计报告书.doc

.信息科学与技术学院数据结构课程设计报告题目名称：二叉树的应用专业_学生_学生_指导目 录1、课程设计的目的、课程设计题目、题目要求21.1课程设计的目的31.2课程设计的题目31.3题目要求32课程设计的实验报告内容:43课程设计的原程序代码:44运行结果165. 课程设计总结216参考书目221课程设计的目的1.1课程设计的目的:通过以前的学习以及查看相关资料,按着题目要求编写程序,进一步加强对编程的训练,使得自己掌握一些将书本知识转化为实际应用当中.在整个程序中,主要应用的是链表,但是也运用了类.通过两种方法解决现有问题.1.2课程设计的题目: 二叉树的应用1.3题目要求:1. 建立二叉树的二叉链表存储算法2. 二叉树的先序遍历,中序遍历和后序遍历输出3. 非递归的先序遍历,中序遍历4. 二叉树的层次遍历5. 判断此二叉树是否是完全二叉树6. 二叉树的左右孩子的交换2课程设计的实验报告内容:7. 通过递归对二叉树进行遍历。二叉树的非递归遍历主要采用利用队进行遍历。此后的判断此二叉树是否是完全二叉树也才采用队,而二叉树的左右孩子的交换则采用的是一个简单的递归。3课程设计的原程序代码:#include<iostream>using namespace std;#define MAXSIZE 100int sign=0;void menu<>/typedef struct BiTNodechar data;BiTNode *left_child,*right_child;BiTNode,*BiTree;int CreateBiTree<BiTree &T>/创建二叉树 char ch; cout<<"请输入数据#为结束: " cin>>ch; if<ch='#'> T=NULL; else if<!<T=new BiTNode>> cout<<"Overflow!"/no alloction return 0; T->data=ch; CreateBiTree<T->left_child>/create leftchild CreateBiTree<T->right_child> /create rightchild return 1;/判断此树是否是完全二叉树int LevelOrder1<BiTree &T>BiTree stackMAXSIZE;BiTreep;int front,rear;front=-1,rear=0;stackrear=T;while<rear!=front>front+;p=stackfront;if<<p->left_child=NULL>&&<p->right_child>>sign=1;if<p->left_child>rear+;stackrear=p->left_child;if<p->right_child>rear+;stackrear=p->right_child;return 1;void Output<BiTree &T> /输出二叉树if<!T> cout<<"空树!n"return ; /空树cout<<T->data<<" "/ 输出根结点if<T->left_child> Output<T->left_child> /输出左子树if<T->right_child>Output<T->right_child>/输出右子树int Depth<BiTree &T> /求树深int i,j;if<!T> return 0;i = Depth<T->left_child>j = Depth<T->right_child>return <i>j?i:j> + 1;int Node<BiTree &T>/求结点数if<!T> return 0;return 1+Node<T->left_child>+Node<T->right_child>int Leaf<BiTree &T> /求叶子结点if<!T> return 0;if<!T->left_child&&!T->right_child> return 1;/仅有根结点return Leaf<T->left_child>+Leaf<T->right_child>/返回叶子结点的数目void PreOrder<BiTree &T> /先序遍历算法 DLRif<!T> return ; /递归调用的结束条件cout<<T->data<<" " / 访问根结点的数据域PreOrder<T->left_child>/先序递归遍历T的左子树PreOrder<T->right_child>/先序递归遍历T的右子树void InOrder<BiTree &T>/中序遍历算法 LDRif<!T> return ;InOrder<T->left_child>cout<<T->data<<" "InOrder<T->right_child>void PostOrder<BiTree &T>/后序遍历算法 LRDif<!T> return ;PostOrder<T->left_child>PostOrder<T->right_child>cout<<T->data<<" "/非递归先序遍历int NRPreOrder<BiTree &T>BiTree stack100,p;int top;if<T=NULL>return 1;top=-1;p=T;while<!<p=NULL&&top=-1>>while<p!=NULL>cout<<p->data<<" "if<top<100-1>top+;stacktop=p;else cout<<"栈溢出"<<endl; return 0; p=p->left_child;if<top=-1>return 1;elsep=stacktop;top-;p=p->right_child; return 1;/非递归中序遍历int NRInOrder<BiTree &T>BiTree stack100,p;int top;if<T=NULL>return 1;top=-1;p=T;while<!<p=NULL&&top=-1>>while<p!=NULL>if<top<100-1>top+;stacktop=p;else cout<<"栈溢出"<<endl; return 0; p=p->left_child;if<top=-1>return 1;elsep=stacktop;cout<<p->data<<" "top-;p=p->right_child;return 1;/层次遍历void LevelOrder<BiTree &T>BiTree queue100;int front,rear;if<T=NULL>return;front=-1;rear=0;queuerear=T;while<front!=rear>front+;cout<<queuefront->data<<" "if<queuefront->left_child!=NULL>rear+;queuerear=queuefront->left_child;if<queuefront->right_child!=NULL>rear+;queuerear=queuefront->right_child;/*左右子树交换*/*将结点的左右子树交换*/*BiTNode *swap<BiTNode &T> BiTNode *t,*t1,*t2; if<T=NULL> t=NULL; else t=<BiTNode *>malloc<sizeof<BiTNode>> t->data=T->data; t1=swap<T->left_child> t2=swap<T->right_child> t->left_child=t2; t->right_child=t1; return<t> void print<BiTNode &T> if<T!=NULL> printf<"%c",T->data> if<T->left_child!=NULL|T->right_child!=NULL> printf<"<"> print<b->left_child> if<b->right_child!=NULL>printf<", "> print<b->right_child> printf<">"> */int PreOrderTraverse<BiTree T> if<!T>return 0;BiTree t;if <T->left_child|T->right_child> t=T->left_child;T->left_child=T->right_child;T->right_child=t;PreOrderTraverse<T->left_child>PreOrderTraverse<T->right_child>return 0;/菜单void menu<> cout<<"*"<<endl; cout<<"<< 主菜单 >>"<<endl; cout<<"*"<<endl; cout<<"<< 0.建立二叉树 >>"<<endl; cout<<"<< 1.二叉树树深 >>"<<endl; cout<<"<< 2.二叉树结点数 >>"<<endl; cout<<"<< 3.二叉树的叶子结点 >>"<<endl; cout<<"<< 4.二叉树的先序遍历 >>"<<endl; cout<<"<< 5.二叉树的中序遍历 >>"<<endl; cout<<"<< 6.二叉树的后序遍历 >>"<<endl; cout<<"<< 7.二叉树的非递归先序遍历 >>"<<endl; cout<<"<< 8.二叉树的非递归中序遍历 >>"<<endl; cout<<"<< 9.二叉树的层次遍历 >>"<<endl; cout<<"<< 10.判断此树是否是完全二叉树 >>"<<endl; cout<<"<< 11.左右孩子交换 >>"<<endl; cout<<"<< 12.退出 >>"<<endl; cout<<"*"<<endl;/主函数void main<> int br,a;BiTree T;br=CreateBiTree<T>while<1>menu<>cout<<"请输入选择的命令->"cin>>a;if<a>=0|a<=12>switch <a>case 0:cout<<"建立后的二叉树为：n"Output<T>cout<<endl;system<"pause">break;case 1:cout<<"该树的树深为: "<<Depth<T><<endl;system<"pause">break;case 2:cout<<"该树的结点数："<<Node<T><<endl;system<"pause">break;case 3:cout<<"该树的叶子结点为："<<Leaf<T><<endl;system<"pause">break;case 4:cout<<"该树以先序遍历输出为：n"PreOrder<T>cout<<endl;system<"pause">break;case 5:cout<<"该树以中序遍历输出为:n"InOrder<T>cout<<endl;system<"pause">break;case 6:cout<<"该树以后序遍历输出为：n"PostOrder<T>cout<<endl;system<"pause">break;case 7:cout<<"该树的非递归先序遍历输出为:n" NRPreOrder<T>cout<<endl;system<"pause">break;case 8:cout<<"该树的非递归中序遍历输出为:n" NRInOrder<T>cout<<endl;system<"pause">break;case 9:cout<<"该树的层次遍历：n"LevelOrder<T>cout<<endl;system<"pause">break;case 10:LevelOrder1<T>if<sign=1>cout<<"这不是一个完全二叉树。"<<endl;else cout<<"这是一个完全二叉树。"<<endl;/break;system<"pause">break;case 11:PreOrderTraverse<T> cout<<"左右孩子已经替换成功"<<endl;break;case 12:exit<-1>4运行结果:4. 1用二叉链表创建二叉树：4.2主菜单4.3求二叉树树深：4.4二叉树结点数:4.5二叉树的中序遍历:4.6二叉树的层次遍历：4.7左右孩子交换：4.8左右孩子交换后的中序遍历：4.9左右孩子交换后的层次遍历：5. 课程设计总结：此次课程设计使我对书本的知识有进一步了解。同时也是我知道自己的一些不足,这次课程设计我是在书本与同学的帮助下完成的。6参考书目：1.数据结构课本2.数据结构基本操作11 / 11