Basic properties and ergodicity of binary tree

Binary tree ：

Each node in a tree has at most two nodes , Can have no nodes , You can also have only one node , It can also be an empty node

Let's talk about the common forms of binary trees ：

        

The difference between full binary tree and complete binary tree ：

        A full binary tree is a tree except for leaf nodes , Each node has two children

        A complete binary tree means that each node does not necessarily have two children , But if it appears on the same layer , Of the nodes of a complete binary tree i Position and full binary tree node  i The position numbers are the same , It's a complete binary tree .

        therefore , A full binary tree must be a complete binary tree , But a complete binary tree is not necessarily a full binary tree

Then let's talk about the properties of binary trees ：

        1. In the binary tree i There are at most 2^i-1 Nodes （i>0）

        2. Depth is k There are at most 2^k - 1 Nodes (k>0)

        3. For any binary tree , If the degree is 2 The number of nodes is n2 individual , Then the number of leaves n0 Must be n2+1(n0=n2+1)

        4. have n The depth of a complete binary tree of nodes must be

         5. For a completely binary tree , From top to bottom , From left to right , The number is i The node of , The left child must be 2i, The right child is numbered 2*i + 1, Their parents' number must be i/2(i=1 Time is root )

Traversal of binary tree ：

        It can be divided into three situations , The discussion of these three cases , It is based on whether to traverse the root first , Or traverse the root in the middle , Or to traverse the root at the end , It is divided into preorder traversal （DLR）, In the sequence traversal (LDR), After the sequence traversal （LRD）

        D： root L: Left node R: Right node

        Let's start with a binary tree ：

        

        First, let's talk about preorder traversal (DLR)

                Root first on the left and then on the right ： Like a function r( from A Incoming node ), And then put A Print , After all, it is the first order , Then go through the left side , That is, go down and traverse

                

                The function stack here is

                 

         

Don't talk much , Go straight to the code ：

        

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
typedef struct _binary_node binary_node;

struct _binary_node
{
	char ch;
	binary_node *lchild;
	binary_node *rchild;
};

void recursion_print(binary_node *node)
{
	if (node == NULL) {
		return;
	} 

	printf("%c ", node->ch);
	recursion_print(node->lchild);
	recursion_print(node->rchild);
}

int main()
{
	// Lean lean lean lean lean lean lean lean lean lean lean lean lean lean lean lean lean lean lean lean lean lean lean lean lean lean lean lean lean lean lean lean lean lean lean lean lean lean lean lean lean lean lean lean lean lean lean lean lean lean lean lean lean lean lean lean lean lean 
	binary_node node_a = { 'A', NULL, NULL };
	binary_node node_b = { 'B', NULL, NULL };
	binary_node node_c = { 'C', NULL, NULL };
	binary_node node_d = { 'D', NULL, NULL };
	binary_node node_e = { 'E', NULL, NULL };
	binary_node node_f = { 'F', NULL, NULL };


	node_a.lchild = &node_b;
	node_a.rchild = &node_c;

	node_b.rchild = &node_e;
	node_b.lchild = &node_d;

	node_c.rchild = &node_f;

	// Shit, shit 
	recursion_print(&node_a);
	return 1;
}

  Running results ：

        

  Yes, of course , Binary trees are certainly not recursive , therefore , For example, calculate the number of leaves of a binary tree , The height of the binary tree , Another example is copying a binary tree , Here's the complete code ：

binary_tree.c

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
typedef struct _binary_node binary_node;

struct _binary_node
{
	char ch;
	binary_node *lchild;
	binary_node *rchild;
};

void recursion_print(binary_node *node)
{
	if (node == NULL) {
		return;
	} 

	printf("%c ", node->ch);
	recursion_print(node->lchild);
	recursion_print(node->rchild);
}

void calc_leaf_num(binary_node *node,int *p)
{
	// The end condition of the program 
	if(node == NULL) {
		return ;
	}
	//left and right is null
	if(node->lchild == NULL && node->rchild == NULL) {
		(*p)++;
	}
	calc_leaf_num(node->lchild,p);// Pass in the address of the calculation quantity variable 
	calc_leaf_num(node->rchild,p);
}


// Calculate tree height 
int get_tree_high(binary_node *node)
{
	if(node == NULL) {
		return 0;
	}
	// Recursively calculate the height of the left and right trees 
	int left_high = get_tree_high(node->lchild);
	int right_high = get_tree_high(node->rchild);
	return left_high > right_high ? left_high + 1 : right_high + 1;
}

// Copying a binary tree is to create a space on the heap 
// To store every node of the binary tree 
// Finally, return to the header node 
binary_node* copy_tree(binary_node *node)
{
	if(node == NULL){
		return NULL;
	}
	
	// I still need to traverse the left tree , In traversing the right tree 
	binary_node* lnode = copy_tree(node->lchild);
	binary_node* rnode = copy_tree(node->rchild);
	// Each node has to do one thing 
	binary_node *new_node = (binary_node*)malloc(sizeof(binary_node));
	if(new_node != NULL) {
		new_node->ch = node->ch;
		new_node->lchild = lnode;
		new_node->rchild = rnode;
	}
	return new_node;
}

// Release the copied tree 
void free_tree(binary_node *node)
{
	if(node == NULL) {
		return;
	}
	free_tree(node->lchild);
	free_tree(node->rchild);
	// Before that, take a look at the released nodes 
	printf("%c Released \n",node->ch);
	free(node);// Release this node 
}
	
	
int main()
{
	binary_node node_a = { 'A', NULL, NULL };
	binary_node node_b = { 'B', NULL, NULL };
	binary_node node_c = { 'C', NULL, NULL };
	binary_node node_d = { 'D', NULL, NULL };
	binary_node node_e = { 'E', NULL, NULL };
	binary_node node_f = { 'F', NULL, NULL };


	node_a.lchild = &node_b;
	node_a.rchild = &node_c;

	node_b.rchild = &node_e;
	node_b.lchild = &node_d;

	node_c.rchild = &node_f;

	recursion_print(&node_a);

	int leaf_num = 0;

	calc_leaf_num(&node_a,&leaf_num);	
	
	printf(" The number of leaf nodes is :%d\n",leaf_num);

	int tree_high = get_tree_high(&node_a);

	printf(" The number of leaves is :%d\n",tree_high);

	// Copy the binary tree 
	binary_node *node = copy_tree(&node_a);

	// Then recursively traverse the binary tree 
	printf("\n-------------\n");
	recursion_print(node);
	printf("\n-----\n");
	// Release each node of the copy 
	
	// Binary tree non recursive traversal 
	
	free_tree(node);
	return 1;
}