swust oj 982
2024-09-23 19:14:39
输出利用二叉树存储的普通树的度
1000(ms)
10000(kb)
2619 / 5991
普通树可转换成相应的二叉树（该二叉树的根结点一定缺少右儿子），反之亦然。故而可以根据相应的转换方法去统计某一二叉树对应的普通树的度。普通树的度为其结点儿子数的最大值。相应的二叉树可利用二叉树的先序递归遍历算法创建。先序递归遍历建立二叉树的方法为：按照先序递归遍历的思想将对二叉树结点的抽象访问具体化为根据接收的数据决定是否产生该结点从而实现创建该二叉树的二叉链表存储结构。约定二叉树结点数据为单个大写英文字符。当接收的数据是字符"#"时表示该结点不需要创建，否则创建该结点。最后再统计该二叉树对应的森林中树的棵数。需要注意输入数据序列中的"#"字符的序列及个数关系，这会最终决定创建的二叉树的形态（序列里面允许无效字符但需要正确处理）。
输入
输入为接受键盘输入的由大写英文字符和"#"字符构成的一个字符串（用于创建对应的二叉树）。
输出
若表示的二叉树对应普通树，则该普通树的度；否则输出ERROR。
样例输入
AB#CD##E###
ABC####
AB##C##
ABCD###EF##G###
A##B##
样例输出
3
1
ERROR
3
1
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cstdio>
typedef char Datetype;
using namespace std;
int x; typedef struct link{
Datetype date;
struct link *lchild;
struct link *rchild;
}tree; typedef struct queue{
tree *data;
struct queue *next;
}que; typedef struct {
que *front;
que *rear;
}lin; void Initqueue(lin *&L)
{
L=(lin *)malloc(sizeof(lin));
L->front=L->rear=NULL;
} void destroyed(lin *&L)
{
que *p=NULL,*r=NULL;
p=L->front;
while(p!=NULL)
{
r=p;
p=p->next;
free(r);
}
free(L);
} bool pop(lin *&L, tree *&e)
{
que *p;
if(L->rear==NULL)
return false;
p=L->front;
if(L->rear==L->front)
L->front=L->rear=NULL;
else
L->front=p->next;
e=p->data;
free(p);
return true;
} int empty(lin *&L)
{
return (L->rear==NULL);
} void push(lin *&L,tree *e)
{
que *p;
p = (que *)malloc(sizeof(que));
p->data=e;
p->next=NULL;
if(L->rear==NULL)
{
L->front=p;
L->rear=p;
}
else
{
L->rear->next=p;
L->rear=p;
}
} void creattree(tree *&L)
{
char c;
cin>>c;
if(c=='#')
L=NULL;
else
{
L = (tree *)malloc(sizeof(tree)) ;
L->date=c;
creattree(L->lchild);
creattree(L->rchild);
}
} void find(tree *L)
{
if(L!=NULL)
{
x++;
find(L->rchild);
}
} void destroytree(tree *&L)
{
if(L!=NULL)
{
destroytree(L->lchild);
destroytree(L->rchild);
free(L);
}
} int deep(tree *L)
{
int ldep,rdep,max;
if(L!=NULL)
{
ldep=deep(L->lchild);
rdep=deep(L->rchild);
max=ldep>rdep?ldep+:rdep+;
return max;
}
else
return ;
} void finddegree(tree *&L, int n)
{
if(L!=NULL)
{
if(x<n)
x=n;
finddegree(L->lchild,n);
finddegree(L->rchild,n+);
} } void run(tree *L)
{
tree *p=L;
lin *qu;
Initqueue(qu);
if(L!=NULL)
push(qu,p);
while(!empty(qu))
{
pop(qu,p);
cout<<p->date;
if(p->lchild!=NULL)
push(qu,p->lchild);
if(p->rchild!=NULL)
push(qu,p->rchild);
}
destroyed(qu);
} int main()
{
tree *L = NULL;
x=;
creattree(L);
if(L->rchild!=NULL)
cout<<"ERROR";
else
{
finddegree(L,);
cout<<x;
}
destroytree(L);
return ;
}
最新文章
- Ruby--学习记录（实时更新）
- xsocks 64位平台下编译问题小记
- 利用SQLiteOpenHelper来管理SQLite数据库 （转）
- 在SQL Server实现最短路径的搜索
- [北京周六见]10 家创业公司联合招 Partner-均融资 1 到 3 轮-薪酬股权可观-本周六举行欢迎来坐坐吃喝谈天 - V2EX
- POJ 2010 Moo University - Financial Aid 优先队列
- 原生AJAX基础讲解及兼容处理
- Asycn/Await 异步编程初窥（二）
- redis的配置详解
- 历史记录 history
- Alpha冲刺Day8
- 如何在Cocos2D游戏中实现A*寻路算法(五)
- IT - 偶像的力量
- 如何将本地的文件上传到你的github仓库中(首次流程)
- Java: String.split(....); 结果很意外
- GDALSetProjection使用的一个注意事项
- Properties 类的使用
- 【Tomcat】Tomcat + Memcached 实现session共享
- 常用chrome插件&&常用FireFox插件
- 怎么解决安装SqlServer2008总是提示Restart computer as failed