9도 OJ - 1078 - 두 갈래 나무 두루
4671 단어 두루 다니다두 갈래 나무중서 역행차례차례 두루 다니다
제목 설명
두 갈래 나무의 전순, 중순, 후순 반복의 정의: 전순 반복: 모든 하위 나무에 대해 먼저 접근한 다음에 왼쪽 하위 나무를 반복한 다음에 오른쪽 하위 나무를 반복한다.중서 반복: 어떤 하위 나무에 대해 왼쪽 하위 나무를 먼저 훑어본 다음에 뿌리를 방문하고 마지막으로 오른쪽 하위 나무를 훑어본다.뒷차례 훑어보기: 어떤 하위 나무에 대해 먼저 왼쪽 하위 나무를 훑어본 다음에 오른쪽 하위 나무를 훑어보고 마지막에 뿌리를 방문한다.두 갈래 나무의 전차적 역류와 중차적 역류를 정하고 후차적 역류를 구한다.
입력
두 문자열의 길이는 n이 26보다 작다.첫 번째 행위는 앞뒤로, 두 번째 행위는 앞뒤로.두 갈래 나무의 결점 이름은 대문자로 A, B, C...최대 26개의 결점.
출력
샘플을 입력하면 여러 그룹이 있을 수 있습니다. 각 그룹의 테스트 샘플에 대해 한 줄을 출력하고 뒷순서로 흐르는 문자열을 출력합니다.
샘플 입력
ABC BAC FDXEAG XDEFAG
샘플 출력
BCA XEDGAF
출처
2006년 청화대학 컴퓨터 연구 생기시험 진제
순서대로 훑어보기:
중역:
다음 순서를 반복합니다.
먼저 훑어보는 첫 번째 노드는 반드시 뿌리이기 때문에 먼저 훑어보는 것부터 시작하여 귀착에 따라 먼저 왼쪽 나무를 훑어보고 오른쪽 나무를 훑어본다
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 30;
char preOrder[MAXN]; //
char inOrder[MAXN]; //
char ans[MAXN];
int cnt;
//// root
int GetPreOrderLoc(char root){
int len = strlen(preOrder);
for(int i = 0; i < len; i++){
if(preOrder[i] == root){
return i;
}
}
}
// root
int GetInOrderLoc(char root){
int len = strlen(inOrder);
for(int i = 0; i < len; i++){
if(inOrder[i] == root){
return i;
}
}
}
// preOrder[l...r]
//root ，l r
void dfs(char root, int l, int r){
if(l <= r){
int p1 = GetPreOrderLoc(root); //root
int p2 = GetInOrderLoc(root); //root
//
dfs(preOrder[p1+1], l, p2-1);
//
dfs(preOrder[p1+p2-l+1], p2+1, r);
ans[cnt++] = root;
}
}
int main()
{
while(scanf("%s %s", preOrder, inOrder)!=EOF){
cnt = 0;
dfs(preOrder[0], 0, strlen(preOrder)-1);
for(int i = 0; i < cnt; i++){
cout << ans[i];
}
cout << endl;
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Java Set 컬렉션의 반복 및 구현 클래스 비교Java Set 컬렉션의 반복 및 구현 클래스 비교 Java의 Set 컬렉션은 중복된 요소를 포함하지 않는 Collection입니다. 주의: 여기 Set 집합에 넣는 것은 String 형식입니다. 만약에 우리가 정의...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
