以二叉链表为结构体,写出二叉树结点总数及叶子总数的算法?我需要完整的程序代码

以二叉链表为结构体,写出二叉树结点总数及叶子总数的算法?我需要完整的程序代码

分太少啊
#include <stdlib.h>
#include <stdio.h>
#define MAXL 100
typedef char Elemtype ;

typedef struct
{
Elemtype e;
} Elem;
typedef struct BTree
{
Elem data;
struct BTree * lchild,*rchild;
} BITnode,*BTree;

void Createtree(BTree *T) //创建二叉树
{
Elemtype a;
scanf("%c",&a);
if (a == '@' )
{
*T = NULL;
}
else
{
*T = (BTree)malloc(sizeof(BITnode));
if(!T)
{
exit(1);
}
(*T)->data.e = a;
Createtree(&(*T)->lchild);
Createtree(&(*T)->rchild);
}
return ;
}
//前序遍7a686964616fe78988e69d8331333264663637历
void PreTravel(BTree T)
{
if(T)
{
printf(" %c",T->data.e);
PreTravel(T->lchild);
PreTravel(T->rchild);
}
}
//中序遍历
void MidTravel(BTree T)
{
if(T)
{
MidTravel(T->lchild);
printf(" %c",T->data.e);
MidTravel(T->rchild);

}
}
//后序遍历
void PostTravel(BTree T)
{
if(T)
{
PostTravel(T->lchild);
PostTravel(T->rchild);
printf(" %c",T->data.e);
}
}
//递归计算叶子数
int Count_leaf(BTree T)
{
if (T == NULL)
{
return 0;
}
else if (T->lchild == NULL && T->rchild == NULL)
{
return 1;
}
else
{
return Count_leaf(T->lchild) + Count_leaf(T->rchild);
}
}
///非递归计算叶子结点个数
///用栈存放节点 Not_Leaf_Count计算叶子结点个数
typedef struct
{
int top;
BTree MAXSIZE[MAXL];
} *Stack, Le_Node;

int Not_Count_Leaf(BTree T)
{
int Not_Leaf_Count = 0;
Stack s;
s = (Stack )malloc(sizeof(Le_Node));
s ->top =0;
while (T != NULL || s->top != 0)
{
if (T != NULL)
{

s->MAXSIZE[s->top] = T;
s->top ++;
T = T->lchild;
}
else
{ s->top --;
T = s->MAXSIZE[s->top];

if (T->lchild == NULL && T->rchild == NULL)
{
Not_Leaf_Count++;
}
T = T->rchild;
}
}
return Not_Leaf_Count;
}

//计算二叉树的高度
int Height_Bitree(BTree T)
{
int h1,h2;
if (T != NULL)
{
h1 = Height_Bitree(T->lchild);
h2 = Height_Bitree(T->rchild);
if (h1 > h2)
{
return h1+1;
}
else
{
return h2+1;
}
}
else
return 0;
}
//非递归计算二叉树高度
int Not_Height_Bitree(BTree T)
{
BTree Que[MAXL];
int hp = 0,dp = 0,rear = 0,tp = 1,lc = 1;
BTree p;
if (T != NULL) //根节点入队
{
Que[rear++] = T;

}
while (rear != 0)
{
p = Que[--rear];//队头元素出队
hp ++; //为已访问的节点数
if (p->lchild != NULL)
{
Que[rear++] = p->lchild;
tp ++; //记录历史入队的节点数
}
if (p->rchild != NULL)
{
Que[rear++] = p->rchild;
tp ++;
}
if(hp == lc) //当hp = lc时，表明本层节点均已访问完
{
dp ++;
lc = tp;
}
}
return dp;
}
//按层次遍历
void Level_Travel(BTree T)
{
BTree Que[MAXL];
int front = 0,rear = 0;
BTree p;
if (T != NULL) //根节点入队
{
Que[rear] = T;
rear = (rear+1)%MAXL;
}
while (front != rear)
{
p = Que[front];//队头元素出队
front = (front +1)% MAXL;
printf(" %c",p->data.e);
if (p->lchild != NULL)
{
Que[rear] = p->lchild;
rear = (rear + 1)%MAXL;
}
if (p->rchild != NULL)
{
Que[rear] = p->rchild;
rear = (rear+1)%MAXL;
}
}
return ;
}

//非递归先序遍历
void NPreTravel(BTree T)
{
BTree stack[MAXL];
BTree p;
int top ;
if (T != NULL)
{
top = 0;
p = T;
while (p != NULL || top > 0)
{
while (p != NULL)
{
printf(" %c",p->data.e);
stack[top] = p;
top ++;
p = p->lchild;
}
if (top > 0)
{
top--;
p = stack[top];
p = p->rchild;
}
}
}

}
//非递归中序遍历
void NMidTravel(BTree T)
{
BTree stack[MAXL];
BTree p;
int top;
if (T != NULL)
{
top = 0;
p = T;
while (p != NULL || top > 0)
{
while (p != NULL)
{
stack[top] = p;
top ++;
p = p->lchild;
}
if (top > 0)
{
top--;
p = stack[top];
printf(" %c",p->data.e);
p = p->rchild;
}
}
}
}
//非递归后续遍历
typedef struct
{
BTree ptr;
int tag;
} stacknode;
void NPostTravel(BTree T)
{
stacknode s[MAXL];
stacknode x;
BTree p = T;
int top;
if (T != NULL)
{
top = 0;
p = T;
do
{
while (p != NULL) //遍历左子树
{
s[top].ptr = p;
s[top].tag = 1; //标记为左子树
top ++;
p = p->lchild;

}
while (top > 0 && s[top-1].tag == 2)
{
x = s[--top];
p = x.ptr;
printf(" %c",p->data.e); //tag 为2 表示右子数访问完毕，故访问根节点
}
if (top > 0)
{
s[top-1].tag = 2; //遍历右子树
p = s[top-1].ptr->rchild;
}
}
while (top > 0);
}
}
void menu()
{
printf("----------------------------------------------\n\n");
printf("0:退出\n");
printf("1:创建二叉树\n");
printf("2:递归前序遍历\n3:非递归前序遍历\n");
printf("4:递归中序遍历\n5:非递归中序遍历\n");
printf("6:递归后续遍历\n7:非递归后续遍历\n");
printf("8:递归计算叶子数\n9:非递归计算叶子数\n");
printf("10:递归计算高度 \n11:非递归计算高度\n");
printf("12:按层次遍历\n");
printf("-----------------------------------------------\n");
return ;
}

int main()
{
BTree T = NULL;
int select ;
menu();

do
{

printf("输入您的选择：");
scanf("%d",&select);
switch (select)
{
case 0:
{
printf("退出\n");
break ;
}
case 1:
{
printf("创建二叉树\n");
printf("输入数据，以@结束\n");
Createtree(&T);
break;
}

case 2:
{
printf("递归前序遍历\n");
PreTravel(T);
break;
}
case 3:
{
printf("非递归前序遍历\n");
NPreTravel(T);
break;
}
case 4:
{
printf("递归中序遍历\n");
MidTravel(T);
break;
}
case 5:
{
printf("非递归中序遍历\n");
NMidTravel(T);
break;
}
case 6:
{
printf("递归后序遍历\n");
PostTravel(T);
break;
}
case 7:
{
printf("非递归后序遍历\n");
NPostTravel(T);
break ;
}
case 8:
{
printf("递归计算叶子数为：%d\n",Count_leaf(T));
break ;
}
case 9:
{
printf("非递归计算叶子数为：%d\n",Not_Count_Leaf(T));
break;
}
case 10:
{
printf("递归计算高度\n");
printf("高度为：%d\n",Height_Bitree(T));

break;
}
case 11:
{
printf("非递归计算高度\n");
printf("高度为：%d\n",Not_Height_Bitree(T));
break;
}
case 12:
{
printf("按层次遍历二叉树\n");
Level_Travel(T);
break;
}
default :
;

}
}
while (select);
printf("-------------欢迎-----------\n");
system("pause");
return 0;
}

5

叶子结点总数=二度二叉树的个数＋1

发牛财

ej=fgrg d=ooo

2010-11-27 12:58 最佳答案 同学，你们老师和我们老师留的作业是一模一样的阿，我有现成的做好了的程序，调试成功。这个程序的难点就在于这种很别扭的输入形式，所以我为它设计了一个结构体形式存放输入内容e68a84e8a2ade799bee5baa631333264663637，再将它转化成了线性结构。 #include <iostream.h> #include <stdlib.h> struct inform { char data; int l; int r; int signl; int signr; }; struct leafnode { char leaf; leafnode* lchild; leafnode* rchild; }; void print(inform* ps, int n); void judge ( inform* ps ); leafnode* creatree(); void preorder (leafnode* T); void inorder (leafnode* T); void postorder (leafnode* T); char a[100]; int k=1; int s=0; inform *p; void main() { int n; cout<<"请输入二叉树内容：第一行为节点总数n ，后面的n行是节点的具体形式："<<endl; cout<<"n= "; cin>>n; p=(inform* )malloc( n*sizeof(inform) ); inform *p1; p1=p; for(int i=0; i<n; i++) { cin>>(p+i)->data>>(p+i)->l>>(p+i)->r; if((p+i)->l != -1) (p+i)->signl=1; else (p+i)->signl= 0; if((p+i)->r !=-1) (p+i)->signr=1; else (p+i)->signr= 0; } a[0]= p->data; judge ( p1 ); cout<<endl<<"输出转换的线性字符串： "<<endl; cout<<a<<endl<<endl; leafnode* T; T= creatree(); cout<<"先序遍历二叉树： "<<endl; preorder( T ); cout<<endl<<"中序遍历二叉树： "<<endl; inorder ( T ); cout<<endl<<"后序遍历二叉树： "<<endl; postorder( T ); cout<<endl<<endl; } void judge( inform* ps ) { inform* b; if (ps->signl==0) { a[k]='@'; k++; } else { b = p+(ps->l); a[k] = b->data; k++; judge(b); } if ((ps->signr) == 0) { a[k]='@'; k++; } else { b = p+(ps->r ); a[k] = b->data; k++; judge(b); } } leafnode* creatree() { char ch; leafnode *t; ch= a[s]; s++; if(ch=='@') { t=NULL; } else { t=(leafnode* )malloc(sizeof(leafnode)); t->leaf=ch; t->lchild=creatree(); t->rchild=creatree(); } return t; } void preorder (leafnode* T) { if(T) { cout<<T->leaf; preorder(T->lchild); preorder(T->rchild); } } void inorder (leafnode* T) { if(T) { inorder(T->lchild); cout<<T->leaf; inorder(T->rchild); } } void postorder (leafnode* T) { if(T) { postorder(T->lchild); postorder(T->rchild); cout<<T->leaf; }