선순 중순 2차원 트리의 귀속 알고리즘 구축

2132 단어 두 갈래 나무
그 선행 서열의 첫 번째 요소는 루트 노드이고, 그 다음은 왼쪽 트리의 선행 서열이며, 그 다음은 오른쪽 트리의 선행 서열이기 때문에 루트 노드는 선행 서열에서 분리될 수 있다.중차 서열에서 확정된 루트 노드를 찾습니다. 중차 서열 특성에 따라 수건 서열에서 루트 노드 앞의 서열은 왼쪽 트리의 중차 서열이고 루트 노드 뒤의 서열은 오른쪽 트리의 중차 서열입니다.좌우 트리의 중차 서열 길이로 이 두 갈래 트리의 선차 서열에서 좌우 트리의 선차 서열의 경계점을 찾아 두 갈래 트리의 좌우 트리의 선차 서열을 얻을 수 있다.귀속 실현: 귀속 함수 입력: 두 갈래 트리의 선순 서열과 중순 서열;-, 세워진 두 갈래 나무의 뿌리 노드를 되돌려줍니다.알고리즘 사상: 1) 두 갈래 나무가 비어 있으면 되돌아온다.2) 비어 있지 않으면 첫 번째 원소를 순서대로 취하여 루트 노드를 만듭니다.3) 중간 시퀀스에서 루트 노드를 찾아 좌우 하위 트리의 우선 시퀀스와 중간 시퀀스를 확인합니다.4) 자신을 차례로 호출하여 왼쪽 나무를 짓는다.5) 자신을 차례로 호출하여 오른쪽 나무를 만든다.
void createBiTree(linkshu &root, const char*  pre , const char* in,int len)
{
int k;// 
const char* temp;
if(len<=0)
{
root=NULL;
return;
}
root=(linkshu)malloc(sizeof(struct shu));
root->data=*pre;
for(temp=in;temp<in+len;temp++)
{
if(*temp==*pre)
break;
}


k=temp-in;
createBiTree(root->lchild,pre+1,in,k);
createBiTree(root->rchild,pre+1+k,temp+1,len-1-k);


 
}

검지offer-24: 두 갈래 나무 중 어느 값의 경로
두 갈래 나무에서 두 개의 결점을 찾는 최근 공공 조상의 결점

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage