Binary trees in C

Tree:

A tree is recursively defined as a set of nodes where one node is considered as the root of the tree and all the remaining nodes are divided into non-empty sets called a sub-tree of the root node.

Binary trees in c:

It is defined as a collection of elements called nodes. Every node contains a left pointer that points to the left child, a right pointer that points to the right child, and a data element. The root element is indicated by a root pointer. The topmost node in the tree is the root element. If root= 0 then the tree is empty. It is in which each node has almost 2 children.

Key terms in a binary tree:

Parent:

If N is the root node that has a left subtree S1 and right subtree S2 then N is the parent of S1 and S2.

Level number:

The level number is assigned to the binary tree. The root node has level number 0. The left and right child nodes of the root node have a level number 1. so all the child nodes are defined to have their level number as parents level number+1.

Degree:

The degree of a node is the number of child nodes that the node has.

Sibling:

All nodes that have the same level number and a parent are called siblings

In degree:

In degree of a node is the number of edges arriving at the node.

Out degree:

Out degree of a node is the number of edges leaving from a node.

Leaf node:

A leaf node has zero child nodes

Edge:

It is a line connecting a node N to any of its successors. A binary tree has n-1 edges.

Path:

A flow of consecutive edges is called a path.

Depth:

The depth of a root node is the length of the path from the root to node N. The root node depth is zero.

Height of a tree:

It is the number of nodes on the path from the root to the leaf node in the tree.

Example of binary trees in c:

Here, Root node: 1

Level numbers: 0, 1, 2, 3

Degree:

Node	DEGREE
1	2
2	2
3	2
4	2
5	0
6	2
7	1
8	0
9	0
10	0
11	0
12	0

Sibling: nodes 2 and 3, 4 and 5, 6 and 7, 8 and 9, 10 and 11.

Leaf node: 8,9,5,10,11,12.

Path: For example, the path for node 8 is 1,2,4, and 8.

Implementation of binary tree:

#include<stdio.h>
#include<stdlib.h>
//representation of a node in binary tree
struct node
{
int value;
struct node *left_child, *right_child;
};
//creating new nodes 
struct node *new_node(int value)
{
struct node *tmp = (struct node *)malloc(sizeof(struct node));
tmp->value = value;
tmp->left_child = tmp->right_child = NULL;
return tmp;
}
//function for displaying the nodes
void print(struct node *root_node) 
{
if (root_node != NULL)//root node is null
{
print(root_node->left_child);
printf("%d \n", root_node->value);
print(root_node->right_child);
}
}
//insertion of node with data
struct node* insert_node(struct node* node, int value) 
{
if (node == NULL) return new_node(value);
if (value < node->value)
{
node->left_child = insert_node(node->left_child, value);
}
else if (value > node->value)
{
node->right_child = insert_node(node->right_child, value);
}
return node;
}
//main program
int main()
{
printf("Implementation of a Binary Tree in C!\n\n");
struct node *root_node = NULL;
root_node = insert_node(root_node, 10);
insert_node(root_node, 1);
insert_node(root_node, 2);
insert_node(root_node, 3);
insert_node(root_node, 4);
insert_node(root_node, 5);
insert_node(root_node, 6);
print(root_node);
return 0;
}

Output:

 

Also, read Python3 How can I improve my code follow the instruction?