Implementation of a binary tree, Data Structure & Algorithms

Assignment Help:

Like general tree, binary trees are implemented through linked lists. A typical node in a Binary tree has a structure as follows

struct NODE

{

struct NODE *leftchild;

int nodevalue;               /* this can be of any data type */

struct NODE *rightchild;

};

805_IMPLEMENTATION OF A BINARY TREE.png

Figure: Node structure of a binary tree

The 'left child 'and 'right child' are pointers to another tree-node. The "leaf node" (not shown) here will have NULL values for these pointers.

The binary tree creation follows a extremely simple principle. For the new element to be inserted, compare it along with the current element in the tree. If its value is less than the present element in the tree, then move to the left side of that element or else to its right. If there is no sub tree at the left, then make your new element as the left child of that present element or else compare it to the existing left child and follow the similar rule. Exactly, the same need to done for the case while your new element is greater than the current element into the tree however this time with the right child. Though this logic is followed for the formation of a Binary tree, this logic is frequently suitable to search for a key value in the binary tree.

Following is algorithm for the implementation of Binary tree:

Step-1: If new element < current element, then go to step-2 or else go to step -3

Step-2: If the current element does not contain a left sub-tree, then converts new element into the left child of the current element; else make the existing left child as your current element and go to step-1

Step-3: If the current element does not contain a right sub-tree, then converts new element into the right child of the present element; else make the existing right child as your existing element and go to step-1


Related Discussions:- Implementation of a binary tree

Recurrence relation, solve the following relation by recursive method: T(n...

solve the following relation by recursive method: T(n)=2T(n^1/2)+log n

Algorithm to merge two sorted arrays with third array, Q. Write down an alg...

Q. Write down an algorithm to merge the two sorted arrays into the third array. Do  not perform the sort function in the third array.                           Ans: void m

Binary search, Explain binary search with an example

Explain binary search with an example

Procedure of analysis of algorithm, Example 1:  Following are Simple sequen...

Example 1:  Following are Simple sequence of statements Statement 1;  Statement 2; ... ... Statement k; The entire time can be found out through adding the times for

A Booth''s, Draw a flowchart of a Booth''s multiplication algorithm and exp...

Draw a flowchart of a Booth''s multiplication algorithm and explain it.

Design a doubly linked list, Instructions : You have to design a dou...

Instructions : You have to design a doubly linked list container. The necessary classes and their declarations are given below The main() function for testing the yo

Splaying algorithm, Insertion & deletion of target key requires splaying of...

Insertion & deletion of target key requires splaying of the tree. In case of insertion, the tree is splayed to find the target. If, target key is found out, then we have a duplicat

What is class invariants assertion, What is Class invariants assertion ...

What is Class invariants assertion A class invariant is an assertion which should be true of any class instance before and after calls of its exported operations. Generally

Representation of a sparse matrix, Let us assume a sparse matrix from stora...

Let us assume a sparse matrix from storage view point. Assume that the entire sparse matrix is stored. Then, a significant amount of memory that stores the matrix consists of zeroe

Implement the physat algorithm, The first assignment in this course require...

The first assignment in this course required you to acquire data to enable you to implement the PHYSAT algorithm (Alvain et al. 2005, Alvain et al. 2008) in this second assignment

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd