Cormen Edition 3 Exercise 22.1 Question 2 (Page No. 592)

Question

Give an adjacency-list representation for a complete binary tree on $7$ vertices. Give an equivalent adjacency-matrix representation. Assume that vertices are numbered from $1\ to\ 7$ as in a binary heap.

Answer 1

Complete Binary Tree on 7 vertices

            
           ________1________
      _____2___          ___3__
     4         5        6      7

Adjacency List Representation:

Node#	Connected With
1	2,3
2	1,4,5
3	1,6,7
4	2
5	2
6	3
7	3

Corresponding  adjacency matrix representation:

0 1 1 0 0 0 0

1 0 0 1 1 0 0

1 0 0 0 0 1 1

0 1 0 0 0 0 0

0 1 0 0 0 0 0

0 0 1 0 0 0 0

0 0 1 0 0 0 0