二叉树采用二叉链表结构表示。设计并实现如下算法：求一棵二叉树的深度和双分支结点的个数。
程序 2007-12-07 23:28 阅读5 评论0 字号： 大大 中中 小小#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define STACK_INIT_SIZE 100
#define STACKING 10
typedef struct Binode{
struct Binode *lchild;
struct Binode *rchild;
char data;
int number;
}Binode,BiTree;
typedef struct QNode
{
Binode data1;
struct QNode *next;
}QNode,*Quen;
typedef struct
{
Quen front;
Quen rear;
}linkQ;
void InitQueue(linkQ *Q)
{
Q->front=Q->rear=(Quen)malloc(sizeof(QNode));
if(!Q->front)exit(0);
Q->front->next=NULL;
}
void DeQuene(linkQ *Q,BiTree *e)
{
Quen p;
if(Q->front==Q->rear)
printf("error\n");
p=Q->front->next;
*e=p->data1;
Q->front->next=p->next;
if(Q->rear==p)Q->rear=Q->front;
free(p);
}
void EnQueue(linkQ *Q,BiTree *e)
{
Quen p;
p=(Quen)malloc(sizeof(QNode));
if(!p)exit(0);
p->data1=*e;
p->next=NULL;
Q->rear->next=p;
Q->rear=p;
}
BiTree *creatBiTree(BiTree *T)
{char ch;
scanf("%c",&ch);
if(ch==' ') T=NULL;
else{
T=(BiTree *)malloc(sizeof(Binode));
T->data=ch;
T->lchild=creatBiTree(T->lchild);
T->rchild=creatBiTree(T->rchild);
}
return T;
}
void visit(BiTree *T)
{printf("%-2c",T->data);}
int depth(BiTree *T)
{int depth1,depth2;
if(!T)return 0;
else
{
depth1=depth(T->lchild);
depth2=depth(T->rchild);
if(depth1>depth2)return depth1+1;
else return depth2+1;
}
}
int Leaf_Count(BiTree *T)
{
if(!T) return 0;
else if(!T->lchild&&!T->rchild) return 1;
else return Leaf_Count(T->lchild)+Leaf_Count(T->rchild);
}
void LayerOrder(BiTree *T)
{ linkQ Q; BiTree p;int i=0;
InitQueue(&Q);
EnQueue(&Q,T);
while(Q.front!=Q.rear)
{
DeQuene(&Q,&p);
if(p.lchild!=NULL&&p.rchild!=NULL){visit(&p);i++;}
if(p.lchild) EnQueue(&Q,p.lchild);
if(p.rchild) EnQueue(&Q,p.rchild);
}
printf("\nthe jiedian zhonshu shi:%d\n",i);
}
BiTree *Create_G(BiTree *T)
{ char c;
BiTree *p,*s[10000];
int b,top=-1;
p=NULL;T=NULL;
c=getchar();
while(c != '#'){
switch(c){
case '(':
top++;
s[top] = p;
b = 1;
break;
case ')':
if(top == -1){
printf("二叉树广义表字符串错误!\n");
exit(1);
}
top--;
break;
case ',':
b = 2;
break;
default:
p =(Binode*)malloc(sizeof(Binode));
p->data = c;
p->lchild = p->rchild = NULL;
if(T == NULL)
{
T = p;
}
else
{
if( b == 1)
{
s[top]->lchild = p;
}
else
{
s[top]->rchild = p;
}
}
}
c=getchar();
}
return T;
}
void main()
{BiTree p,*t;
t=creatBiTree(&p);
printf("the tree's depth is:\n");
printf("%d\n",depth(t));
printf("you liang ge jiedian de jiedian shi:\n");
LayerOrder(t);
printf("%d\n",Leaf_Count(t));
}