두 갈래 나무 예제
8168 단어 데이터 구조와 알고리즘
제목: 이미 알고 있는 두 갈래 나무의 앞차례와 중간차례, 뒷차례를 구한다.
사고방식: 선서 서열의 첫 번째 숫자를 하나의 뿌리로 삼아 중서 서열에서 이 숫자를 찾으면 중서 서열에서 뿌리 앞의 서열은 뿌리의 왼쪽 트리이고 뒤의 서열은 오른쪽 트리이다.만약에 중서력 횟수 중 i의 첫 번째 점이 루트 노드라면 두 구역, 0~i와 i~n-1로 구분한다.
#include
#include
using namespace std;
int a[1005];
int k;
void postorder(int *p, int *q, int len){
if(len == 0)// 0,
return;
int t = 0;
int s = *p;
for(; t < len; t ++){
if(q[t] == *p){//
break;
}
}
postorder(p+1, q, t);//
postorder(p+t+1, q+t+1, len-t-1);//
a[k++] = s;
}
int main(){
int n, i, j;
int p[1005], q[1005];
while(cin>>n){
for(i = 0; i < n; i ++){
cin>>p[i];
}
for(j = 0; j < n; j ++){
cin>>q[j];
}
k = 0;
postorder(p, q, n);
for(i = 0; i < k-1; i ++){
cout<' ';
}
cout<1]<<endl;
}
return 0;
}
2. 확장: 이미 알고 있는 중서, 후서, 전서를 구한다.
#include"iostream"
using namespace std;
int pre[30];
int in[30];
int post[30];
int indexOfRootIn(int start,int stop,int root){
for(int j=start;j<=stop;j++){
if(in[j]==root){
return j;
}
}
return -1;
}
/*void postOrder(int pre_start,int pre_end,int in_start,int in_end,int length){
if(length==0)
return;
if(length==1){
cout<*/
void preOrder(int post_start,int post_end,int in_start,int in_end,int length){
if(length==0)
return;
if(length==1){
cout<<in[in_start]<<endl;
return;
}
int root = post[post_end];
int index = indexOfRootIn(in_start,in_end,root);
int len1= index-in_start;
int len2= in_end-index;
cout<" "<<endl;
preOrder(post_start,post_start+index-1,in_start,index-1,len1);
preOrder(post_start+index,post_end-1,index+1,in_end,len2);
}
int main(){
int N;
cin>>N;
for(int i=0;i){
cin>>post[i];
}
for(int i=0;i){
cin>>in[i];
}
preOrder(0,N-1,0,N-1,N);
return 0;
}
다음으로 전송:https://www.cnblogs.com/cccyx/p/11537623.html
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
두 갈래 나무의 깊이가 두루 다니다텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.