sdutoj2804 두 갈래 나무의 깊이를 구하기 (중순 및 후순에 따라 트리를 반복 구하기)
2323 단어 나무와 두 갈래 나무
두 갈래 나무의 깊이를 구하다
Time Limit: 1000MS Memory limit: 65536K
제목 설명
이미 알고 있는 두 갈래 나무의 중차적 역행 서열과 후차적 역행 서열은 두 갈래 나무의 깊이를 구한다.
입력
입력 데이터가 여러 그룹, 입력 T는 T그룹 데이터가 있음을 나타냅니다.각 그룹의 데이터는 길이가 50보다 작은 두 개의 문자열을 포함하는데, 첫 번째 문자열은 두 갈래 나무의 중차적 이동을 나타내고, 두 번째 문자열은 두 갈래 나무의 후차적 이동을 나타낸다.
출력
두 갈래 나무의 깊이를 출력합니다.
예제 입력
2
dbgeafc
dgebfca
lnixu
linux
예제 출력
4
3
힌트
코드 구현:
#include
#include
#include
#include
using namespace std;
struct Tree
{
char data;
Tree *lchild,*rchild;
};
char a[110],b[110];
///
Tree *Creat(int n,char a[],char b[])
{
if(n == 0)
return NULL;
char *p;
Tree *T;
T = new Tree;
T->data = b[n - 1];///
for(p = a; *p != '\0'; p++)///
{
if(*p == b[n - 1])
break;
}
int t = p - a;
T->lchild = Creat(t,a,b);/// ,
T->rchild = Creat(n - t - 1,p + 1,b + t);/// ,
return T;
}
int Depth(Tree *T)
{
int ldepth,rdepth;
if(!T)
return 0;
else
{
ldepth = Depth(T->lchild);
rdepth = Depth(T->rchild);
return ldepth > rdepth ? ldepth+1 : rdepth+1;
}
}
int main()
{
int n;
while(~scanf("%d",&n))
{
while(n--)
{
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
Tree *T;
scanf("%s%s",a,b);
int len = strlen(a);
T = Creat(len,a,b);
printf("%d
",Depth(T));
}
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
SDUT-2804 데이터 구조 실험의 2차원 트리 8: (중차순 후차순) 2차원 트리의 깊이를 구하기데이터 구조 실험의 두 갈래 나무 8: (중차원 후차원) 두 갈래 나무의 깊이를 구한다 Time Limit: 1000MS Memory Limit: 65536KB Submit Statistic Problem Desc...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.