Implement a binary tree using array as underline storage
+ root at index 1,
+ left child at parent's (index * 2)
+ right child at patent's (index * 2 + 1)
+ parent is at child's (index / 2)
1. building a binary tree using array
2. implement tree traversals: pre-order, in-order, post-order, level-order
3. implement insert method that insert the element in the order of insertion
[
4. modify the insert method so the tree is a BST
5. add a method called "contains" to search for an element in the tree
6. add methods findMin and findMax
]
*/
I am stuck can you help me to complete the implementation
public class ArrTree {
public static int DEFAULT_SIZE = 20;
//constructors
public ArrTree(){
this.buffer = new int[DEFAULT_SIZE];
this.size = 0;
}
public ArrTree(int n){ //create a tree with the given size n
this.buffer = new int[n+1];
this.size = 0; //empty tree
}
//mutators
public boolean insert(int v){
if(this.size < this.buffer.length){
this.buffer[++this.size] = v;
return true;
}
return false; // cannot insert the value
}
//methods
//traverse the tree in-order fashion - this is the interface for the user
public String preOrder(){
return doPreOrder(1); //start at the root
}
//this is the actual code handling the pre-order traversal
private String doPreOrder(int v){
if(v <= this.size){
return this.buffer[v] + " " +
doPreOrder(v*2) +
doPreOrder(v*2+1);
}else{ //nothing to do ==> extends out of the leaf
return "";
}
}
//attributes
private int buffer[];
private int size;
//===================================
//Driver to test the tree
public static void main(String[] args){
ArrTree t = new ArrTree(50);
for(int i = 0; i < 10; i++)
t.insert(i);
System.out.println(t.preOrder());
}
}