[이차 트리] 선순과 중순에 따라 출력 후순을 반복합니다.
1364 단어 두 갈래 나무
제목 설명 입력 첫 번째 줄: 두 갈래 나무의 앞 순서 반복 순서
두 번째 줄: 중간 순서 반복 순서
두 갈래 트리 출력 순서
샘플 입력
ABCDEFGH CBEDAGHF
샘플 출력 CEDBHGFA
분석:
이 문제의 가장 핵심적인 문제는 어떻게 트리(또는 시뮬레이션 트리)를 만드는가이다. 이것은 분치(귀속)와 유사하다. 우리는 선서열을 a로 하고 중서열을 b로 하고 전역 변수 s로 a에서 몇 번째 수를 찾았는지 나타낸다.
먼저 예시를 보면 a에서 A가 뿌리 노드라는 것을 알 수 있다. 그리고 중서 역력의 성질에 따라 b에서 A의 왼쪽 아들은 A의 왼쪽에 있고 오른쪽 아들은 A의 오른쪽에 있다.
다시 순서대로 훑어보는 성질에서 B는 A의 왼쪽 아들이다. 이때 s=1, 다시 B의 좌우 아들을 차례로 수색한다. B가 수색한 후에 s=5(F), 그러면 A의 오른쪽 아들은 F이다. 다시 F의 좌우 아들을 수색하면 전체 프로그램이 귀속될 수 있다.
파라미터를 가지고 있을 때 현재 결점의 좌우 아들을 어느 범위에서 찾아야 하는지 규정해야 한다. 그렇지 않으면 착란될 것이다
(작성) 코드는 다음과 같습니다.
#include
#include
char a[1000],b[1000];
int n,s=1;
struct node
{
int l,r;
}t[260];
void dfs(int q,int w,int o)//q,w ，o
{
if(s==n+1) return;
for(int i=q;i<=w;i++)
if(b[i]==a[s])
{
if(!t[o].l) t[o].l=b[i];
else t[o].r=b[i];
s++;
dfs(q,i-1,b[i]);//
dfs(i+1,w,b[i]);//
}
}
void hdfs(int a)
{
if(a)
{
hdfs(t[a].l);
hdfs(t[a].r);
printf("%c",a);
}
}
int main()
{
//freopen("build-tree.in","r",stdin);
//freopen("build-tree.out","w",stdout);
scanf("%s%s",a+1,b+1);
n=strlen(a+1);
dfs(1,n,0);
hdfs(a[1]);
} 트리를 만들 필요가 없는 프로그램은 사실 찾으면서 출력하기만 하면 코드를 주지 않는다
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
java 데이터 구조 2차원 트리의 실현 코드일.두 갈래 트리 인터페이스 2 노드 클래스 3. 두 갈래 나무 구현 이 글을 통해 여러분께 도움이 되었으면 좋겠습니다. 본 사이트에 대한 지지에 감사드립니다!...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
