二叉树的应用数据结构课程设计样本.doc

资料内容仅供您学习参考，如有不当之处，请联系改正或者删除。

信息科学与技术学院
数据结构课程设计报告

题目名称:
二叉树的应用
专业班级:
计算机科学与技术
学生姓名:
陈 杰
学生学号:

指导教师:
高 攀

完成日期: -04

目 录

1、 课程设计的目的、 课程设计题目、 题目要求 2
1.1课程设计的目的 3

1.2课程设计的题目 3

1.3题目要求 3

2课程设计的实验报告内容: 4

3课程设计的原程序代码: 4

4运行结果 16

5. 课程设计总结 21

6参考书目 22

1课程设计的目的
1.1课程设计的目的:
经过以前的学习以及查看相关资料,按着题目要求编写程序,进一步加强对编程的训练,使得自己掌握一些将书本知识转化为实际应用当中.在整个程序中,主要应用的是链表,可是也运用了类.经过两种方法解决现有问题.
1.2课程设计的题目: 二叉树的应用
1.3题目要求:
1. 建立二叉树的二叉链表存储算法
2. 二叉树的先序遍历, 中序遍历和后序遍历输出
3. 非递归的先序遍历, 中序遍历
4. 二叉树的层次遍历
5. 判断此二叉树是否是完全二叉树
6. 二叉树的左右孩子的交换

2课程设计的实验报告内容:
7. 经过递归对二叉树进行遍历。二叉树的非递归遍历主要采用利用队进行遍历。此后的判断此二叉树是否是完全二叉树也才采用队, 而二叉树的左右孩子的交换则采用的是一个简单的递归。

3课程设计的原程序代码:
#include<iostream>
using namespace std;
#define MAXSIZE 100
int sign=0;
void menu();
//
typedef struct BiTNode
{
char 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 stack[MAXSIZE];
BiTree p;
int front,rear;

front=-1,rear=0;
stack[rear]=T;
while(rear!=front)
{
front++;
p=stack[front];
if((p->left_child==NULL)&&(p->right_child))
sign=1;
if(p->left_child)
{
rear++;
stack[rear]=p->left_child;
}
if(p->right_child)
{
rear++;
stack[rear]=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) //先序遍历算法 DLR
{
if(!T) return ; //递归调用的结束条件
cout<<T->data<<" "; // 访问根结点的数据域
PreOrder(T->left_child);//先序递归遍历T的左子树
PreOrder(T->right_child);//先序递归遍历T的右子树
}

void InOrder(BiTree &T)//中序遍历算法 LDR
{
if(!T) return ;
InOrder(T->left_child);
cout<<T->data<<" ";
InOrder(T->right_child);
}

void PostOrder(BiTree &T)//后序遍历算法 LRD
{
if(!T) return ;
PostOrder(T->left_child);
PostOrder(T->right_child);
cout<<T->data<<" ";
}

//非递归先序遍历
int NRPreOrder(BiTree &T)
{BiTree stack[100],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++;
stack[top]=p;
}
else{
cout<<"栈溢出"<<endl;
return 0;
}
p=p->left_child;
}
if(top==-1)
return 1;
else{
p=stack[top];
top--;
p=p->right_child;
}
}
return 1;}

//非递归中序遍历
int NRInOrder(BiTree &T)
{BiTree stack[100],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++;
stack[top]=p;
}
else{
cout<<"栈溢出"<<endl;
return 0;
}
p=p->left_child;
}
if(top==-1)
return 1;
else{
p=stack[top];
cout<<p->data<<" ";
top--;
p=p->right_child;
}
}
return 1;}

//层次遍历
void LevelOrder(BiTree &T)
{BiTree queue[100];
int front,rear;
if(T==NULL)
return;
front=-1;
rear=0;
queue[rear]=T;
while(front!=rear){
front++;
cout<<queue[front]->data<<" ";
if(queue[front]->left_child!=NULL){
rear++;
queue[rear]=queue[front]->left_child;
}
if(queue[front]->right_child!=NULL)
{
rear++;
queue[rear]=queue[front]->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. 《数据结构基本操作》