1: 구조 체인식 두 갈래 나무(二)

1267 단어
1: 시퀀스로 구성
먼저 알아야 할 것은:
(1): n개의 서로 다른 노드의 두 갈래 트리는 모두 그의 중서 서열과 선서 서열 또는 중서 서열과 후서 서열에 의해 유일하게 확정될 수 있다
(2): 두 가지 서열로 두 갈래 나무를 정할 때 선순과 후순 서열의 작용은 두 갈래 나무의 뿌리 노드를 확정하는 것이고, 중순 서열의 작용은 좌우 서브나무의 중순 서열을 확정하는 것이다
(1)의 증명은 수학 귀납법으로 할 수 있지만 (2)의 결론은 명백하다
구현:
1: 중간 및 선행 시퀀스로 구성
BTNode *CreateBTree(char pre[], char in[], int n)
{
	//pre ， in ，n ;  0 
    BTNode *p;
	char data, *temp;
	
	int i;
	if( n<=0 ) return NULL;// ，   
	data=*pre;// 
    p=new BTNode;// 
	p->data=data;
	
	for(temp=in; temp<in+n; temp++ )//  in  
		if( *temp==data ) break;
		i=temp-in;// in  i
		
		p->left=CreateBTree(pre+1, in, i);// 
		p->right=CreateBTree(pre+i+1, temp+1, n-i-1);// 
		
		return p;// 
}

2: 중간 및 하위 시퀀스로 구성
BTNode *CreateBTree(char post[], char in[], int n)
{
	//post ， in ，n ;  0 
    BTNode *p;
	char data, *temp;

	int i;
	if( n<=0 ) return NULL;
	data=*(post+n-1);// 
    p=new BTNode;// 
	p->data=data;

	for(temp=in; temp<in+n; temp++ )//  in  
		if( *temp==data ) break;
	i=temp-in;// in  i
	
	p->left=CreateBTree(post, in, i);// 
	p->right=CreateBTree(post+i, temp+1, n-i-1);// 

	return p;// 
}

2: 아이 사슬에 저장된 여러 갈래 나무를 두 갈래 나무로 바꾼다
Nuxt 프런트엔드에 Markdown/Strapi 리치 텍스트 표시.
요즘 공공조상

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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