欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数据结构 统计二叉树中度为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 指令