Tree and binary tree: basic operation and implementation of binary tree

Tree and binary tree basic operations and their implementation

An overview of the basic operations of binary trees

Sum up , The binary tree has the following Basic operation ：

• Create a binary tree CreateBTNode(*b, *str)： According to the binary tree bracket representation string str Generate the corresponding binary chain storage structure b
• Destroy binary chain storage structure DestroyBT(*b)： Destroy binary chain b And free up space
• Find node FindNode(*b,x)： In the binary tree b Search for data The domain value is x The node of , And return a pointer to the node
• Find a child node LchildNode( p) and RchildNode( p)： Find the nodes in the binary tree respectively *p Left child node and right child node of
• For height BTNodeDepth(*b)： Find a binary tree b Height . If binary tree is empty , Then its height is 0; otherwise , Its height is equal to the maximum height of the left subtree and the right subtree plus 1
• Output binary tree DispBTNode(*b)： Output a binary tree in parentheses

The basic arithmetic implementation of binary tree

（1） Create a binary tree CreateBTNode(* b,*str)

Correct binary tree brackets indicate that there are only 4 Class characters ：

• Single character ： The value of the node
• (： Indicates the beginning of a left subtree
• )： Indicates the end of a subtree
• ,： Represents the beginning of a right subtree

Algorithm design ：

• First construct The root node N, Reconstruct The left subtree L, Finally, construct Right subtree R
• structure Right subtree R when , Can't find N 了 , All need to be saved N
• The nodes are matched according to the nearest principle , So use a Stack preservation N

use ch Scan strings that represent binary trees in parenthesis ：

1. if ch=‘(’： The previously created node is stacked as a parent node , Juxtaposition k=1, Indicates the start of processing the left child node
2. if ch=‘)’： Represents the left... Of the top node of the stack , The right child node has been processed , Backstack
3. if ch=‘,’： Indicates the start of processing the right child node , Set up k=2
4. Other situations （ Node values ）：
   establish p Node is used to store ch
   When k=1 when , take p Node as the left child node of the top node of the stack
   When k=2 when , take *p Node as the right child node of the top node of the stack

void CreateBTNode(BTNode *&b,char *str) {
    
	// from str- Binary chain b
	BTNode *St[MaxSize],*p;
	int top=-1,k,j=0;
	char ch;
	b = NULL; // The binary chain is initially empty 
	ch = str[j];
	while(ch!='\0') {
     //str Cycle before the scan is complete 
		switch(ch) {
    	
			case'(':top++;St[top]=p;k=1; break; // There may be left child nodes , Into the stack 
			case')':top--; break;
			case',':k=2; break; // The following is the right child node 
			default: // Node value encountered 
				p=(BTNode *)malloc(sizeof(BTNode));
				p->data=ch; p->lchild=p->rchild=NULL;
				if (b==NULL) //p Is the root node of the binary tree 
					b=p;
				else {
     // The root node of the binary tree has been established 
					switch(k) {
    
						case 1:St[top]->lchild=p; break;
						case 2:St[top]->rchild=p; break;
					}
				}
		}
			j++; ch=str[j]; // Continue scanning str
	}
}

（2） Destroy binary chain DestroyBT(*b)

The recursive model is as follows ：

The corresponding recursive algorithm is as follows ：

void DestroyBT(BTNode *&b) {
    
	if(b==NULL)
		return ;
	else {
    
		DestroyBT(b->lchild);
		DestroyBT(b->rchild);
		free(b); // There is one node left *b, Direct release 
	}
}

（4） Find node FindNode(*b,x)

The corresponding recursive algorithm is as follows ：

BTNode *FindNode(BTNode *b,ElemType x) {
    
	BTNode *p;
	if(b==NULL)
		return NULL;
	else if(b->data==x)
		return b;
	else {
    
		p=FindNode(b->lchild,x);
		if(p!=NULL) 
			return p;
		else
			return FindNode(b->rchild,x);
	}
}

（4） Find a child node LchildNode§ and RchildNode§

Go straight back to *p Pointer to the left child node or the right child node of the node

BTNode *LchildNode(BTNode *p) {
    
	return p->lchild;
}

BTNode *RchildNode(BTNode *p) {
    
	return p->rchild;
}

（5） For height BTNodeDepth(*b)

The corresponding recursive algorithm is as follows ：

int BTNodeDepth(BTNode *b) {
    
	int lchilddep,rchilddep;
	if(b==NULL)
		return(0); // The height of the empty tree is 0
	else {
    
		lchilddep=BTNodeDepth(b->lchild); // Find the height of the left subtree as lchilddep
		rchilddep=BTNodeDepth(b->rchild); // Find the height of the right subtree as rchilddep
		return ((lchilddep>rchilddep) ? (lchilddep+1):(rchilddep+1));
	}
}

（6） Output binary tree DispBTNode(*b)

The root node （ The left subtree , Right subtree ）—— Brackets indicate

void DispBTNode(BTNode *b) {
    
	if(b!=NULL) {
    
		printf("%c",b->data);
		if(b->lchild!=NULL || b->rchild!=NULL) {
    
			printf("(");
			DispBTNode(b->lchild); // Recursively handle the left subtree 
			if(b->rchild!=NULL)
				printf(",");
			DispBTNode(b->rchild); // Recursively handle the right subtree 
			printf(")");
		}
	}
}