Trees and binary trees: Construction of binary trees

Trees and binary trees ： The construction of a binary tree

review

Same binary tree （ Assume that each node value is unique ） have only Sequence first , Middle sequence and post sequence
but Different binary trees may Having the same preorder sequence , Middle sequence or post sequence

for example ：

The following proposition is true or not ？

1. At the same time, a binary tree is given Preorder sequence and middle sequence We can only determine the binary tree .（ correct ）
2. At the same time, a binary tree is given Middle sequence and post sequence We can only determine the binary tree .（ correct ）
3. At the same time, a binary tree is given First order sequence and second order sequence We can only determine the binary tree .（ error ）

Theorem 1： whatever n(n>0) A binary tree with different nodes , Both of them can be uniquely determined by their meso sequence and preorder sequence

Demonstration of the example of constructing binary tree from preorder and inorder sequence

for example , The known sequence is ABDGCEF, The middle order sequence is DGBAECF, The process of constructing a binary tree is as follows .

The following algorithm for constructing binary tree is obtained from the above theorem ：

BTNode *CreateBT1(char *pre,char *in,int n) {
    
	BTNode *s;
	char *p;
	int k;
	if(n<=0) return NULL;
	s=(BTNode *)malloc(sizeof(BTNode)); // Create a root node 
	s->data=*pre;
	for(p=in;i<in+n;p++) // stay in Found in *pre The location of k
		if(*p==*pre)
			break;
	k=p-in;
	s->lchild=CreateBT1(pre+1,in,k); // Construct the left subtree 
	s->rchild=CreateBT1(pre+k+1,p+1,n-k-1); // Construct the right subtree 
	return s;
} // The idea of preorder traversal 

Theorem 2： whatever n(n>0) A binary tree with different nodes , Both of them can be uniquely determined by their middle order sequence and post order sequence

for example , The known middle order sequence is DGBAECF, The following sequence is GDBEFCA. The corresponding process of constructing a binary tree is as follows

The following algorithm for constructing binary tree is obtained from the above theorem ：

BTNode *CreateBT2(char *post,char *in,int n) {
    
	BTNode *b;
	char r,*p;
	int k;
	if(n<=0)
		return NULL;
	r=*(post+n-1); // Root node value 
	b=(BTNode *)malloc(sizeof(BTNode)); // Create a binary tree node *b
	b->data=r;
	for(p=in;p<in+n;p++) // stay in Find the root node in 
		if(*p==r)
			break;
	k=p-in; //k For the root node at in Subscript in 
	b->lchild=CreateBT2(post,in,k); // Recursively construct left subtree 
	b->rchild=CreateBT2(post+k,p+1,n-k-1); // Recursively construct the right subtree 
	return b; // The idea of preorder traversal 
}

Example ：

The corresponding recursive algorithm is as follows ：

BTNode *trans1(SqBTree a,int i) {
    
	BTNode *b;
	if(i>MaxSize)
		return NULL;
	if(a[i]=='#')
		return NULL; // Returns when the node does not exist NULL
	b=(BTNode *)malloc(sizeof(BTNode)); // Create a root node 
	b->data=a[i];
	b->lchild=trans1(a,2*i); // Recursively create left subtree 
	b->rchild=trans1(a,2*i+1); // Recursively create the right subtree 
	return(b); // Return root node 
} // The idea of preorder traversal 

The corresponding recursive algorithm is as follows ：

void *trans2(BTNode *b,SqBTree a,int i) {
    
	if(b!=NULL) {
    
		a[i]=b->data; // Create a root node 
		trans2(b->lchild,a,2*i); // Recursively create left subtree 
		trans2(b->rchild,a,2*i+1); // Recursively create the right subtree 
	}
} // The idea of preorder traversal