Member Avatar for sam.udo

i was asked to create a binary tree,populate it with the elements of a given array,sort it and output the items in the tree using post order,i can handle the rest except the populating of the tree with the elements of a given array since i was asked to insert the arrays' elements into the binary tree with respect to the way they appear in the array without following the normal rule of item insertion in a binary tree i.e assuming there exist an array(int[]a) such that 2,5,36,7,78,4 are members of the array(ordered form) then i should also make sure that the nodes of the binary tree are of the same order...e.g A[0] = 2,A[1] = 5,A[2] = 36...A[5] = 4 then for the binary tree root = 2,root.left = 5,root.right = 36,root.left.left =7,root.right.right=78 e.t.c , i need a help or better still a sample code on how to write this stuff.........

  • 3 Contributors
  • 2 Replies
  • 252 Views
  • 7 Hours Discussion Span
  • Latest Post Latest Post by Taywin

Dani AI

Generated

Quick clarification for : the requested insertion order is the heap/level-order mapping of an array into a binary tree, not the value-based BST insertion shown by . For a zero-based array the rule is:

  • node at index i has left child at 2i + 1 and right child at 2i + 2.

That produces A[0] = root, A[1] = root.left, A[2] = root.right, A[3] = root.left.left, etc. (The example in the original post mixes one index — with {2,5,36,7,78,4} the element 78 at index 4 is root.left.right, not root.right.right.)

A compact Java implementation that builds the array-ordered tree and prints post-order:

public class ArrayToBinaryTree {
  static class Node { int val; Node left, right; Node(int v){ val = v; } }

  static Node build(int[] a, int i) {
    if (a == null || i >= a.length) return null;
    Node n = new Node(a[i]);
    n.left = build(a, 2*i + 1);
    n.right = build(a, 2*i + 2);
    return n;
  }

  static void postOrder(Node n) {
    if (n == null) return;
    postOrder(n.left);
    postOrder(n.right);
    System.out.println(n.val);
  }

  public static void main(String[] args) {
    int[] a = {2,5,36,7,78,4};
    Node root = build(a, 0);
    postOrder(root);
  }
}

Alternative (iterative) construction: create a Node[] of the same length, instantiate nodes for every non-null entry, then link children by indices (left = 2i+1, right = 2i+2). Complexity is O(n) time and O(n) memory.

Notes and pitfalls: post-order does not produce a sorted sequence — if sorting is required, use value-based insertion (a BST) followed by in-order traversal (this is the behavior ’s example implements). As noted, manually implementing the build and traversal helps understanding more than copy-pasting. Edge cases: check for empty/null arrays, use Integer[] and skip null elements if holes are needed, and be aware of array-index bounds when linking children.

Recommended Answers

All 2 Replies

Member Avatar for msi_333

This code snippet should help

public class BinaryTreeTest {

  public static void main(String[] args) {
    new BinaryTreeTest().run();
  }

  static class Node {
    Node left;

    Node right;

    int value;

    public Node(int value) {
      this.value = value;
    }
  }

  public void run() {
    // build the simple tree from chapter 11.
    Node root = new Node(5);
    System.out.println("Binary Tree Example");
    System.out.println("Building tree with root value " + root.value);
    insert(root, 1);
    insert(root, 8);
    insert(root, 6);
    insert(root, 3);
    insert(root, 9);
    System.out.println("Traversing tree in order");
    printInOrder(root);
    System.out.println("Traversing tree front-to-back from location 7");
    printFrontToBack(root, 7);
  }

  public void insert(Node node, int value) {
    if (value < node.value) {
      if (node.left != null) {
        insert(node.left, value);
      } else {
        System.out.println("  Inserted " + value + " to left of "
            + node.value);
        node.left = new Node(value);
      }
    } else if (value > node.value) {
      if (node.right != null) {
        insert(node.right, value);
      } else {
        System.out.println("  Inserted " + value + " to right of "
            + node.value);
        node.right = new Node(value);
      }
    }
  }

  public void printInOrder(Node node) {
    if (node != null) {
      printInOrder(node.left);
      System.out.println("  Traversed " + node.value);
      printInOrder(node.right);
    }
  }

  /**
   * uses in-order traversal when the origin is less than the node's value
   * 
   * uses reverse-order traversal when the origin is greater than the node's
   * order
   */
  public void printFrontToBack(Node node, int camera) {
    if (node == null)
      return;
    if (node.value > camera) {
      // print in order
      printFrontToBack(node.left, camera);
      System.out.println("  Traversed " + node.value);
      printFrontToBack(node.right, camera);
    } else if (node.value < camera) {
      // print reverse order
      printFrontToBack(node.right, camera);
      System.out.println("  Traversed " + node.value);
      printFrontToBack(node.left, camera);
    } else {
      // order doesn't matter
      printFrontToBack(node.left, camera);
      printFrontToBack(node.right, camera);
    }
  }

}
Member Avatar for Taywin

(-_-) You are killing him in a long run... How would he actually learn how to implement? Reading other people's code doesn't really help learning but more on copying... Also, giving code like this would just keep leading him to your approach while his may not be this way at all...

Edited by Taywin because: n/a
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.