Re: A link list based binary tree in java
Andrew Marcus writes:
I don't know how far it would help me.
Depends on what "it" is. If it is what I think it is, it would remove
a totally unnecessary hurdle from your way.
I tried to make a link list based binary tree following the book "data
structures and algorithms in java" By Michael T GoodRich and
Tamassia.I did all
but I wanted to implement a function to determine whether a particular
node exists or not.All I want to implement a function boolean
exists(node n).Can anyone help??My program is as follows:-
I suggest this working order:
(1) Make up your mind about the constructors: if they are _meant_ to
ignore their arguments, at _least_ rename the arguments so that
this intention is absolutely clear to the reader, or better,
remove the arguments altogether. Are nodes meant to contain both
"id" and "data"? (Does a tree of zero nodes make sense to you?
Is the tree meant to be ordered somehow? Binary trees often are.)
(2) Make the program complete and compilable, compile it and study
the error messages and act accordingly until the program compiles.
You may want to remove parts like the preorder method for now;
put them back when you can cope with the simpler parts.
(3) Add a _short_ and _simple_ main method to test it. Make it build
a tree with a single node. Compile and run. Make it build a tree
with _two_ nodes. Compile and run. Write a method that counts the
nodes and make the main method print its value. Compile and run.
import java.io.*;
Not used.
interface Node {
Object getData();
int getID();
}
class TreeEmptyException extends Exception {
TreeEmptyException(String message) {
super(message);
}
}
class LinkBinTree {
BinNode root;
int size;
LinkBinTree(Object O) {
root = new BinNode(0);
}
This constructor ignores its argument. If that is intentional, at
_least_ rename to argument; it could be "obj", it could be "_", it
could be "ignored", it could be _anything_ _except_ "O"; even "o"
might be tolerable. Preferably make it just LinkBinTree(), if you
don't use the argument at all.
If that 0 (zero) is meant to be O (oh), replace _both_ with something
sensible. And change the font you use when you write code so that you
can see the difference.
(You should indent the all following to make it clearer that it is
inside the LinkBinTree class.)
class BinNode implements Node {
int id;
BinNode left;
BinNode right;
Object data;
BinNode(int iden) {
id = iden;
left = null;
right = null;
data = null;
}
BinNode(Object O) {
id = 0;
left = null;
right = null;
data = null;
}
I wonder if you really want two different constructors, however.
Maybe you want one that takes two arguments, id and data? Just
wondering. In the code you show, data is always null.
public Object getData() {return data;}
public int getID() { return id;}
void addLeft(Object obj) {
BinNode b = new BinNode(obj);
left = b;
}
void addRight(Object obj) {
BinNode r = new BinNode(obj);
right = r;
}
These don't really _add_ to this node, they _replace_ whatever is
there. Might consider checking that the left or right node is missing
before the assignment, or rename the methods. At the moment, this is
minor. Your tree, however, has a field named "size" that is nowhere
maintained. I would remove that field for now.
BinNode addLeft(Node n,Object O) throws TreeEmptyException
{
if(!exists(n)) throw new TreeEmptyException("Tree doesn't
exists");
return n.addLeft(O);
}
BinNode addRight(Node n,Object O) throws TreeEmptyException{
if(!exists(n)) throw new TreeEmptyException("Tree doesn't
exists");
return n.addRight(O);
}
I'm not sure what the existence check is for. The methods have the
Node right there, so in that sense it certainly exists. Zoltar's
advice of implementing a "find" method is sound. Maybe you want here a
method that finds a Node with a given "id"?
(Those O's get ignored; see above.)
When you make this code to compile, you will find out that there is no
addLeft(Object) or addRight(Object) in the interface Node. Do you see
the two obvious ways to fix this? Your choice.
void preOrder(Node n) {
LinkQueueApp<Integer> q =new LinkQueueApp<Integer>();
int p=n.getID();
q.enqueue(p);
while(!q.isEmpty()) {
p =q.dequeue();
System.out.println("The pre-order is : "
+n.getData());
for(int i=p;(i==p+1) || (i==p+2)&&i<=size;i++)
q.enqueue(i);
}
}
I would remove this until simpler stuff works. And then I would use
this as an opportunity to learn recursive programming: count nodes,
print nodes in different orders without any auxiliary data structure.
Binary trees are great for that.
void boolean exists(Node n) {
if(Node == root) return;
else {
if(Node
Your code ends here. This last piece is very wrong -- there is no such
type as "void boolean", and other code expects this to return a
boolean, not just to return, and comparing a type, Node, to an object
is just nonsense -- but it may be best to simply throw it away and
write that "find" instead.
First make it complete and compilable. Then write a simple main
method, and do make it simple at first. Compile and run. Add pieces
and keep it compilable and runnable and comprehensible. You will
learn, and you may find that you enjoy the experience.