On binary tree (C language)

Binary tree is a very classical non-linear discontinuous data structure in tree data structure , It is widely used because of its excellent time complexity , In this article, we will talk about the generation and traversal of binary trees .
For example, how can we solve the storage problem of binary trees in the figure below ？

Here we can control the input format when inputting , That is, we can input the left subtree first, set an end flag after the input of the left subtree of a branch, and then continue to input the right subtree , In the figure above, we can input according to the following format ：
ABC##DE###FG###
Now let's look at the code directly , There are some recursive ideas in the code , If you don't understand anything, you can track variables , It will also be clearer to see in this way .

void creatB_TREE(B_TREE **root) {
    
	char ch;
	scanf("%c",&ch);

	if (ch == '#') {
    
		*root = NULL;
	} else {
    
		*root = (B_TREE *) calloc(sizeof(B_TREE), 1);
		(*root)->data = ch;
		creatB_TREE(&((*root)->leftChild));
		creatB_TREE(&((*root)->rightChild));
	}
}

After writing this function, let's take a look at the traversal of binary tree , The traversal of binary trees is divided into three types, namely, the first root order , Middle root order , Posterior root order . It looks like three types, but their code is only a little different , We use “ First root order ” For example, let's talk about traversal of binary tree .
The so-called first root order is to access the root node first, take out the data in it, and then treat the left subtree of the root node as the root node, continue to access the data in it, and then access the right subtree after the left subtree is accessed . There are also some recursive ideas , It is suggested that you carry out variable tracking for easy understanding .

void preRootOrder(B_TREE *root) {
    
	if (root) {
    
		printf("[%c] ",root->data);
		preRootOrder(root->leftChild);
		preRootOrder(root->rightChild);
	}
}

After understanding the above code, we will directly follow the code of middle root order and post root order , The difference between them is very small , There is only a small difference in when to fetch the data in the root node .

void posteriorRootOrder(B_TREE *root){
    
	if (root) {
    
		posteriorRootOrder(root->leftChild);
		posteriorRootOrder(root->rightChild);
		printf("[%c] ",root->data);
	}	
}

void middleRootOrder(B_TREE *root) {
    
	if (root) {
    
		middleRootOrder(root->leftChild);
		printf("[%c] ",root->data);
		middleRootOrder(root->rightChild);		
	}

}

Finally, let's take a look at the complete code and its operation ：

#include <stdio.h>
#include <malloc.h>

typedef struct B_TREE {
    
	char data;
	struct B_TREE *leftChild;
	struct B_TREE *rightChild;
}B_TREE;

void creatB_TREE(B_TREE **root);
void preRootOrder(B_TREE *root);
void middleRootOrder(B_TREE *root);
void posteriorRootOrder(B_TREE *root);

void posteriorRootOrder(B_TREE *root){
    
	if (root) {
    
		posteriorRootOrder(root->leftChild);
		posteriorRootOrder(root->rightChild);
		printf("[%c] ",root->data);
	}	
}

void middleRootOrder(B_TREE *root) {
    
	if (root) {
    
		middleRootOrder(root->leftChild);
		printf("[%c] ",root->data);
		middleRootOrder(root->rightChild);		
	}

}

void preRootOrder(B_TREE *root) {
    
	if (root) {
    
		printf("[%c] ",root->data);
		preRootOrder(root->leftChild);
		preRootOrder(root->rightChild);
	}
}

void creatB_TREE(B_TREE **root) {
    
	char ch;
	scanf("%c",&ch);

	if (ch == '#') {
    
		*root = NULL;
	} else {
    
		*root = (B_TREE *) calloc(sizeof(B_TREE), 1);
		(*root)->data = ch;
		creatB_TREE(&((*root)->leftChild));
		creatB_TREE(&((*root)->rightChild));
	}
}

int main() {
    
	B_TREE *root = NULL;

	printf("please input your data,'#' is symbol of over:"); 
	creatB_TREE(&root);

	printf("preRootOrder:");
	preRootOrder(root);
	printf("\n");

	printf("middleRootOrder:");
	middleRootOrder(root);
	printf("\n");

	printf("posteriorRootOrder:");
	posteriorRootOrder(root);
	printf("\n");

	return 0;

}

If you have any questions, please leave a message below , Thank you for watching .