I\'m supposed to write a program that implements a binary tree. The program has
ID: 3603478 • Letter: I
Question
I'm supposed to write a program that implements a binary tree. The program has to use an array and fill the elements from the array into a tree structure.
This is what I have so far:
Class 1:
public class Node {
private int value;
private Node left;
private Node right;
private boolean isRoot=false;
public Node(int value){
this.value=value;
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
}
public boolean isRoot() {
return isRoot;
}
public void setRoot(boolean isRoot) {
this.isRoot = isRoot;
}
}
Class 2:
public class Tree {
public Tree(int[] array){
Node root= new Node(array[0]);
root.setRoot(true);
Node current=root;
int level=0;
for(int i=1;i<=array.length;i++){
if(array[i]>current.getValue()){
current.setLeft(new Node(array[i]));
current=current.getLeft();
level++;
}
else{
current.setRight(new Node(array[i]));
current=current.getRight();
level++;
}
}
}
}
I'm not too sure what to do after this and I need some help.
Explanation / Answer
Here is the working solution
public class BinaryTree {
Node root;
// Tree Node
class Node {
int data;
Node left, right;
Node(int data)
{
this.data = data;
this.left = this.right = null;
}
}
// Function to insert nodes in level order
public Node insertfromArray(int[] arr, Node root,
int i)
{
// Base case for recursion
if (i < arr.length) {
Node temp = new Node(arr[i]);
root = temp;
// insert left child
root.left = insertfromArray(arr, root.left,
2 * i + 1);
// insert right child
root.right = insertfromArray(arr, root.right,
2 * i + 2);
}
return root;
}
// Function to print tree nodes in PreOrder fashion
public void preOrder(Node root){
if (root != null) {
System.out.print(root.data + " ");
preOrder(root.left);
preOrder(root.right);
}
}
// Function to print tree nodes in InOrder fashion
public void inOrder(Node root)
{
if (root != null) {
inOrder(root.left);
System.out.print(root.data + " ");
inOrder(root.right);
}
}
// Function to print tree nodes in PostOrder fashion
public void PostOrder(Node root){
if (root != null) {
PostOrder(root.left);
PostOrder(root.right);
System.out.print(root.data + " ");
}
}
// Driver program to test above function
public static void main(String args[])
{
BinaryTree t2 = new BinaryTree();
int arr[] = { 5, 8, 9, -2, 7 }; // you can use scanner to get input from user
t2.root = t2.insertfromArray(arr, t2.root, 0); // first element is the root
t2.inOrder(t2.root);
System.out.println(" ");
t2.preOrder(t2.root);
System.out.println(" ");
t2.PostOrder(t2.root);
}
}
while returning it should be this.left
similary for others, you have stated to convert array of integers to binary tree but in your code you are trying to construct a binary search tree
binary tree doesnt compare the values where binary search tree does
i am giving you code for binary search tree also
class Node {
int data;
Node left, right;
Node(int d) {
data = d;
left = right = null;
}
}
class Index {
int index = 0;
}
class BinaryTree {
Index index = new Index();
// A recursive function to construct BST from pre[]. preIndex is used
// to keep track of index in pre[].
Node constructTreeUtil(int pre[], Index preIndex, int key,
int min, int max, int size) {
// Base case
if (preIndex.index >= size) {
return null;
}
Node root = null;
// If current element of pre[] is in range, then
// only it is part of current subtree
if (key > min && key < max) {
// Allocate memory for root of this subtree and increment *preIndex
root = new Node(key);
preIndex.index = preIndex.index + 1;
if (preIndex.index < size) {
// Contruct the subtree under root
// All nodes which are in range {min .. key} will go in left
// subtree, and first such node will be root of left subtree.
root.left = constructTreeUtil(pre, preIndex, pre[preIndex.index],
min, key, size);
// All nodes which are in range {key..max} will go in right
// subtree, and first such node will be root of right subtree.
root.right = constructTreeUtil(pre, preIndex, pre[preIndex.index],
key, max, size);
}
}
return root;
}
// The main function to construct BST from given preorder traversal.
// This function mainly uses constructTreeUtil()
Node constructTree(int pre[], int size) {
int preIndex = 0;
return constructTreeUtil(pre, index, pre[0], Integer.MIN_VALUE,
Integer.MAX_VALUE, size);
}
// A utility function to print inorder traversal of a Binary Tree
void printInorder(Node node) {
if (node == null) {
return;
}
printInorder(node.left);
System.out.print(node.data + " ");
printInorder(node.right);
}
// Driver program to test above functions
public static void main(String[] args) {
BinaryTree tree = new BinaryTree();
int pre[] = new int[]{10, 5, 1, 7, 40, 50};
int size = pre.length;
Node root = tree.constructTree(pre, size);
System.out.println("Inorder traversal of the constructed tree is ");
tree.printInorder(root);
}
}