CSharp  Java  Python  Swift  GO  WPF  Ruby  Scala  F#  JavaScript  SQL  PHP  Angular  HTML
Q. Program to implement Binary Tree using the linked listExplanationIn this program, we need to create the binary tree by inserting nodes and displaying nodes in inorder fashion. A typical binary tree can be represented as follows: In the binary tree, each node can have at most two children. Each node can have zero, one or two children. Each node in the binary tree contains the following information: Data that represents value stored in the node. Left that represents the pointer to the left child. Right that represents the pointer to the right child. Algorithm
SolutionPython#Represent a node of binary tree class Node: def __init__(self,data): #Assign data to the new node, set left and right children to None self.data = data; self.left = None; self.right = None; class BinaryTree: def __init__(self): #Represent the root of binary tree self.root = None; #insertNode() will add new node to the binary tree def insertNode(self, data): #Create a new node newNode = Node(data); #Check whether tree is empty if(self.root == None): self.root = newNode; return; else: queue = []; #Add root to the queue queue.append(self.root); while(True): node = queue.pop(0); #If node has both left and right child, add both the child to queue if(node.left != None and node.right != None): queue.append(node.left); queue.append(node.right); else: #If node has no left child, make newNode as left child if(node.left == None): node.left = newNode; queue.append(node.left); else: #If node has left child but no right child, make newNode as right child node.right = newNode; queue.append(node.right); break; #inorder() will perform inorder traversal on binary search tree def inorderTraversal(self, node): #Check whether tree is empty if(self.root == None): print("Tree is empty"); return; else: if(node.left != None): self.inorderTraversal(node.left); print(node.data), if(node.right!= None): self.inorderTraversal(node.right); bt = BinaryTree(); #Add nodes to the binary tree bt.insertNode(1); #1 will become root node of the tree print("Binary tree after insertion"); #Binary after inserting nodes bt.inorderTraversal(bt.root); bt.insertNode(2); bt.insertNode(3); #2 will become left child and 3 will become right child of root node 1 print("\nBinary tree after insertion"); #Binary after inserting nodes bt.inorderTraversal(bt.root); bt.insertNode(4); bt.insertNode(5); #4 will become left child and 5 will become right child of node 2 print("\nBinary tree after insertion"); #Binary after inserting nodes bt.inorderTraversal(bt.root); bt.insertNode(6); bt.insertNode(7); #6 will become the left child and 7 will become the right child of node 3 print("\nBinary tree after insertion"); #Binary after inserting nodes bt.inorderTraversal(bt.root); Output: Binary tree after insertion 1 Binary tree after insertion 2 1 3 Binary tree after insertion 4 2 5 1 3 Binary tree after insertion 4 2 5 1 6 3 7 C#include <stdio.h> #include <stdlib.h> #include <stdbool.h> //Represent a node of binary tree struct node{ int data; struct node *left; struct node *right; }; //Represent the root of binary tree struct node *root = NULL; //createNode() will create a new node struct node* createNode(int data){ //Create a new node struct node *newNode = (struct node*)malloc(sizeof(struct node)); //Assign data to newNode, set left and right child to NULL newNode>data = data; newNode>left = NULL; newNode>right = NULL; return newNode; } //Represent a queue struct queue { int front, rear, size; struct node* *arr; }; //createQueue() will create a queue struct queue* createQueue() { struct queue* newQueue = (struct queue*) malloc(sizeof( struct queue )); newQueue>front = 1; newQueue>rear = 0; newQueue>size = 0; newQueue>arr = (struct node**) malloc(100 * sizeof( struct node* )); return newQueue; } //Adds a node to queue void enqueue(struct queue* queue, struct node *temp){ queue>arr[queue>rear++] = temp; queue>size++; } //Deletes a node from queue struct node *dequeue(struct queue* queue){ queue>size; return queue>arr[++queue>front]; } //insertNode() will add new node to the binary tree void insertNode(int data) { //Create a new node struct node *newNode = createNode(data); //Check whether tree is empty if(root == NULL){ root = newNode; return; } else { //Queue will be used to keep track of nodes of tree levelwise struct queue* queue = createQueue(); //Add root to the queue enqueue(queue, root); while(true) { struct node *node = dequeue(queue); //If node has both left and right child, add both the child to queue if(node>left != NULL && node>right != NULL) { enqueue(queue, node>left); enqueue(queue, node>right); } else { //If node has no left child, make newNode as left child if(node>left == NULL) { node>left = newNode; enqueue(queue, node>left); } //If node has left child but no right child, make newNode as right child else { node>right = newNode; enqueue(queue, node>right); } break; } } } } //inorder() will perform inorder traversal on binary search tree void inorderTraversal(struct node *node) { //Check whether tree is empty if(root == NULL){ printf("Tree is empty\n"); return; } else { if(node>left != NULL) inorderTraversal(node>left); printf("%d ", node>data); if(node>right != NULL) inorderTraversal(node>right); } } int main(){ //Add nodes to the binary tree insertNode(1); //1 will become root node of the tree printf("Binary tree after insertion: \n"); //Binary after inserting nodes inorderTraversal(root); insertNode(2); insertNode(3); //2 will become left child and 3 will become right child of root node 1 printf("\nBinary tree after insertion: \n"); //Binary after inserting nodes inorderTraversal(root); insertNode(4); insertNode(5); //4 will become left child and 5 will become right child of node 2 printf("\nBinary tree after insertion: \n"); //Binary after inserting nodes inorderTraversal(root); insertNode(6); insertNode(7); //6 will become left child and 7 will become right child of node 3 printf("\nBinary tree after insertion: \n"); //Binary after inserting nodes inorderTraversal(root); return 0; } Output: Binary tree after insertion 1 Binary tree after insertion 2 1 3 Binary tree after insertion 4 2 5 1 3 Binary tree after insertion 4 2 5 1 6 3 7 JAVAimport java.util.LinkedList; import java.util.Queue; public class BinaryTree { //Represent a node of binary tree public static class Node{ int data; Node left; Node right; public Node(int data){ //Assign data to the new node, set left and right children to null this.data = data; this.left = null; this.right = null; } } //Represent the root of binary tree public Node root; public BinaryTree(){ root = null; } //insertNode() will add new node to the binary tree public void insertNode(int data) { //Create a new node Node newNode = new Node(data); //Check whether tree is empty if(root == null){ root = newNode; return; } else { Queue<Node> queue = new LinkedList<Node>(); //Add root to the queue queue.add(root); while(true) { Node node = queue.remove(); //If node has both left and right child, add both the child to queue if(node.left != null && node.right != null) { queue.add(node.left); queue.add(node.right); } else { //If node has no left child, make newNode as left child if(node.left == null) { node.left = newNode; queue.add(node.left); } //If node has left child but no right child, make newNode as right child else { node.right = newNode; queue.add(node.right); } break; } } } } //inorder() will perform inorder traversal on binary search tree public void inorderTraversal(Node node) { //Check whether tree is empty if(root == null){ System.out.println("Tree is empty"); return; } else { if(node.left!= null) inorderTraversal(node.left); System.out.print(node.data + " "); if(node.right!= null) inorderTraversal(node.right); } } public static void main(String[] args) { BinaryTree bt = new BinaryTree(); //Add nodes to the binary tree bt.insertNode(1); //1 will become root node of the tree System.out.println("Binary tree after insertion"); //Binary after inserting nodes bt.inorderTraversal(bt.root); bt.insertNode(2); bt.insertNode(3); //2 will become left child and 3 will become right child of root node 1 System.out.println("\nBinary tree after insertion"); //Binary after inserting nodes bt.inorderTraversal(bt.root); bt.insertNode(4); bt.insertNode(5); //4 will become left child and 5 will become right child of node 2 System.out.println("\nBinary tree after insertion"); //Binary after inserting nodes bt.inorderTraversal(bt.root); bt.insertNode(6); bt.insertNode(7); //6 will become left child and 7 will become right child of node 3 System.out.println("\nBinary tree after insertion"); //Binary after inserting nodes bt.inorderTraversal(bt.root); } } Output: Binary tree after insertion 1 Binary tree after insertion 2 1 3 Binary tree after insertion 4 2 5 1 3 Binary tree after insertion 4 2 5 1 6 3 7 C#using System; using System.Collections.Generic; namespace Tree { public class Program { //Represent a node of binary tree public class Node<T>{ public T data; public Node<T> left; public Node<T> right; public Node(T data) { //Assign data to the new node, set left and right children to null this.data = data; this.left = null; this.right = null; } } public class BinaryTree<T>{ //Represent the root of binary tree public Node<T> root; public BinaryTree(){ root = null; } //insertNode() will add new node to the binary tree public void insertNode(T data) { //Create a new node Node<T> newNode = new Node<T>(data); //Check whether tree is empty if(root == null){ root = newNode; return; } else { Queue<Node<T>> queue = new Queue<Node<T>>(); //Add root to the queue queue.Enqueue(root); while(true) { Node<T> node = queue.Dequeue(); //If node has both left and right child, add both the child to queue if(node.left != null && node.right != null) { queue.Enqueue(node.left); queue.Enqueue(node.right); } else { //If node has no left child, make newNode as left child if(node.left == null) { node.left = newNode; queue.Enqueue(node.left); } //If node has left child but no right child, make newNode as right child else { node.right = newNode; queue.Enqueue(node.right); } break; } } } } //inorder() will perform inorder traversal on binary search tree public void inorderTraversal(Node<T> node) { //Check whether tree is empty if(root == null){ Console.WriteLine("Tree is empty"); return; } else { if(node.left!= null) inorderTraversal(node.left); Console.Write(node.data + " "); if(node.right!= null) inorderTraversal(node.right); } } } public static void Main() { BinaryTree<int> bt = new BinaryTree<int>(); //Add nodes to the binary tree bt.insertNode(1); //1 will become root node of the tree Console.WriteLine("Binary tree after insertion"); //Binary after inserting nodes bt.inorderTraversal(bt.root); bt.insertNode(2); bt.insertNode(3); //2 will become left child and 3 will become right child of root node 1 Console.WriteLine("\nBinary tree after insertion"); //Binary after inserting nodes bt.inorderTraversal(bt.root); bt.insertNode(4); bt.insertNode(5); //4 will become left child and 5 will become right child of node 2 Console.WriteLine("\nBinary tree after insertion"); //Binary after inserting nodes bt.inorderTraversal(bt.root); bt.insertNode(6); bt.insertNode(7); //6 will become left child and 7 will become right child of node 3 Console.WriteLine("\nBinary tree after insertion"); //Binary after inserting nodes bt.inorderTraversal(bt.root); } } } Output: Binary tree after insertion 1 Binary tree after insertion 2 1 3 Binary tree after insertion 4 2 5 1 3 Binary tree after insertion 4 2 5 1 6 3 7 PHP<!DOCTYPE html> <html> <body> <?php //Represent a node of binary tree class Node{ public $data; public $left; public $right; function __construct($data){ //Assign data to the new node, set left and right children to NULL $this>data = $data; $this>left = NULL; $this>right = NULL; } } class BinaryTree{ //Represent the root of binary tree public $root; function __construct(){ $this>root = NULL; } //insertNode() will add new node to the binary tree function insertNode($data) { //Create a new node $newNode = new Node($data); //Check whether tree is empty if($this>root == NULL){ $this>root = $newNode; return; } else { $queue = array(); //Add root to the queue array_push($queue, $this>root); while(true) { $node = array_shift($queue); //If node has both left and right child, add both the child to queue if($node>left != NULL && $node>right != NULL) { array_push($queue, $node>left); array_push($queue, $node>right); } else { //If node has no left child, make newNode as left child if($node>left == NULL) { $node>left = $newNode; array_push($queue, $node>left); } //If node has left child but no right child, make newNode as right child else { $node>right = $newNode; array_push($queue, $node>right); } break; } } } } //inorder() will perform inorder traversal on binary search tree function inorderTraversal($node) { //Check whether tree is empty if($this>root == NULL){ print("Tree is empty <br>"); return; } else { if($node>left != NULL) $this>inorderTraversal($node>left); print($node>data . " "); if($node>right != NULL) $this>inorderTraversal($node>right); } } } $bt = new BinaryTree(); //Add nodes to the binary tree $bt>insertNode(1); //1 will become root node of the tree print("\nBinary tree after insertion <br>"); //Binary after inserting nodes $bt>inorderTraversal($bt>root); $bt>insertNode(2); $bt>insertNode(3); //2 will become left child and 3 will become right child of root node 1 print("<br> Binary tree after insertion <br>"); //Binary after inserting nodes $bt>inorderTraversal($bt>root); $bt>insertNode(4); $bt>insertNode(5); //4 will become left child and 5 will become right child of node 2 print("<br> Binary tree after insertion <br>"); //Binary after inserting nodes $bt>inorderTraversal($bt>root); $bt>insertNode(6); $bt>insertNode(7); //6 will become left child and 7 will become right child of node 3 print("<br> Binary tree after insertion <br>"); //Binary after inserting nodes $bt>inorderTraversal($bt>root); ?> </body> </html> Output: Binary tree after insertion 1 Binary tree after insertion 2 1 3 Binary tree after insertion 4 2 5 1 3 Binary tree after insertion 4 2 5 1 6 3 7
Next TopicPrograms List
