Array-based representation of a binary tree, Data Structure & Algorithms

Assignment Help:

Assume a complete binary tree T with n nodes where each node has an item (value). Label the nodes of the complete binary tree T from top to bottom & from left to right 0, 1, ..., n-1. Relate with T the array A where the ith   entry of A is the item in the node labeled i of T, i = 0, 1, ..., n-1. Table illustrates the array representation of a Binary tree of Figure

1724_Array-based representation of a Binary Tree.png

Given the index i of a node, we can efficiently & easily compute the index of its parent and left & right children:

Index of Parent: (i - 1)/2, Index of Left Child: 2i + 1, Index of Right Child: 2i + 2.

Node #

Item

Left child

Right child

0

A

1

2

1

B

3

4

2

C

-1

-1

3

D

5

6

4

E

7

8

5

G

-1

-1

6

H

-1

-1

7

I

-1

-1

8

J

-1

-1

9

?

?

?

Table: Array Representation of a Binary Tree

First column illustrates index of node, second column contain the item stored into the node & third & fourth columns mention the positions of left & right children

(-1 shows that there is no child to that specific node.)


Related Discussions:- Array-based representation of a binary tree

Threads in main method, Create main method or a test class that creates 2 E...

Create main method or a test class that creates 2 Element objects that are neighbours of each other, the first element temperature set at 100, the 2nd at 0 and use an appropriate h

Algorithmic implementation of multiple stacks, So far, we now have been con...

So far, we now have been concerned only with the representation of single stack. What happens while a data representation is required for several stacks? Let us consider an array X

Explain division method, Explain Division Method Division Method: - In...

Explain Division Method Division Method: - In this method, key K to be mapped into single of the m states in the hash table is divided by m and the remainder of this division

Calculation of storage complexity, Since memory is becoming more & cheaper,...

Since memory is becoming more & cheaper, the prominence of runtime complexity is enhancing. However, it is very much significant to analyses the amount of memory utilized by a prog

How to measure the algorithm efficiency, How to measure the algorithm's eff...

How to measure the algorithm's efficiency? It is logical to examine the algorithm's efficiency as a function of some parameter n showing the algorithm's input size. Instance

What are the objectives of visual realism applications, What are the Object...

What are the Objectives of visual realism applications After studying this unit, you should be able to know specific needs of realism, add realism to pictures by el

Algorithm for determining who won rock paper scissors game, Suppose you are...

Suppose you are given the results of 5 games of rock-paper-scissors. The results are given to you on separate pieces of paper; each piece says either 'A' if the first person won, o

Circularly linked lists implementation, CIRCULARLY LINKED LISTS IMPLEMENTAT...

CIRCULARLY LINKED LISTS IMPLEMENTATION A linked list wherein the last element points to the first element is called as CIRCULAR linked list. The chains do not specified first o

Effective way of storing two symmetric matrices, Explain an efficient and e...

Explain an efficient and effective way of storing two symmetric matrices of the same order in the memory. A n-square matrix array will be symmetric if a[j][k]=a[k][j] for all j

Search, What are the conditions under which sequential search of a list is ...

What are the conditions under which sequential search of a list is preferred over binary search?

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