数据结构二叉树子系统学习资料.docx
《数据结构二叉树子系统学习资料.docx》由会员分享，可在线阅读，更多相关《数据结构二叉树子系统学习资料.docx（17页珍藏版）》请在冰点文库上搜索。
数据结构二叉树子系统学习资料
数据结构：
二叉树子系统
/*
*题目：
按屏幕提示用前序方法建立一棵二叉树，并能按凹入法显示二叉树结构。
*编写前序遍历、中序遍历、后序遍历、层次遍历程序。
*编写求二叉树的叶结点数、总结点数和深度的程序。
*设计一个选择式菜单，以菜单方式选择下列操作。
*二叉树子系统
********************************
**1------建二叉树*
**2------凹入显示*
**3------先序遍历*
**4------中序遍历*
**5------后序遍历*
**6------层次遍历*
**7------求叶子数*
**8------求结点数*
**9------求树深度*
**0------返回*
********************************
*请选择菜单号（0--9）
*/
#include
#include
typedefstructbTree//二叉树结点
{
chardata;//值域
structbTree*lchild;//左孩子
structbTree*rchild;//右孩子
}BT;
BT*createTree（）;
voidshowTree（BT*t）;
voidpreOrder（BT*t）;
voidpostOrder（BT*t）;
voidinOrder（BT*t）;
voidlevelOrder（BT*t）;
intleafNum（BT*t）;
intnodeNum（BT*t）;
inttreeDepth（BT*t）;
/*************************************************
Function:
main（）
Description:
主调函数
Calls:
createTree（）
showTree（）
preOrder（）
postOrder（）
inOrder（）
leafNum（）
levelOrder（）
nodeNum（）
treeDepth（）
Input:
NULL
Return:
void
Others:
NULL
*************************************************/
voidmain（）
{
BT*t=NULL;
intchoice,k=1;
while（k）
{
printf（"\n二叉树子系统\n"）;
printf（"*******************************\n"）;
printf（"*1------建二叉树*\n"）;
printf（"*2------凹入显示*\n"）;
printf（"*3------先序遍历*\n"）;
printf（"*4------中序遍历*\n"）;
printf（"*5------后序遍历*\n"）;
printf（"*6------层次遍历*\n"）;
printf（"*7------求叶子数*\n"）;
printf（"*8------求结点数*\n"）;
printf（"*9------求树深度*\n"）;
printf（"*0------返回*\n"）;
printf（"*******************************\n"）;
printf（"请选择菜单号（0--9）：
"）;
fflush（stdin）;
scanf（"%d",&choice）;
switch（choice）
{
case1:
printf（"请输入根结点（'0'表示该结点为空）：
"）;
t=createTree（）;
printf（"二叉树建立成功。
\n"）;
break;
case2:
showTree（t）;
break;
case3:
printf（"先序遍历序列：
"）;
if（t==NULL）
{
printf（"空。
\n"）;
}
else
{
preOrder（t）;
}
break;
case4:
printf（"中序遍历序列：
"）;
if（t==NULL）
{
printf（"空。
\n"）;
}
else
{
inOrder（t）;
}
break;
case5:
printf（"后序遍历序列：
"）;
if（t==NULL）
{
printf（"空。
\n"）;
}
else
{
postOrder（t）;
}
break;
case6:
printf（"层次遍历序列：
"）;
if（t==NULL）
{
printf（"空。
\n"）;
}
else
{
levelOrder（t）;
}
break;
case7:
printf（"该二叉树的叶子数：
"）;
if（t==NULL）
{
printf（"0。
\n"）;
}
else
{
printf（"%d。
\n",leafNum（t））;
}
break;
case8:
printf（"该二叉树的结点数为：
"）;
if（t==NULL）
{
printf（"0。
\n"）;
}
else
{
printf（"%d。
\n",nodeNum（t））;
}
break;
case9:
printf（"该二叉树的深度为：
"）;
if（t==NULL）
{
printf（"0。
\n"）;
}
else
{
printf（"%d。
\n",treeDepth（t））;
}
break;
case0:
k=0;
break;
default:
k=1;
break;
}
}
}
/*************************************************
Function:
createTree（）
Description:
建立二叉树
Calls:
createTree（）
Input:
NULL
Return:
BT*
Others:
NULL
*************************************************/
BT*createTree（）//建立二叉树
{
BT*t;
charx;
getchar（）;
scanf（"%c",&x）;//获取输入的结点值
if（x=='0'）//输入的值为零，结点为空
{
t=NULL;
}
else
{
t=（BT*）malloc（sizeof（BT））;
t->data=x;//赋值
printf（"请输入结点%c的左孩子：
",t->data）;
t->lchild=createTree（）;//递归建立左孩子
printf（"请输入结点%c的右孩子：
",t->data）;
t->rchild=createTree（）;//递归调用
}
returnt;
}
/*************************************************
Function:
showTree（）
Description:
凹入显示二叉树
Calls:
void
Input:
t：
结点指针
Return:
void
Others:
NULL
*************************************************/
voidshowTree（BT*t）//显示二叉树
{
BT*sta[100],*p;
intlev[100][2];//第一个空存要空的长度，第二空存左右孩子的标示
inttp,n,i,wid=4;
if（t!
=NULL）//结点非空
{
printf（"凹入表示法:
\n"）;
tp=1;
sta[tp]=t;//将各个结点的指针放在指针数组中
lev[tp][0]=wid;//显示的前面的空白长度
while（tp>0）
{
p=sta[tp];
n=lev[tp][0];
//显示
for（i=0;i{
printf（""）;
}
printf（"%c",p->data）;
for（i=n+1;i<30;i+=2）
{
printf（"▄"）;
}
printf（"\n"）;
tp--;
//记录左右孩子
if（p->lchild!
=NULL）
{
tp++;
sta[tp]=p->lchild;
lev[tp][0]=n+wid;
lev[tp][1]=1;
}
if（p->rchild!
=NULL）
{
tp++;
sta[tp]=p->rchild;
lev[tp][0]=n+wid;
lev[tp][1]=2;
}
}
}
}
/*************************************************
Function:
preOrder（）
Description:
先序遍历
Calls:
preOrder（）
Input:
t：
结点指针
Return:
void
Others:
NULL
*************************************************/
voidpreOrder（BT*t）//先序遍历
{
if（t）//结点不为空
{
printf（"%3c",t->data）;//显示
preOrder（t->lchild）;//递归调用
preOrder（t->rchild）;
}
}
/*************************************************
Function:
postOrder（）
Description:
后序遍历
Calls:
postOrder（）
Input:
t：
结点指针
Return:
void
Others:
NULL
*************************************************/
voidpostOrder（BT*t）//后序遍历
{
if（t）//结点不为空
{
postOrder（t->lchild）;
postOrder（t->rchild）;
printf（"%3c",t->data）;//显示
}
}
/*************************************************
Function:
inOrder（）
Description:
中序遍历
Calls:
inOrder（）
Input:
t：
结点指针
Return:
void
Others:
NULL
*************************************************/
voidinOrder（BT*t）//中序遍历
{
if（t）//结点不为空
{
inOrder（t->lchild）;
printf（"%3c",t->data）;//显示
inOrder（t->rchild）;
}
}
/*************************************************
Function:
levelOrder（）
Description:
层次遍历
Calls:
void
Input:
t：
结点指针
Return:
void
Others:
NULL
*************************************************/
voidlevelOrder（BT*t）//层次遍历
{
inti,j;
BT*q[100];//指针数组
BT*p;
p=t;
if（p!
=NULL）//结点非空
{
i=1;
q[i]=p;
j=2;
}
while（i!
=j）//先将每个结点的指针存入指针数组中，在显示出来
{
p=q[i];
printf（"%3c",p->data）;
if（p->lchild!
=NULL）//左孩子非空
{
q[j]=p->lchild;
j++;
}
if（p->rchild!
=NULL）//左孩子非空
{
q[j]=p->rchild;
j++;
}
i++;//为了显示下一个结点
}
}
/*************************************************
Function:
leafNum（）
Description:
求二叉树叶子数
Calls:
leafNum（）
Input:
t：
结点指针
Return:
int
Others:
NULL
*************************************************/
intleafNum（BT*t）//叶子数
{
inti=0;
if（t->lchild==NULL&&t->rchild==NULL）//左右孩子都为空
{
i++;
}
else
{
i=leafNum（t->lchild）+i;//递归访问左孩子的叶子数
i=leafNum（t->rchild）+i;
}
returni;
}
/*************************************************
Function:
nodeNum（）
Description:
求二叉树结点数
Calls:
nodeNum（）
Input:
t：
结点指针
Return:
int
Others:
NULL
*************************************************/
intnodeNum（BT*t）//结点数
{
inti=0;
if（t）//结点不为空
{
i++;
i=nodeNum（t->lchild）+i;
i=nodeNum（t->rchild）+i;
}
returni;
}
/*************************************************
Function:
treeDepth（）
Description:
求二叉树的深度
Calls:
treeDepth（）
Input:
t：
结点指针
Return:
int
Others:
NULL
*************************************************/
inttreeDepth（BT*t）//二叉树的深度
{
intldep,rdep;
if（t==NULL）//结点不为空
{
return0;
}
else
{
ldep=treeDepth（t->lchild）;
rdep=treeDepth（t->rchild）;
if（ldep>rdep）//左深度大于右深度
{
returnldep+1;//返回左深度的值
}
else
{
returnrdep+1;
}
}
}
升级会员 