数据结构 统计二叉树中度为0,1和2的结点个数
程序员文章站
2022-05-16 18:34:47
...
Description
给定先序序列,按照该序列创建对应的二叉树,并输出该二叉树度为0,1和2的结点个数。
Input
一行,二叉树按先序遍历序列,空指针用字符^占位
Output
一行,三个整数分别代表该二叉树度为0,1和2的结点个数
Sample Input
ABD^^^CE^^F^^
Sample Output
3 1 2
递归遍历寻找
理解递归的思想 就很好理解程序了
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct node{
char ch;
struct node *Lchild;
struct node *Rchild;
}BiTNode,*BiTree;
void Q_CreatTree(BiTree *T);
int NodeNumber_1(BiTree T);
int NodeNumber_2(BiTree T);
int NodeNumber_0(BiTree T);
int main(void)
{
BiTree T;
Q_CreatTree(&T);
getchar();
printf("%d ",NodeNumber_0(T));//度为0的节点
printf("%d ",NodeNumber_1(T));//度为1的节点
printf("%d",NodeNumber_2(T));//度为2的节点
}
void Q_CreatTree(BiTree *T)//前序遍历建立二叉树
{
char str;
str=getchar();
if(str=='^')
{
*T=NULL;
}
else
{
(*T)=(BiTree)malloc(sizeof(BiTNode));
(*T)->ch=str;
Q_CreatTree( &( (*T)->Lchild ) );
Q_CreatTree( &( (*T)->Rchild ) );
}
}
int NodeNumber_0(BiTree T)
{
int i=0;
if(T)
{
if(T->Lchild==NULL&&T->Rchild==NULL)
{
i=1;
}
else
{
i=NodeNumber_0( T->Lchild ) + NodeNumber_0( T->Rchild );
}
}
return i;
}
int NodeNumber_1(BiTree T)
{
int i=0;
if(T)
{
if( (T->Lchild==NULL&&T->Rchild!=NULL) ||(T->Lchild!=NULL&&T->Rchild==NULL))
{
i=1+NodeNumber_1(T->Lchild)+NodeNumber_1(T->Rchild);
}
else
{
i=NodeNumber_1(T->Lchild)+NodeNumber_1(T->Rchild);
}
}
return i;
}
int NodeNumber_2(BiTree T)
{
int i=0;
if(T)
{
if((T->Lchild!=NULL)&&(T->Rchild!=NULL))
{
i=1+NodeNumber_2(T->Lchild) + NodeNumber_2(T->Rchild);
}
else
{
i= NodeNumber_2(T->Lchild) + NodeNumber_2(T->Rchild);
}
}
return i;
}
上一篇: vue指令
下一篇: vue03-directives 指令