二叉树的应用数据结构课程设计

1、信息科学与技术学院数据结构课程设计报告题目名称：二叉树的应用专业班级：计算机科学与技术学生姓名：陈 杰学生学号：200808261指导教师：高 攀完成日期：2010-04目 录1、课程设计的目的、课程设计题目、题目要求21.1课程设计的目的31.2课程设计的题目31.3题目要求32课程设计的实验报告内容:43课程设计的原程序代码:44运行结果165. 课程设计总结216参考书目221课程设计的目的1.1课程设计的目的:通过以前的学习以及查看相关资料,按着题目要求编写程序,进一步加强对编程的训练,使得自己掌握一些将书本知识转化为实际应用当中.在整个程序中,主要应用的是链表,但是也运用了类.通过两

2、种方法解决现有问题.1.2课程设计的题目: 二叉树的应用1.3题目要求:1. 建立二叉树的二叉链表存储算法2. 二叉树的先序遍历，中序遍历和后序遍历输出3. 非递归的先序遍历，中序遍历4. 二叉树的层次遍历5. 判断此二叉树是否是完全二叉树6. 二叉树的左右孩子的交换2课程设计的实验报告内容:7. 通过递归对二叉树进行遍历。二叉树的非递归遍历主要采用利用队进行遍历。此后的判断此二叉树是否是完全二叉树也才采用队，而二叉树的左右孩子的交换则采用的是一个简单的递归。3课程设计的原程序代码:#include<iostream>using namespace std;#define MAXS

3、IZE 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

4、 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

5、(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<<" "/

6、 输出根结点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+N

7、ode(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

8、->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)/

9、后序遍历算法 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<<"

10、"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&&to

11、p=-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,re

12、ar;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;/*左右子树交换*/*将结点的左右子树

13、交换*/*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("

14、%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

15、->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<<&

16、quot;*"<<endl; cout<<"<< 0.建立二叉树 >>"<<endl; cout<<"<< 1.二叉树树深 >>"<<endl; cout<<"<< 2.二叉树结点数 >>"<<endl; cout<<"<< 3.二叉树的叶子结点 >>"<<endl; cout<<"

17、<< 4.二叉树的先序遍历 >>"<<endl; cout<<"<< 5.二叉树的中序遍历 >>"<<endl; cout<<"<< 6.二叉树的后序遍历 >>"<<endl; cout<<"<< 7.二叉树的非递归先序遍历 >>"<<endl; cout<<"<< 8.二叉树的非递归中序遍历 >>&q

18、uot;<<endl; cout<<"<< 9.二叉树的层次遍历 >>"<<endl; cout<<"<< 10.判断此树是否是完全二叉树 >>"<<endl; cout<<"<< 11.左右孩子交换 >>"<<endl; cout<<"<< 12.退出 >>"<<endl; cout<<"*

19、"<<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<<"该树的树深为:

20、"<<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<<"该树以先序遍历输出为

21、：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;cas