How to draw a Tree from array of integer

To draw a binary tree from an array of integers that represents a Max-Heap, you'll need to follow these steps:

Understand the Max-Heap Property:

In a Max-Heap, for every node i, the value of i is greater than or equal to the values of its children. This means the maximum value is at the root of the heap.

Understand the Array Representation of a Binary Heap:

For a given index i in the array:

Left child: 2*i + 1
Right child: 2*i + 2
Parent: (i - 1) / 2 (integer division)

Drawing the Tree:

Use a graphical library to draw the tree, or print it in a console-based format.
Here’s an example using Java to visualize the Max-Heap as a tree.

Example Java Code to Draw a Max-Heap Tree

This example will print a textual representation of the Max-Heap binary tree. You can adapt this approach or use graphical libraries if needed.

java

public class MaxHeapPrinter {

public static void main(String[] args) {

int[] heap = { 10, 9, 8, 4, 5, 7, 6 };

printHeap(heap, 0, 0, "H", 10);

}

public static void printHeap(int[] heap, int index, int level, String direction, int maxLevel) {

if (index >= heap.length) {

return;

}

// Print the right child

printHeap(heap, 2 * index + 2, level + 1, "R", maxLevel);

// Print the current node

String indent = " ".repeat(level * maxLevel);

System.out.println(indent + direction + ": " + heap[index]);

// Print the left child

printHeap(heap, 2 * index + 1, level + 1, "L", maxLevel);

}

Explanation of the Code

Heap Array:

int[] heap = { 10, 9, 8, 4, 5, 7, 6 }; represents the Max-Heap.

printHeap Method:

This method is a recursive function that prints the tree. It takes parameters:

heap: The array representation of the heap.
index: The current index in the array.
level: The current depth of the node in the tree.
direction: Indicates whether the node is a left or right child of its parent.
maxLevel: Used to control the spacing in the output to visually represent the tree structure.

Recursive Calls:

Right Child: printHeap(heap, 2 * index + 2, level + 1, "R", maxLevel);
Current Node: Prints the value at the current index.
Left Child: printHeap(heap, 2 * index + 1, level + 1, "L", maxLevel);

Output:

The tree is printed in a top-down format where each level of the tree is indented according to its depth.

Example Output

Given the heap {10, 9, 8, 4, 5, 7, 6}, the output will look like this:

yaml

R: 6

R: 7

L: 5

R: 4

L: 8

R: 9

L: 10

Graphical Representation

For graphical representation, you might consider using libraries such as:

JavaFX: For creating graphical user interfaces and drawing trees.
JFreeChart: For drawing charts and plots, which can also be adapted for tree structures.
Graphviz: A powerful tool for creating visual representations of graphs and trees.

You can generate a DOT file with Graphviz and convert it to an image or other graphical formats.

Graphical Representation of Heap Sort

Step 1

package com.kartik.sorting.tree;
/**
*
* @author MandalKC
*
* @param <T>
*/
public class Node<T extends Comparable<?>> {
    public Node<T> left;
public Node<T> right;
    T data;
    public Node(T data) {
        this.data = data;
    }
}

Step 2

package com.kartik.sorting.tree;
/**

* @author kartik

* This is dynamic heap sort tree printer

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
/**
*
* @author MandalKC
*
*/
public class BTreePrinter {
/**
*
* @param root
*/
public static <T extends Comparable<?>> void printNode(Node<T> root) {
  int maxLevel = BTreePrinter.maxLevel(root);
  printNodeInternal(Collections.singletonList(root), 1, maxLevel);
}
/**
*
* @param nodes
* @param level
* @param maxLevel
*/
private static <T extends Comparable<?>> void printNodeInternal(
   List<Node<T>> nodes, int level, int maxLevel) {
  if (nodes.isEmpty() || BTreePrinter.isAllElementsNull(nodes))
   return;
  int floor = maxLevel - level;
  int endgeLines = (int) Math.pow(2, (Math.max(floor - 1, 0)));
  int firstSpaces = (int) Math.pow(2, (floor)) - 1;
  int betweenSpaces = (int) Math.pow(2, (floor + 1)) - 1;
  BTreePrinter.printWhitespaces(firstSpaces);
  List<Node<T>> newNodes = new ArrayList<Node<T>>();
  for (Node<T> node : nodes) {
   if (node != null) {
    System.out.print(node.data);
    newNodes.add(node.left);
    newNodes.add(node.right);
   } else {
    newNodes.add(null);
    newNodes.add(null);
    System.out.print(" ");
   }
   BTreePrinter.printWhitespaces(betweenSpaces);
  }
  System.out.println("");
  for (int i = 1; i <= endgeLines; i++) {
   for (int j = 0; j < nodes.size(); j++) {
    BTreePrinter.printWhitespaces(firstSpaces - i);
    if (nodes.get(j) == null) {
     BTreePrinter.printWhitespaces(endgeLines + endgeLines + i
       + 1);
     continue;
    }
    if (nodes.get(j).left != null)
     System.out.print("/");
    else
     BTreePrinter.printWhitespaces(1);
    BTreePrinter.printWhitespaces(i + i - 1);
    if (nodes.get(j).right != null)
     System.out.print("\\");
    else
     BTreePrinter.printWhitespaces(1);
    BTreePrinter.printWhitespaces(endgeLines + endgeLines - i);
   }
   System.out.println("");
  }
  printNodeInternal(newNodes, level + 1, maxLevel);
}
/**
*
* @param count
*/
private static void printWhitespaces(int count) {
  for (int i = 0; i < count; i++)
   System.out.print(" ");
}
/**
*
* @param node
* @return
*/
private static <T extends Comparable<?>> int maxLevel(Node<T> node) {
  if (node == null)
   return 0;
  return Math.max(BTreePrinter.maxLevel(node.left),
    BTreePrinter.maxLevel(node.right)) + 1;
}
/**
*
* @param list
* @return
*/
private static <T> boolean isAllElementsNull(List<T> list) {
  for (Object object : list) {
   if (object != null)
    return false;
  }
  return true;
}
}

Step 3

package com.kartik.sorting;
import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;
import com.kartik.sorting.tree.BTreePrinter;
import com.kartik.sorting.tree.Node;
/**
*
* @author MandalKC
*
*/
public class HeapSort {
private static int[] a;
private static int n;
private static int left;
private static int right;
private static int largest;
/**
*
* @param input
*/
private static void printNumbers(int[] input) {
  for (int i = 0; i < input.length; i++) {
   System.out.print(input[i] + ", ");
  }
  System.out.println("\n");
}
/**
*
* @param input
* @return
*/
public static Node<Integer> drawTree(int[] input) {
  Node<Integer> node = null;
  Map<String, Node<Integer>> mapNode = new HashMap<String, Node<Integer>>();
  int i = 0, c = 0;
  int count = 0;
  for (i = 0; i < input.length; i++) {
   if (i > 0) {
    for (c = 1; c <= square(i); c++) {
     String stringKey = "n" + i + c;
     if (count < input.length) {
      node = new Node<Integer>(input[count]);
      mapNode.put(stringKey, node);
     }
     count++;
    }
   } else {
    String stringKey = "n" + i + c;
    node = new Node<Integer>(input[count]);
    mapNode.put(stringKey, node);
    count++;
   }
  }
  Map<String, Node<Integer>> sortMapNode = new TreeMap<String, Node<Integer>>(
    mapNode);
  Node<Integer> root = null;
  Node<Integer> prent = null;
  int countVal = 1;
  int pointerCount = 0;
  for (Map.Entry<String, Node<Integer>> entry : sortMapNode.entrySet()) {
   String key = entry.getKey();
   char p = key.charAt(1);
   char q = key.charAt(2);
   int k = Integer.parseInt(String.valueOf(p));
   int k1 = Integer.parseInt(String.valueOf(p));
   int k2 = Integer.parseInt(String.valueOf(q));
   if (k > 0) {
    String newKey = null;
    if (k1 % 2 == 0) {
     if ((k1 + k2) % 2 == 0) {
      newKey = "n" + (k1 - 1) + (k2 / 2);
      prent = mapNode.get(newKey);
      prent.right = entry.getValue();
      countVal++;
      pointerCount++;
     } else {
      if (k2 % 2 == 0) {
       newKey = "n" + (k1 - 1) + (k2 / 2);
       prent = mapNode.get(newKey);
       prent.right = entry.getValue();
       countVal++;
       pointerCount++;
      } else {
       newKey = "n" + (k1 - 1) + countVal;
       prent = mapNode.get(newKey);
       prent.left = entry.getValue();
       pointerCount++;
      }
     }
    } else {
     if ((k1 + k2) % 2 == 0) {
      if (k1 == 1) {
       newKey = "n00";
       prent = mapNode.get(newKey);
       if (k2 == 1) {
        prent.left = entry.getValue();
       }
       pointerCount++;
      } else {
       newKey = "n" + (k1 - 1) + countVal;
       prent = mapNode.get(newKey);
       prent.left = entry.getValue();
       pointerCount++;
      }
     } else {
      if (k1 == 1) {
       newKey = "n00";
       prent = mapNode.get(newKey);
       if (k2 == 2) {
        prent.right = entry.getValue();
        countVal++;
       }
       pointerCount++;
      } else {
       if (k2 % 2 == 0) {
        newKey = "n" + (k1 - 1) + (k2 / 2);
        prent = mapNode.get(newKey);
        prent.right = entry.getValue();
        countVal++;
        pointerCount++;
       } else {
        newKey = "n" + (k1 - 1) + countVal;
        prent = mapNode.get(newKey);
        prent.left = entry.getValue();
        pointerCount++;
       }
      }
     }
    }
    if (pointerCount == square(k1)) {
     countVal = 1;
     pointerCount = 0;
    }
   } else {
    root = entry.getValue();
   }
  }
  return root;
}
/**
*
* @param a
* @return
*/
public static int square(int a) {
  int n = 1;
  for (int i = 0; i < a; i++) {
   n = n * 2;
  }
  return n;
}
/**
*
* @param a
*/
public static void buildheap(int[] a) {
  n = a.length - 1;
  for (int i = n / 2; i >= 0; i--) {
   maxheap(a, i);
  }
}
/**
*
* @param a
* @param i
*/
public static void maxheap(int[] a, int i) {
  left = 2 * i;
  right = 2 * i + 1;
  BTreePrinter.printNode(drawTree(a));
  printNumbers(a);
  if (left <= n && a[left] > a[i]) {
   largest = left;
  } else {
   largest = i;
  }
  if (right <= n && a[right] > a[largest]) {
   largest = right;
  }
  if (largest != i) {
   exchange(i, largest);
   maxheap(a, largest);
  }
}
/**
*
* @param i
* @param j
*/
public static void exchange(int i, int j) {
  int t = a[i];
  a[i] = a[j];
  a[j] = t;
}
/**
*
* @param myarray
*/
public static void sort(int[] myarray) {
  a = myarray;
  buildheap(a);
  for (int i = n; i > 0; i--) {
   exchange(0, i);
   n = n - 1;
   maxheap(a, 0);
  }
}
public static void main(String[] args) {
  int []numbers={18,55,2,93,1,23,10,66,12,7,54,45,3,43,23,56,77,99,11,88};
  //int []numbers={18,55,2,93,1,23,10,66,12,7,54,3,43,23,56,77,99,11,88};
  //int[] numbers = { 4, 14, 7, 9, 8, 23, 5, 66, 100 ,34,12,77};
  sort(numbers);
}
}

Output:

/ \

55 2

/ \ / \

93 1 23 10

/ \ / \ / \ / \

66 12 7 54 45 3 43 23

/ \ / \ /

56 77 99 11 88

18, 55, 2, 93, 1, 23, 10, 66, 12, 7, 54, 45, 3, 43, 23, 56, 77, 99, 11, 88,

/ \

55 2

/ \ / \

93 1 23 10

/ \ / \ / \ / \

66 12 88 54 45 3 43 23

/ \ / \ /

56 77 99 11 7

18, 55, 2, 93, 1, 23, 10, 66, 12, 88, 54, 45, 3, 43, 23, 56, 77, 99, 11, 7,

many more iteration you can run and see the result

Conclusion

This example provides a basic console-based textual representation of a Max-Heap binary tree. For more complex visualizations, you can use graphical libraries or tools that offer better visual representation capabilities.