建立二叉树,并对树进行操作（数据结构）
题目：
建立二叉树，并对树进行操作
基本功能要求：
a) 利用完全二叉树的性质建立一棵二叉树。
b) 统计数叶子结点的个数。
c) 求二叉树的深度。
#include "stdlib.h " /* 存储分配头文件，或用 "malloc.h " */
#include "stdio.h " /* 标准I/O头文件 */
#include "ctype.h "
#define N 10000 /* 定义NULL,本行可省去 */
#define LENG sizeof(struct Bnode) /* 确定结点所占空间的字节数 */
typedef char ElemType; /* 抽象元素类型为char类型 */
typedef struct Bnode /* Bnode为结点(C结构体)类型 */
{ ElemType data; /* data为抽象元素类型 */
struct Bnode *lchild, *rchild; /* 为指针类型 */
signed size;
}Bnode;
int node[4] ;
int creat_tree(Bnode**root ) /* root是指向指针的指针类型 */
{ /* 本算法递归生成二叉树 */
ElemType ch;
scanf( "%c ",&ch); /* 输入结点,字符型 */
if (ch== ' '){ (*root)-> data=NULL;
return;} /* 生成空二叉树 */
else /* 生成非空二叉树 */
{ (*root)=(Bnode*)malloc(LENG); /* 申请结点空间 */
(*root)-> data=ch; /* 生成根结点 */
creat_tree(&(*root)-> lchild); /* 递归生成左子树 */
creat_tree(&(*root)-> rchild); /* 递归生成右子树 */
}
} /* creat_tree */
void preorder1(Bnode *root)
{ /* 前序遍历二叉树 */
if (root)
{ printf( "%c ",root-> data);
if(root-> lchild)preorder1(root-> lchild);
if(root-> rchild)preorder1(root-> rchild);
}
} /* preorder */
void preorder2(Bnode *root)
{ /* 中序遍历二叉树 */
if (root)
{
if(root-> lchild)preorder2(root-> lchild);
printf( "%c ",root-> data);
if(root-> rchild)preorder2(root-> rchild);
}
} /* preorder */
void preorder3(Bnode *root)
{ /* 后序遍历二叉树 */
if (root)
{
if(root-> lchild)preorder3(root-> lchild);
if(root-> rchild)preorder3(root-> rchild);
printf( "%c ",root-> data);
}
} /* preorder */
void preorder4(Bnode *root)/*中序非递归遍历二叉树*/
{ Bnode *p,*stack[N];
int top=0;
p=root;
do{
while(p!=NULL)
{
top++;
stack[top]=p;
p=p-> lchild;
}
if(top> 0)
{
p=stack[top];/*p所指的 节点为无左子树或其左子树已经遍历过*/
top--;
printf( "%c ",p-> data);
p=p-> rchild;
}
}while(p!=NULL||top!=0);
} /* preorder */
void preorder5(Bnode *root)/*先序非递归遍历二叉树*/
{ Bnode *p,*stack[N];
int top ;
p=root;
if(root!=NULL)
{top=1;
stack[top]=p;
while(top> 0)
{
p=stack[top] ;/*将右小孩放入栈*/
top--;
printf( "%c ",p-> data);
if(p-> rchild!=NULL)
{top++;
stack[top]=p-> rchild;
}
if(p-> lchild!=NULL)
{top++;
stack[top]=p-> lchild;
}
}
} /* preorder */
void degrees(Bnode *root)/*中序非递归遍历二叉树*/
{ Bnode *p,*stack[N];
int top=0,i=0,j=0,k=0;
p=root;
do{
while(p!=NULL)
{
top++;
stack[top]=p;
p=p-> lchild;
}
if(top> 0)
{
p=stack[top];/*p所指的 节点为无左子树或其左子树已经遍历过*/
top--;
if(p-> lchild!=NULL&&p-> rchild!=NULL)k++;
else if(p-> lchild==NULL&&p-> rchild==NULL)i++;
else j++;
printf( "%c ",p-> data);
p=p-> rchild;
}
}while(p!=NULL||top!=0);
printf( "Dgrees=0: %d ",i);
printf( "Dgrees=1: %d ",j);
printf( "Dgrees=2: %d ",k);
} /* preorder */
int nodes(Bnode *root)
{
int num1,num2;
if(root==NULL)return(0);
else
{
num1=nodes(root-> lchild);
num2=nodes(root-> rchild);
return(num1+num2+1);/*加1是因为要算上根节点*/
}
}
int nodeO(Bnode *root)
{
int num1,num2;
if(root==NULL)return(0);
else
{
num1=nodeO(root-> lchild);
num2=nodeO(root-> rchild);
if(root-> lchild==NULL&&root-> rchild==NULL)
return(num1+num2+1);/*加1是因为要算上根节点*/
else return(num1+num2);
}
}
int node1(Bnode *root)
{
int num1,num2;
if(root==NULL)return(0);
else if( (root-> lchild!=NULL&&root-> rchild==NULL) ||(root-> lchild==NULL&&root-> rchild!=NULL))
return(1);
else
{
num1=node1(root-> lchild);
num2=node1(root-> rchild);
return(num1+num2+1 );/*加1是因为要算上根节点*/
}
}
int node2(Bnode *root)
{
int num1,num2;
if(root==NULL)return(0);
else
{
num1=node2(root-> lchild);
num2=node2(root-> rchild);
if(root-> lchild!=NULL&&root-> rchild!=NULL)
return(num1+num2+1);/*加1是因为要算上根节点*/
else return(num1+num2);
}
}
void main(void) /*主函数*/
{ int j ;
char CH;
Bnode *root; /* root是指向根结点的指针变量 */
root=(Bnode *)malloc(sizeof(Bnode ));
do{
printf( "\n1:Create Tree: ");
printf( "\n2:Travel Tree:(DLR) ");
printf( "\n3:Travel Tree:(LDR) ");
printf( "\n4:Travel Tree:(LRD) ");
printf( "\n5:Travel Tree:(LDR)(FeiDiGui): ");
printf( "\n6:Travel Tree:(DLR)(FeiDiGui): ");
printf( "\n7:Degrees of Tree:(DiGui); ");
printf( "\n8:Degrees of Tree:(FeiDiGui); ");
printf( "\nChoose : ");
scanf( "%d ",&j);
switch(j){
case 1:creat_tree(&root);
break;/* 取根指针变量的地址,生成二叉树 */
case 2:preorder1(root); break; /* 前序遍历二叉树 */
case 3:preorder2(root); break; /* 中序遍历二叉树 */
case 4:preorder3(root); break; /* 后序遍历二叉树 */
case 5:preorder4(root); break; /* 非递归中序遍历二叉树 */
case 6:preorder5(root); break; /* 非递归先序遍历二叉树 */
case 7:node[3] =nodes(root);
printf( "SIZE OF TREE=%d ",node[3] ) ; /* 递归算法求节点总数*/
node[0] =nodeO(root);
printf( "Degree=0:%d ",node[0] ) ;
node[1] =node1(root);
printf( "Degree=1:%d ",node[1] ) ;
node[2] =node2(root);
printf( "Degree=2:%d ",node[2] ) ;break;
case 8: degrees(root); break;
default:printf( "Choose from 1,2,3,4...8 ");break;
}
printf( "\nCONTINUE?(Y/N) ");
while(isspace(CH=getchar()));
}while(CH!= 'N '||CH!= 'n ');
printf( "\nbyebye! ");
}
此程序在编译运行时发现有两处错误：
错误 noname.c 101: 表达式语法错在 preorder5 函数中
错误 noname.c 223: 复合指令缺少 }在 preorder5 函数中
请各位高手解释一下程序错误的原因，和解决方法 谢谢！！！
[解决办法]
mark
[解决办法]
void preorder5(Bnode *root)/*先序非递归遍历二叉树*/
{ Bnode *p,*stack[N];//1号“{”
int top ;
p=root;
if(root!=NULL)
{top=1; //2号“{ ”
stack[top]=p;
while(top> 0)
{ //3号“{”
p=stack[top] ;/*将右小孩放入栈*/
top--;
printf( "%c ",p-> data);
if(p-> rchild!=NULL)
{top++; //4号“{ ”
stack[top]=p-> rchild;
} //与4号“{”对应
if(p-> lchild!=NULL)
{top++; //5号“{”
stack[top]=p-> lchild;
} //与5号“{”对应
}//与3号“{”对应
}//与2号“{ ”对应 /* preorder */
显然，不是你多写了一个“{”，就是你少写了一个“}”
重新检查你写的程序
[解决办法]
mark
[解决办法]
mark
