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

Which sorting methods sorting a list which is almost sorted, Which sorting ...

Which sorting methods would be most suitable for sorting a list which is almost sorted  Bubble Sorting method.

Union & intersection of two linklist, how to write an algorithm for unions ...

how to write an algorithm for unions & intersection of two linklists?

Binary search tree, Objectives The purpose of this project is to give yo...

Objectives The purpose of this project is to give you significant exposure to Binary Search Trees (BST), tree traversals, and recursive code. Background An arbitrary BST i

Representation of arrays, REPRESENTATION OF ARRAYS This is not uncommon...

REPRESENTATION OF ARRAYS This is not uncommon to determine a large number of programs which procedure the elements of an array in sequence. However, does it mean that the eleme

Explain multidimensional array, Multidimensional array: Multidimensional a...

Multidimensional array: Multidimensional arrays can be defined as "arrays of arrays". For example, a bidimensional array can be imagined as a bidimensional table made of elements,

LINKED LIST, HOW LINKED LIST HEADER WORKS? HOW TO INSERT AND DELETE ELEMENT...

HOW LINKED LIST HEADER WORKS? HOW TO INSERT AND DELETE ELEMENTS IN LINKED LIST?

Data structures, Aa) Come up with an ERD from the following scenario, clear...

Aa) Come up with an ERD from the following scenario, clearly stating all entities, attributes, relationships before final sketch of the ERD: [50 m

Abstract data type- queue, A significant aspect of Abstract Data Types is t...

A significant aspect of Abstract Data Types is that they explain the properties of a data structure without specifying the details of its implementation. The properties might be im

The space - time trade off, The Space - Time Trade Off The best algorit...

The Space - Time Trade Off The best algorithm to solve a given problem is one that needs less space in memory and takes less time to complete its implementation. But in practic

Non-recursive implementation of binary tree traversals, As we have seen, as...

As we have seen, as the traversal mechanisms were intrinsically recursive, the implementation was also easy through a recursive procedure. Though, in the case of a non-recursive me

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