Thursday, 23 November 2017

Binary Tree Representations using Array:

In particular, we want to find out the maximum number of nodes in a binary tree of depth k, and the number of leaf nodes and the number of nodes of degree two in a binary tree.  We present both these observations as lemma.

Lemma 5.1: [Maximum number of nodes]:
(1)The maximum number of nodes on level i of a binary tree is 2i -1, i >= 1
(2)The maximum number of nodes in a binary tree of depth k is 2k - 1, k >= 1

Lemma 5.2:  [Relation between number of leaf nodes and nodes of degree 2]:
Nonempty binary tree, T, if n0 is the number of leaf nodes and n2 the number of nodes of degree 2, then n0 = n2 + 1.

Binary Tree Representations using Array:
The numbering scheme used in it suggests out first representation of a binary tree in memory.  Since the nodes are numbered from 1 to n, we can use a one-dimensional array to store the nodes.  (We do not use the 0th position of the array.)  Using Lemma 5.1 we can easily determine the locations of the parent, left child, and right child of any node, i, in the binary tree.
Lemma 5.3:  
If a complete binary tree with n nodes (depth = └ log2n +1┘) is represented sequentially, then for any node with index i, 1<= i <=n, we have:
(1) parent(i) is at └i/2┘ if i != 1 and if i = 1, i is at the root and has no parent.
(2) left_child(i) is at 2i if 2i <= n.  If 2i > n, then i has no left child.

(3) right_child(i) is at (2i + 1), if (2i + 1) <= n.  If (2i + 1) > n, then i has no right child.


Thanks
Mukesh Rajput

No comments:

Post a Comment

Thanks
Mukesh Rajput