统计利用先序遍历创建的二叉树的度为2的结点个数 swustoj

84 阅读 0 评论 56 点赞

我是靠谱客的博主儒雅芹菜，最近开发中收集的这篇文章主要介绍统计利用先序遍历创建的二叉树的度为2的结点个数 swustoj，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

统计利用先序遍历创建的二叉树的度为2的结点个数

1000(ms)

10000(kb)

2468 / 4526

利用先序递归遍历算法创建二叉树并计算该二叉树度为2结点的个数。先序递归遍历建立二叉树的方法为：按照先序递归遍历的思想将对二叉树结点的抽象访问具体化为根据接收的数据决定是否产生该结点从而实现创建该二叉树的二叉链表存储结构。约定二叉树结点数据为单个大写英文字符。当接收的数据是字符"#"时表示该结点不需要创建，否则创建该结点。最后再统计创建完成的二叉树度为2的结点个数。需要注意输入数据序列中的"#"字符和非"#"字符的序列及个数关系，这会最终决定创建的二叉树的形态。

输入

接受键盘输入的由大写英文字符和"#"字符构成的一个字符串（用于创建对应的二叉树）。

输出

输出该用例对应的二叉树度为2的结点个数。

样例输入

#
A##
ABC####
AB##C##
ABCD###EF##G##H##
A##B##
#A

样例输出

0
0
0
1
3
0
0

#include<iostream>
#include<stdlib.h>
using namespace std;
typedef struct node
{
char data;
struct node *l,*r;
}Tree;
int obj=0;//计数
void init(Tree *&l)
{
char ch;
cin>>ch;
if(ch=='#') l=NULL;
else
{
l=(Tree *)malloc(sizeof(Tree));
l->data=ch;
init(l->l);
init(l->r);
}
}
void count(Tree *&l)
{
if(l!=NULL)
{
if(l->l!=NULL&&l->r!=NULL) obj++;//满足条件就加1；
if(l->l!=NULL) count(l->l);
if(l->r!=NULL) count(l->r);
}
}
int main()
{
Tree *l;
init(l);
count(l);
cout<<obj;
return 0;
}