Binary Tree in java(Generic)

H

HelpMe

Please help me.I want to make a binary tree in java.I started but
couldnot accomplish.Can anyone help me to complete .Reply soon
please.My Program is:-

import java.io.*;

interface Node {
T getData();
int getId();
}

interface BinTree<T> {
Node getLeft (Node n);
Node getRight (Node n);
Node[] leaves();
Node parent(Node n);
int numOfChildren(Node n);
}

class ArrayBinTree<T> implements BinTree<T> {
class ArrayBinTreeNode<T> implements Node {
T data;
int id;
T getData {return data;}
int getId {return id;}

}

ArrayBinTreeNode () { //default constructor
id = 0;
data = null;
}
ArrayBinTree (int s){ //copy constructor
id = s;
data = null;
}

Node[] tree;
int numOfNodes;
BinTree(int size) {
tree = new Node[size];
numOfNodes = 0;
}

Node getLeft(Node n) {
return tree [2*n.getId()+1];
}

Node getRight(Node n) {
return tree [2*n.getId()+2];
}
 
J

Jeff Higgins

HelpMe said:
Please help me.I want to make a binary tree in java.I started but
couldnot accomplish.Can anyone help me to complete .Reply soon
please.My Program is:-

not a program, as it's posted.

Start here:

public class BinaryTree {

Object root;
BinaryTree right;
BinaryTree left;

}

Forget about interfaces, polymorphism, and generics
until you can produce a plain old data structure, you
can add the fancy stuff later.

Here's a link that was helpful to me.
import java.io.*;

interface Node {
T getData();
int getId();
}

interface BinTree<T> {
Node getLeft (Node n);
Node getRight (Node n);
Node[] leaves();
Node parent(Node n);
int numOfChildren(Node n);
}

class ArrayBinTree<T> implements BinTree<T> {
class ArrayBinTreeNode<T> implements Node {
T data;
int id;
T getData {return data;}
int getId {return id;}

}

ArrayBinTreeNode () { //default constructor
id = 0;
data = null;
}
ArrayBinTree (int s){ //copy constructor
id = s;
data = null;
}

Node[] tree;
int numOfNodes;
BinTree(int size) {
tree = new Node[size];
numOfNodes = 0;
}

Node getLeft(Node n) {
return tree [2*n.getId()+1];
}

Node getRight(Node n) {
return tree [2*n.getId()+2];
}
 
J

Jeff Higgins

Jeff said:
not a program, as it's posted.

Start here:

public class BinaryTree {

Object root;
BinaryTree right;
BinaryTree left;

}

Forget about interfaces, polymorphism, and generics
until you can produce a plain old data structure, you
can add the fancy stuff later.

Here's a link that was helpful to me.
<http://www.brpreiss.com/books/opus5/html/book.html>

import java.io.Serializable;

@SuppressWarnings("unchecked")
public class Node
implements Cloneable, Serializable, Comparable {

private static final long serialVersionUID = 1L;

private final Comparable data;

public Node(Comparable data) {
this.data = data; }

public int height() {
// TODO
return -1; }

public int depth() {
// TODO
return -1; }

public Object getData() {
return data; }

public int compareTo(Object that) {
if(that instanceof Node) {
return this.data.compareTo(((Node)that).data);
} throw new ClassCastException(); }

@Override
protected Object clone()
throws CloneNotSupportedException {
return super.clone(); }

@Override
public String toString() {
return data.toString(); }
}


import java.io.Serializable;
import java.util.Iterator;

@SuppressWarnings("unused")
public class BinaryTree
implements Cloneable, Serializable {

private static final long serialVersionUID = 1L;

private Node root;
private BinaryTree right;
private BinaryTree left;

public BinaryTree(){};

public BinaryTree (Node root) {
this.root = root; }

public Node getRoot() {
return root; }

public int height() {
// TODO
return -1; }

private class PreOrderIterator
implements Iterator<Node> {

@Override
public boolean hasNext() {
// TODO
return false; }

@Override
public Node next() {
// TODO
return null; }

@Override
public void remove() {
// TODO
}
}
}


public class TestTree {

public static void main(String[] args) {

Node root = new Node("root");
BinaryTree tree = new BinaryTree(root);
System.out.println(tree.getRoot()); }

}


import java.io.*;

interface Node {
T getData();
int getId();
}

interface BinTree<T> {
Node getLeft (Node n);
Node getRight (Node n);
Node[] leaves();
Node parent(Node n);
int numOfChildren(Node n);
}

class ArrayBinTree<T> implements BinTree<T> {
class ArrayBinTreeNode<T> implements Node {
T data;
int id;
T getData {return data;}
int getId {return id;}

}

ArrayBinTreeNode () { //default constructor
id = 0;
data = null;
}
ArrayBinTree (int s){ //copy constructor
id = s;
data = null;
}

Node[] tree;
int numOfNodes;
BinTree(int size) {
tree = new Node[size];
numOfNodes = 0;
}

Node getLeft(Node n) {
return tree [2*n.getId()+1];
}

Node getRight(Node n) {
return tree [2*n.getId()+2];
}
 
L

Lew

Jeff said:
@SuppressWarnings("unchecked")
public class Node
implements Cloneable, Serializable, Comparable {

It would be fun to genericize this such that the "unchecked" warnings need not
be suppressed.
 
L

Lord Zoltar

Please help me.I want to make a binary tree in java.I started but
couldnot accomplish.Can anyone help me to complete .Reply soon
please.My Program is:-

The Java API has a TreeMap class. Would that suffice?
 
V

voorth

The Java API has a TreeMap class. Would that suffice?

I'm afraid not. The TreeMap is an implementation of SortedMap that
stores its keys in a Red-Black tree. It is not a tree implementation.
 
L

Lord Zoltar

I'm afraid not. The TreeMap is an implementation of SortedMap that
stores its keys in a Red-Black tree. It is not a tree implementation.

I'm pretty sure TreeMap is a tree implementation, as it implements a
Red-Black tree (and Red-Black trees are a form of binary search tree).
Do you need the actual source code for an implementation of a tree and
not just an API to use a tree implementation?
 
J

Jeff Higgins

Lew said:
public class Node implements Cloneable, Serializable,
Comparable <Node>
{
...

Oh! OK that's kinda neat, thanks.

import java.io.Serializable;

public class Node<T extends Comparable<T>>
implements Cloneable, Serializable, Comparable<Node<T>> {

private static final long serialVersionUID = 1L;

private final T data;

public Node(T data) {
this.data = data; }

public int height() {
// TODO
return -1; }

public int depth() {
// TODO
return -1; }

public T getData() {
return data; }

@Override
protected Object clone()
throws CloneNotSupportedException {
return super.clone(); }

@Override
public String toString() {
return data.toString(); }

@Override
public int compareTo(Node<T> that) {
return this.data.compareTo(that.data); }
}


import java.io.Serializable;
import java.util.Iterator;

@SuppressWarnings("unused")
public class BinaryTree<T extends Comparable<T>>
implements Cloneable, Serializable {

private static final long serialVersionUID = 1L;

private Node<T> root;
private BinaryTree<T> right;
private BinaryTree<T> left;

public BinaryTree() {};

public BinaryTree(Node<T> root) {
this.root = root; }

public Node<T> getRoot() {
return root; }

public int height() {
// TODO
return -1; }

private class PreOrderIterator
implements Iterator<Node<T>> {

@Override
public boolean hasNext() {
// TODO
return false; }

@Override
public Node<T> next() {
// TODO
return null; }

@Override
public void remove() {
// TODO
}
}
}


public class TestTree {

@SuppressWarnings("boxing")
public static void main(String[] args) {

Node<Integer> root =
new Node<Integer>(Integer.MAX_VALUE);
BinaryTree<Integer> tree =
new BinaryTree<Integer>(root);
System.out.println(tree.getRoot());
}
}
 
J

Jeff Higgins

Jeff said:
@SuppressWarnings("unused")
public class BinaryTree<T extends Comparable<T>>
implements Cloneable, Serializable {

private static final long serialVersionUID = 1L;

private Node<T> root;
Oops!

private BinaryTree<T> right;
private BinaryTree<T> left;
Should be:
private BinaryTree<Node<T>> right;
private BinaryTree<Node<T>> left;

Oops!
 
J

Jeff Higgins

Jeff said:
Should be:

No it shouldn't. Should be just as I first put.

HelpMe, in response to your email request:

Hey! what is the output.It gives like 2147483647.What output is this?
Where is 5 and zero.

There seems to be a 9 missing also. You'll have to blame that on the
powers of 2, and who ever defined Integer.MAX_VALUE.
See class TreeTest. Oops!
 
H

HelpMe

No it shouldn't. Should be just as I first put.

HelpMe, in response to your email request:

Hey! what is the output.It gives like 2147483647.What output is this?
Where is 5 and zero.

There seems to be a 9 missing also. You'll have to blame that on the
powers of 2, and who ever defined Integer.MAX_VALUE.
See class TreeTest. Oops!

Sir,I want to implement it using Array or Link,I mean either a array
based binary tree or link based.How should I proceed.
 
L

Lew

HelpMe said:
Sir,I want to implement it using Array or Link,I mean either a array
based binary tree or link based.How should I proceed.

Jeff Higgins's approach is the link-based one. Those instance variables
'right' and 'left' are the links.
 
J

Jeff Higgins

Lew said:
Jeff Higgins's approach is the link-based one. Those instance variables
'right' and 'left' are the links.

Just to expand a little on Lew's response.
(And to also note that the preliminary outline I've proposed
upthread hasn't yet any provisions for persistance of the tree.)
BTW, Lew. Thanks for the help with the generics angle.

According to the Wikipedia article:
Binary tree
<http://en.wikipedia.org/wiki/Binary_tree>

Binary trees can also be stored as an implicit data structure in arrays,
and if the tree is a complete binary tree, this method wastes no space.
In this compact arrangement, if a node has an index i, its children are
found at indices 2i + 1 and 2i + 2, while its parent (if any) is found at
index [(i - 1)/2] (assuming the root has index zero).

So, if you wish to use an array based storage mechanism you could
add an integer field called index to the Node class,
and an ArrayList field to the Binary tree class
and change the compareTo method to compare index.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,482
Members
44,901
Latest member
Noble71S45

Latest Threads

Top