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

State the output of avaerage value of numbers, Draw trace table and determi...

Draw trace table and determine output from the subsequent flowchart using below data:  X = 5, -3, 0, -3, 7, 0, 6, -11, -7, 12

Applications of binary trees, In computer programming, Trees are utilized ...

In computer programming, Trees are utilized enormously. These can be utilized for developing database search times (binary search trees, AVL trees, 2-3 trees, red-black trees), Gam

Multiple Queues in a single dimension array, Implement multiple queues in a...

Implement multiple queues in a single dimensional array. Write algorithms for various queue operations for them.

Post order traversal, Post order traversal: The children of node are vi...

Post order traversal: The children of node are visited before the node itself; the root is visited last. Each node is visited after its descendents are visited. Algorithm fo

2 Flow Charts, 1.Create a flowchart to show the process that will allow the...

1.Create a flowchart to show the process that will allow the implementation of Stack, Push, and Pop operations. 2.Create a flowchart to show the process that will allow the impleme

Terminology used for files structures, Given are the definitions of some im...

Given are the definitions of some important terms: 1) Field: This is an elementary data item characterized by its size, length and type. For instance, Name

Tic Tac Toe game , Book to refer: Introduction to Algorithms, 3rd Ed, by Cl...

Book to refer: Introduction to Algorithms, 3rd Ed, by Clifford Stein, Thomas H. Cormen, Ronald Rivest, Charles E. Leiserson Question: Tic Tac Toe game -Design a GUI and implement

Graph & optimal scheduling, You are given an undirected graph G = (V, E) in...

You are given an undirected graph G = (V, E) in which the edge weights are highly restricted. In particular, each edge has a positive integer weight of either {1,2,...,W}, where W

Number of operations possible on ordered lists and arrays, Q. Enumerate num...

Q. Enumerate number of operations possible on ordered lists and arrays.  Write procedures to insert and delete an element in to array.

Representation of data structure in memory, Representation of data structur...

Representation of data structure in memory is known as: Abstract data type

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