题目：
算法与数据结构课程设计 完整的二叉树结构的实现及测试 专 业 信息管理与信息系统 班 级 学 生 邹欣 学 号 3110302215 指导教师 鲍春波 章静 2012年 6月21日 – 27日
1. 系统分析
完整的二叉树结构的实现及测试，通过对每一个关于二叉树的功能，从创建、输入、遍历、求结点、求深度等分模块进行规划！在通过main 函数和函数调用的方法加以连接，设计一个主页面就可以了！
2. 系统设计
(1)：数据结构设计思想
根据二叉树的定义和特点，从根本上全面的反应二叉树的特点和知识！先写好每一个功能函数的代码，放在主函数的前面，再写好主函数的代码，在主函数中通过switch ……case ….. 相应的调用与用户选择一致的函数，从而测试每一个功能
。
(2)：系统功能总体设计
(3)：各个功能模块的详细设计
创建二叉树：
计算叶子节点： 计算节点数
树的深度 先序非递归遍历
中序递归遍历 先序递归遍历
4；系统界面设计：
-----------------------------------------------------------------------------------------
-
---------------------------------------------------------------------------------------
3
1) 函数原型 #include
#include
2) 主函数 void main(void)
{
int choice,Y;
BiTree TT,q;
menu();
TT=InitiateHead();
printf("\n请输入你的选择:\n");
scanf("%d",&choice);
while(choice)
{
switch(choice)
{
case 0:
system("cls");exite();break;
case 1:
system("cls");
printf("请输入结点如右面所示格式：1 2 3 0 4 0 0 0 5 6 7 0 0\n ");
CreateBiTree(&TT);menu();break;
case 2:
system("cls");
printf("请输入要查找的结点信息：\n");
scanf("%d",&Y);
q=Search(TT,Y);
if(q) printf("查找成功！！\n");
else printf("查找失败！！\n");
menu(); break;
case 3:
system("cls");bianli(TT);menu();break;
case 4:
system("cls");Root(TT);menu();break;
case 5:
system("cls");printf("打印出来的树的形状是：\n");
PrintTree(TT,0);menu();break;
3功能模块函数 :初始化二叉树
BiTree InitiateHead()
{
BiTNode *bt;
bt=(BiTNode*)malloc(sizeof(BiTNode));
bt->lchild=NULL;
bt->rchild=NULL;
return bt;
}
建立二叉树
void CreateBiTree(BiTree *T)
{
datatype ch;
scanf("%d",&ch);
if(ch==Nil)
*T=NULL;
else
{
*T=(BiTNode*)malloc(sizeof(BiTNode)); /为T 开区间/
if(!(*T)) /如果T 不为空/
return ;
(*T)->data=ch;
CreateBiTree(&((*T)->lchild)); /创建左孩子/
CreateBiTree(&((*T)->rchild)) ; / 创建右孩子/
}
}
查找值为X 的结点
BiTree Search(BiTree bt, datatype x)
{
BiTree p;
if(bt==NULL) /表空查找失败/
return NULL;
else if (bt->data==x)
return bt;
else
{
p=Search(bt->lchild,x);
if(p) /如果p 非空/
return p;
else
{
p=Search(bt->rchild,x);
if(p)
return p;
else
return NULL;
}
}
}
前序递归遍历此二叉树
void fInOrder(BiTree T)
{
if(T) /如果T 非空/
{
printf("%d",T->data); / 访问结点/
fInOrder(T->lchild); / 访问结点的左孩子/
fInOrder(T->rchild); / 访问结点的右孩子/
}
}
中序遍历此二叉树
void InOrder(BiTree T)
{
if(T) /如果T 非空/
{
InOrder(T->lchild); / 访问结点的左孩子/
printf("%d",T->data); / 访问结点/
InOrder(T->rchild); / 访问结点的右孩子/
} }
后序递归遍历此二叉树
void lInOrder(BiTree T)
{
if(T) /如果T 非空/
{
lInOrder(T->lchild); / 访问结点的左孩子/
lInOrder(T->rchild); / 访问结点的右孩子/
printf("%d",T->data); / 访问结点/
}
}
先序非递归遍历此二叉树
void NRPreOrder(BiTree bt)
{
BiTNode *stack[MAXSIZE]; /利用入栈出栈的思想来实现/
BiTNode *p;
int top=-1;
if(bt==NULL)
return ;
p=bt;
while(!(p==NULL&&top==-1)) /判断P 是否为空以及TOP 是否为-1，不是执行/ {
while(p!=NULL)
{
printf("%d",p->data); /输出根结点/
top++;
stack[top]=p; /左孩子一直入栈/
p=p->lchild; /到左孩子的叶子结点/
}
if(top
return;
else
{
p=stack[top]; /左孩子的叶子结点出栈/
top--;
p=p->rchild; /判断P 的右孩子是否为空/
}
}
}
中序非递归遍历此二叉树
void NRInOrder(BiTree bt)
{
BiTNode *stack[MAXSIZE];
BiTNode *p;
int top=-1;
if(bt==NULL)
return;
p=bt;
while(!(p==NULL&&top==-1)) /判断P 是否为空以及TOP 是否为-1，不是执行/ {
while(p!=NULL)
{
top++;
stack[top]=p;
p=p->lchild; /到左孩子的叶子结点/
}
if(top
return;
else
{
p=stack[top]; /左孩子的叶子结点出栈/ top--;
printf("%d",p->data); /输出根结点/
p=p->rchild; /判断P 的右孩子是否为空/ }
}
}
后序非递归遍历此二叉树
void NRPostOrder(BiTree bt)
{
BiTNode *stack[MAXSIZE],*p=bt /
int tag[MAXSIZE];
int top=-1;
do
{
while(p!=NULL)
{
stack[++top]=p;
tag[top]=0;
p=p->lchild;
}
if(top>=0)
{
if(!tag[top])
{
p=stack[top];
p=p->rchild;
tag[top]=1;
}
else
printf("%d",stack[top--]->data);
}
}while((p!=NULL)||(top>=0));
}
遍历此二叉树
void bianli (BiTree T)
{
int choice,a,b; 用do ….while …和栈的思想语句实现/
printf(" 请选择遍历的方法\n"); printf("**1---递归遍历*****\n"); printf("**2---非递归遍历*****\n"); scanf("%d",&choice);
switch(choice)
{
case 1:
printf("你选择的递归遍历\n"); printf("请再选择遍历的方法\n"); printf("**1---先序递归遍历**\n"); printf("**2---中序递归遍历**\n"); printf("**3---后序递归遍历**\n"); scanf("%d",&a);
switch(a)
{
case 1:
printf("先序递归遍历的结果是;\n"); fInOrder(T);break;
case 2:
printf("中序递归遍历的结果是;\n"); InOrder(T);break;
case 3:
printf("后序递归遍历的结果是;\n"); lInOrder(T);break;
}
break;
case 2:
printf("你选择的非递归遍历\n"); printf("请再选择遍历的方法\n"); printf("**1---先序非递归遍历**\n"); printf("**2---中序非递归遍历**\n"); printf("**3---后序非递归遍历**\n"); scanf("%d",&b);
switch(b)
{
case 1:
printf("先序非递归遍历的结果是;\n"); NRPreOrder(T);break;
case 2:
printf("中序非递归遍历的结果是;\n"); NRInOrder(T);break;
case 3:
printf("后序非递归遍历的结果是;\n"); NRPostOrder(T);break;
break;
}
printf("\n");
}
int Visit(BiTNode *bn)
{
return bn->data;
}
求二叉树的根
void Root(BiTree bt)
{
if(bt==NULL)
printf("根为空\n");
else
printf("二叉树的根是%d\n",bt->data);
}
打印二叉树
void PrintTree(BiTree T,int m) /递归调用打印二叉树/
{
int j;
if(T->rchild)
PrintTree(T->rchild,m+1);
for(j=1;j
printf(" "); /打印空格/
if(T->lchild)
PrintTree(T->lchild,m+1);
}
计算叶子结点
int CountLeaf(BiTree bt)
{
if(bt==NULL)
return 0;
if(bt->lchild==NULL&&bt->rchild==NULL) /判断是否为叶子结点/ return 1;
return(CountLeaf(bt->lchild)+CountLeaf(bt->rchild)); / 左右叶子结点数相加/ }
计算结点数
int CountBiTNodes(BiTree bt)
if(bt==NULL)
return 0;
if(bt->lchild==NULL&&bt->rchild==NULL)
return 1;
return (CountBiTNodes(bt->lchild)+CountBiTNodes(bt->rchild)+1); /递归调用/ }
计算树的深度
int CountDepth(BiTree bt)
{
int lChildDepth, rChildDepth;
if(bt==NULL)
return 0;
if (bt->lchild==NULL&&bt->rchild==NULL) /一直深入查找，递归调用/ return 1;
else
{
lChildDepth=CountDepth(bt->lchild); /递归调用/
rChildDepth=CountDepth(bt->rchild); /递归调用/
return((lChildDepth>rChildDepth)?(lChildDepth+1):(rChildDepth+1));/谁大取谁/ }
}
退出
void exite(void)
{
printf("bye bye!\n");
exit(0);
}
界面菜单
void menu(void)
{
printf(" ||----------------------------|||\n");
printf(" ||完整二叉树的实现及测试|||\n");
printf(" ||0----退出--------------------|||\n");
printf(" ||1：建立二叉树------------|||\n");
printf(" ||2：查找值为X 是我结点-|||\n");
printf(" ||3：遍历此二叉树----------|||\n");
printf(" ||4：求二叉树的根-----------||\n");
printf(" ||5：打印此二叉树-----------|||\n");
printf(" ||6;计算叶子结点-----------|||\n");
printf(" ||7：计算结点数---------|||\n");
printf(" ||8：计算树的深度------|||\n");
}
4. 系统测试
选择1---- 选择2---
选择3-1-1
选择4:--
选择5—
选择
6--------
选择
7---
选择
8----
5. 心得体会：
写的不好，请多多关照。
6. 参考文献
1：数据结构课本—厦大出版社- 2：网站资料-------
题目：
算法与数据结构课程设计 完整的二叉树结构的实现及测试 专 业 信息管理与信息系统 班 级 学 生 邹欣 学 号 3110302215 指导教师 鲍春波 章静 2012年 6月21日 – 27日
1. 系统分析
完整的二叉树结构的实现及测试，通过对每一个关于二叉树的功能，从创建、输入、遍历、求结点、求深度等分模块进行规划！在通过main 函数和函数调用的方法加以连接，设计一个主页面就可以了！
2. 系统设计
(1)：数据结构设计思想
根据二叉树的定义和特点，从根本上全面的反应二叉树的特点和知识！先写好每一个功能函数的代码，放在主函数的前面，再写好主函数的代码，在主函数中通过switch ……case ….. 相应的调用与用户选择一致的函数，从而测试每一个功能
。
(2)：系统功能总体设计
(3)：各个功能模块的详细设计
创建二叉树：
计算叶子节点： 计算节点数
树的深度 先序非递归遍历
中序递归遍历 先序递归遍历
4；系统界面设计：
-----------------------------------------------------------------------------------------
-
---------------------------------------------------------------------------------------
3
1) 函数原型 #include
#include
2) 主函数 void main(void)
{
int choice,Y;
BiTree TT,q;
menu();
TT=InitiateHead();
printf("\n请输入你的选择:\n");
scanf("%d",&choice);
while(choice)
{
switch(choice)
{
case 0:
system("cls");exite();break;
case 1:
system("cls");
printf("请输入结点如右面所示格式：1 2 3 0 4 0 0 0 5 6 7 0 0\n ");
CreateBiTree(&TT);menu();break;
case 2:
system("cls");
printf("请输入要查找的结点信息：\n");
scanf("%d",&Y);
q=Search(TT,Y);
if(q) printf("查找成功！！\n");
else printf("查找失败！！\n");
menu(); break;
case 3:
system("cls");bianli(TT);menu();break;
case 4:
system("cls");Root(TT);menu();break;
case 5:
system("cls");printf("打印出来的树的形状是：\n");
PrintTree(TT,0);menu();break;
3功能模块函数 :初始化二叉树
BiTree InitiateHead()
{
BiTNode *bt;
bt=(BiTNode*)malloc(sizeof(BiTNode));
bt->lchild=NULL;
bt->rchild=NULL;
return bt;
}
建立二叉树
void CreateBiTree(BiTree *T)
{
datatype ch;
scanf("%d",&ch);
if(ch==Nil)
*T=NULL;
else
{
*T=(BiTNode*)malloc(sizeof(BiTNode)); /为T 开区间/
if(!(*T)) /如果T 不为空/
return ;
(*T)->data=ch;
CreateBiTree(&((*T)->lchild)); /创建左孩子/
CreateBiTree(&((*T)->rchild)) ; / 创建右孩子/
}
}
查找值为X 的结点
BiTree Search(BiTree bt, datatype x)
{
BiTree p;
if(bt==NULL) /表空查找失败/
return NULL;
else if (bt->data==x)
return bt;
else
{
p=Search(bt->lchild,x);
if(p) /如果p 非空/
return p;
else
{
p=Search(bt->rchild,x);
if(p)
return p;
else
return NULL;
}
}
}
前序递归遍历此二叉树
void fInOrder(BiTree T)
{
if(T) /如果T 非空/
{
printf("%d",T->data); / 访问结点/
fInOrder(T->lchild); / 访问结点的左孩子/
fInOrder(T->rchild); / 访问结点的右孩子/
}
}
中序遍历此二叉树
void InOrder(BiTree T)
{
if(T) /如果T 非空/
{
InOrder(T->lchild); / 访问结点的左孩子/
printf("%d",T->data); / 访问结点/
InOrder(T->rchild); / 访问结点的右孩子/
} }
后序递归遍历此二叉树
void lInOrder(BiTree T)
{
if(T) /如果T 非空/
{
lInOrder(T->lchild); / 访问结点的左孩子/
lInOrder(T->rchild); / 访问结点的右孩子/
printf("%d",T->data); / 访问结点/
}
}
先序非递归遍历此二叉树
void NRPreOrder(BiTree bt)
{
BiTNode *stack[MAXSIZE]; /利用入栈出栈的思想来实现/
BiTNode *p;
int top=-1;
if(bt==NULL)
return ;
p=bt;
while(!(p==NULL&&top==-1)) /判断P 是否为空以及TOP 是否为-1，不是执行/ {
while(p!=NULL)
{
printf("%d",p->data); /输出根结点/
top++;
stack[top]=p; /左孩子一直入栈/
p=p->lchild; /到左孩子的叶子结点/
}
if(top
return;
else
{
p=stack[top]; /左孩子的叶子结点出栈/
top--;
p=p->rchild; /判断P 的右孩子是否为空/
}
}
}
中序非递归遍历此二叉树
void NRInOrder(BiTree bt)
{
BiTNode *stack[MAXSIZE];
BiTNode *p;
int top=-1;
if(bt==NULL)
return;
p=bt;
while(!(p==NULL&&top==-1)) /判断P 是否为空以及TOP 是否为-1，不是执行/ {
while(p!=NULL)
{
top++;
stack[top]=p;
p=p->lchild; /到左孩子的叶子结点/
}
if(top
return;
else
{
p=stack[top]; /左孩子的叶子结点出栈/ top--;
printf("%d",p->data); /输出根结点/
p=p->rchild; /判断P 的右孩子是否为空/ }
}
}
后序非递归遍历此二叉树
void NRPostOrder(BiTree bt)
{
BiTNode *stack[MAXSIZE],*p=bt /
int tag[MAXSIZE];
int top=-1;
do
{
while(p!=NULL)
{
stack[++top]=p;
tag[top]=0;
p=p->lchild;
}
if(top>=0)
{
if(!tag[top])
{
p=stack[top];
p=p->rchild;
tag[top]=1;
}
else
printf("%d",stack[top--]->data);
}
}while((p!=NULL)||(top>=0));
}
遍历此二叉树
void bianli (BiTree T)
{
int choice,a,b; 用do ….while …和栈的思想语句实现/
printf(" 请选择遍历的方法\n"); printf("**1---递归遍历*****\n"); printf("**2---非递归遍历*****\n"); scanf("%d",&choice);
switch(choice)
{
case 1:
printf("你选择的递归遍历\n"); printf("请再选择遍历的方法\n"); printf("**1---先序递归遍历**\n"); printf("**2---中序递归遍历**\n"); printf("**3---后序递归遍历**\n"); scanf("%d",&a);
switch(a)
{
case 1:
printf("先序递归遍历的结果是;\n"); fInOrder(T);break;
case 2:
printf("中序递归遍历的结果是;\n"); InOrder(T);break;
case 3:
printf("后序递归遍历的结果是;\n"); lInOrder(T);break;
}
break;
case 2:
printf("你选择的非递归遍历\n"); printf("请再选择遍历的方法\n"); printf("**1---先序非递归遍历**\n"); printf("**2---中序非递归遍历**\n"); printf("**3---后序非递归遍历**\n"); scanf("%d",&b);
switch(b)
{
case 1:
printf("先序非递归遍历的结果是;\n"); NRPreOrder(T);break;
case 2:
printf("中序非递归遍历的结果是;\n"); NRInOrder(T);break;
case 3:
printf("后序非递归遍历的结果是;\n"); NRPostOrder(T);break;
break;
}
printf("\n");
}
int Visit(BiTNode *bn)
{
return bn->data;
}
求二叉树的根
void Root(BiTree bt)
{
if(bt==NULL)
printf("根为空\n");
else
printf("二叉树的根是%d\n",bt->data);
}
打印二叉树
void PrintTree(BiTree T,int m) /递归调用打印二叉树/
{
int j;
if(T->rchild)
PrintTree(T->rchild,m+1);
for(j=1;j
printf(" "); /打印空格/
if(T->lchild)
PrintTree(T->lchild,m+1);
}
计算叶子结点
int CountLeaf(BiTree bt)
{
if(bt==NULL)
return 0;
if(bt->lchild==NULL&&bt->rchild==NULL) /判断是否为叶子结点/ return 1;
return(CountLeaf(bt->lchild)+CountLeaf(bt->rchild)); / 左右叶子结点数相加/ }
计算结点数
int CountBiTNodes(BiTree bt)
if(bt==NULL)
return 0;
if(bt->lchild==NULL&&bt->rchild==NULL)
return 1;
return (CountBiTNodes(bt->lchild)+CountBiTNodes(bt->rchild)+1); /递归调用/ }
计算树的深度
int CountDepth(BiTree bt)
{
int lChildDepth, rChildDepth;
if(bt==NULL)
return 0;
if (bt->lchild==NULL&&bt->rchild==NULL) /一直深入查找，递归调用/ return 1;
else
{
lChildDepth=CountDepth(bt->lchild); /递归调用/
rChildDepth=CountDepth(bt->rchild); /递归调用/
return((lChildDepth>rChildDepth)?(lChildDepth+1):(rChildDepth+1));/谁大取谁/ }
}
退出
void exite(void)
{
printf("bye bye!\n");
exit(0);
}
界面菜单
void menu(void)
{
printf(" ||----------------------------|||\n");
printf(" ||完整二叉树的实现及测试|||\n");
printf(" ||0----退出--------------------|||\n");
printf(" ||1：建立二叉树------------|||\n");
printf(" ||2：查找值为X 是我结点-|||\n");
printf(" ||3：遍历此二叉树----------|||\n");
printf(" ||4：求二叉树的根-----------||\n");
printf(" ||5：打印此二叉树-----------|||\n");
printf(" ||6;计算叶子结点-----------|||\n");
printf(" ||7：计算结点数---------|||\n");
printf(" ||8：计算树的深度------|||\n");
}
4. 系统测试
选择1---- 选择2---
选择3-1-1
选择4:--
选择5—
选择
6--------
选择
7---
选择
8----
5. 心得体会：
写的不好，请多多关照。
6. 参考文献
1：数据结构课本—厦大出版社- 2：网站资料-------