이 진 트 리 건설 에 관 한 약간의 문제

문제 1. 이 진 트 리 는 전형 적 인 문제 가 있 습 니 다. 중간 순서 와 앞 순 서 를 옮 겨 다 니 는 순 서 를 제시 하면 이 진 트 리 수 를 어떻게 만 듭 니까?(실제 후속 스 트 리밍 은 이전 스 트 리밍 과 같 습 니 다. 이전 스 트 리밍 을 교체 할 수 있 습 니 다)
그러면 우 리 는 앞의 순서 가 서열 을 옮 겨 다 니 는 첫 번 째 노드 가 바로 root 라 는 것 을 쉽게 알 수 있 습 니 다. 그러면 우 리 는 중간 순서 에서 이 점 을 찾 을 수 있 습 니 다. 그러면 이 점 의 왼쪽 은 왼쪽 서브 트 리 의 중간 순서 로 서열 을 옮 겨 다 니 고 오른쪽 도 마찬가지 입 니 다. 그러면 앞 순 서 는 첫 번 째 점 을 제거 한 후에 왼쪽 서브 트 리 의 중간 순서 와 똑 같은 수량 으로 대응 하여 하나의 규모 축 소 를 구성 합 니 다.그러나 문제 가 일치 하 는 서브 문제 이기 때문에 이것 은 재 귀적 으로 해결 할 수 있 는 것 이 분명 하 다. 재 귀적 인 관건 은 바로 중 서 를 옮 겨 다 니 는 서열 과 전 서 를 옮 겨 다 니 는 서열 이 대응 해 야 한 다 는 것 이다.이것 은 아주 쉽게 이해 할 수 있다.코드

#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

struct node
{
    int data;
    node* l;
    node* r;
};
int pre[1000];
int in[1000];
node *root;
node* findd(int l,int r,int L,int R)//l r     ，L R     
{
    if(l>r)
        return NULL;//    ，  
    int p;
    for(p=l;pif(in[p]==pre[L])//      
            break;
    node* now=new node;
    now->l=findd(l,p-1,L+1,L+(p-l));
    now->r=findd(p+1,r,L+(p-l)+1,R);
    now->data=in[p];
    return now;
}
int main()
{

    int n;//    
    scanf("%d",&n);
    for(int i=0;iscanf("%d",pre+i);
    for(int i=0;iscanf("%d",in+i);
    root=findd(0,n-1,0,n-1);
    return 0;
}

문제 2. 어떻게 중간 순 서 를 통 해 두 갈래 나 무 를 옮 겨 다 니 며 재건 합 니까?이 문 제 는 인공 적 으로 조작 하면 알 수 있 을 것 입 니 다. 코드 는 어떻게 씁 니까?바로 우리 가 점 이 좌우 의 바이트 가 있 는 지 어떻게 압 니까?만약 에 층 차 를 옮 겨 다 니 면서 시작 하면 첫 번 째 가 바로 뿌리 노드 (root) 라 는 것 을 알 수 있 습 니 다. 그러면 저 는 중간 순서 에서 이 노드 를 찾 습 니 다. 만약 에 이 점 이 좌우 양쪽 에 약간 있다 면 우 리 는 루트 좌우 양쪽 에 모두 아이 가 있다 는 것 을 알 수 있 습 니 다. 그래서 우 리 는 뿌리 노드 를 계속 찾 은 다음 에 좌우 아이 가 있 는 지, 어디서 아 이 를 찾 는 지 판단 해 야 합 니 다.우리 가 구간 을 제공 해 야 한다 면 뿌리 노드 의 찾기 는 광범 위 한 검색 형식 에 따라 이 문 제 는 bfs 로 해결 해 야 한다.코드

#include
#include
#include
#include
#include
#include
#include
#include
#define INF 0x3f3f3f3f
#define mod 1000000007
using namespace std;

struct node
{
    int data;
    node* l;
    node* r;
};
int layer[1000];
int in[1000];
node *root;
struct node2
{
    int l,r;
    node* now;
};//        
int main()
{
    int n;//    
    scanf("%d",&n);
    for(int i=0;iscanf("%d",layer+i);
    for(int i=0;iscanf("%d",in+i);
    queue que;
    root=new node;
    root->data=layer[0];
    root->l=root->r=NULL;
    node2 p;
    p.l=0;
    p.r=n-1;
    p.now=root;
    que.push(p);
    int countt=1;
    while(!que.empty())
    {
        node2 temp=que.front();
        que.pop();
        int mid;
        for(mid=temp.l;mid<=temp.r;mid++)
            if(in[mid]==temp.now->data)
                break;
        if(temp.l//          
        {
            node *left=new node;
            left->data=layer[countt++];
            left->l=left->r=NULL;
            node2 temp1;
            temp1.l=temp.l;
            temp1.r=mid-1;
            temp1.now=left;
            que.push(temp1);
        }
        if(mid//          
        {
            node *right=new node;
            right->data=layer[countt++];
            right->l=right->r=NULL;
            node2 temp1;
            temp1.l=mid+1;
            temp1.r=temp.r;
            temp1.now=right;
            que.push(temp1);
        }
    }
    return 0;
}

사고: 앞의 순서 든 후속 이 든 층 서 든 본질 적 으로 뿌리 노드 (상대 적 으로) 를 제공 하 는 것 임 을 알 수 있다. 어쨌든 우 리 는 중간 순서 로 옮 겨 다 니 며 좌우 자 수 를 얻 어야 한다.이상 의 문 제 는 구체 적 인 문제 가 없고 쓴 코드 는 모두 개인 적 인 이해 이 며 더욱 최 적 화 된 표기 법 이 있 으 면 지적 해 주 십시오.재 미 있 는 질문 이 있 으 면 다음 에 업데이트 하 겠 습 니 다 |...ω･｀)