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

Algorithms for push and pop operation, Q. Suggest a method of implementing ...

Q. Suggest a method of implementing two stacks in one array such that as long as space is there in an array, you should be capable to add an element in either stack. Using proposed

Graphs, c program to represent a graph as an adjacency multilist form

c program to represent a graph as an adjacency multilist form

Linked list, create aset of ten numbers.then you must divide it into two s...

create aset of ten numbers.then you must divide it into two sets numbers which are set of odd numbers and set of even numbers.

Define the internal path length, Define the Internal Path Length The In...

Define the Internal Path Length The Internal Path Length I of an extended binary tree is explained as the sum of the lengths of the paths taken over all internal nodes- from th

Illustrate the operations of the symbol abstract data type, The operations ...

The operations of the Symbol ADT The operations of the Symbol ADT are the following. a==b-returns true if and only if symbols a and bare identical. a symbol bin Unico

Define prims algorithm, Define Prim's Algorithm Prim's  algorithm  is  ...

Define Prim's Algorithm Prim's  algorithm  is  a  greedy  algorithm  for  constructing  a  minimum  spanning  tree  of  a  weighted linked graph. It works by attaching to a bef

Structures for complete undirected graphs, Q. Draw  the structures of compl...

Q. Draw  the structures of complete  undirected  graphs  on  one,  two,  three,  four  and  five vertices also prove that the number of edges in an n vertex complete graph is n(n-1

Describe data structure?, Typical programming languages such as Pascal, C o...

Typical programming languages such as Pascal, C or Java give primitive data kinds such as integers, boolean, reals values and strings. They give these to be organised into arrays,

Linear array, representation of linear array

representation of linear array

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