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

#binary search, Ask question #Minima binary search tree is used to locate t...

Ask question #Minima binary search tree is used to locate the number 43 which of the following probe sequences are possible and which are not? explainum 100 words accepted#

What are the languages which support assertions, What are the languages whi...

What are the languages which support assertions Languages which support assertions often provide different levels of support. For instance, Java has an assert statement which t

Applications of b-trees, A database is a collection of data organized in a ...

A database is a collection of data organized in a manner that facilitates updation, retrieval and management of the data. Searching an unindexed database having n keys will have a

Compound interest, Write the algorithm for compound interest

Write the algorithm for compound interest

Define different types of sparse matrix, Q1. Define a sparse matrix. Explai...

Q1. Define a sparse matrix. Explain different types of sparse matrices? Evaluate the method to calculate address of any element a jk of a matrix stored in memory. Q2. A linear

Insert function, INSERT FUNCTION /*prototypes of insert & find function...

INSERT FUNCTION /*prototypes of insert & find functions */ list * insert_list(list *); list * find(list *, int); /*definition of  anyinsert function */ list * inser

Cache simulator, how to design a cache simulator with 4-way set associative...

how to design a cache simulator with 4-way set associative cache

Array-based representation of a binary tree, Assume a complete binary tree ...

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

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