# Binary Tree

Hey,
i have to do a couple of things i did the most of the coding but at the compile unfortunately it returns errors that i cannot locate.

1)
public class BT1 {

class BinaryNode<T> {
T value;
BinaryNode<T> left;
BinaryNode<T> right;

}
public class BinaryTree<T>
{
private BinaryNode<T> root;
public BinaryTree()
{
root = null;
}
}

public class BinaryTree2<T>
{
private BinaryNode2<T> root;
public BinaryTree2()
{
root = null;
}
}
//Count Leaves of the BinaryTree1
public static int countLeaves(BinaryNode node)
{
if (node == null)
return 0;
else if (node.left == null && node.right == null)
return 1;
else
return countLeaves(node.left) + countLeaves(node.right);
}
//Count nodes from BinaryTree1 that have exactly one child
public static int countNodesOne(BinaryNode node)
{
if (node == null)
{
return 0;
}
else
{

int leftCount = countNodesOne(node.left = 1);
int rightCount = countNodesOne(node.right = 1);
return leftCount + rightCount;
}
}
//Count nodes from BinaryTree1 that have two child
//i.e count all nodes
public static int countNodes(BinaryNode node)
{
if (node == null)
{
return 0;
}
else
{
int leftCount = countNodes(node.left);
int rightCount = countNodes(node.right);
return 1+ leftCount+ rightCount;
}
}
//It checks if BinaryTree is equal to BinaryTree2
public boolean sameTree(BinaryTree other)
{
return (sameTree(root, other.root) );
}

boolean sameTree(BinaryNode a, BinaryNode2 b)
{
if (a == null && b == null) return true;

else if (a != null && b != null){
return(BinaryNode.data == BinaryNode2.data && sameTree(BinaryNode.left, BinaryNode2.left) &&
sameTree(BinaryNode.right, BinaryNode2.right));
}

else
return false;
}
}

2)

public class BT2\$1{

class BinaryNode<T> {
T value;
BinaryNode<T> left;
BinaryNode<T> right;
int leftSize;

}
public class BinaryTree<T>
{
public  BinaryNode root;
public BinaryTree()
{
root = null;
}

public Object search (int k)
{
BinaryNode currentNode = root;
while (currentNode != null){
if (k==currentNode.leftSize)
//CANNOT FIND CLASS SEARCHDATA
return ((SearchData)currentNode.data).element;
if (k<currentNode = currentNode.leftSize)
currentNode = currentNode.leftChild;
else {
k -= currentNode.leftSize;
currentNode = currentNode.rightChild;
}
}
return null;
}
}
}

3) It asks to add the elements of an unsorted array to a binary tree;
Does it mean heap sort???

Another one point on this exercise it requires to take two integers and print all the values in the tree between these two numbers [???]

Any help is appreciable

###### Who is Participating?

[Webinar] Streamline your web hosting managementRegister Today

x

Commented:

/*
BinaryTree.java

A simple binary tree implementation
MAH 10/14/01

*/

public class BinaryTree {

// instance variables
private String name;        // data to store in the node
private  int        value;       // data to store in the node
private  BinaryTree left;
private BinaryTree right;

// constructor
BinaryTree () {
name = "default";
value  = 0;
left = null;
right = null;
}

// constructor
BinaryTree (String n, int v) {
name = n;
value = v;
left = null;
right = null;
}

// constructor
BinaryTree (String n, int v, BinaryTree l, BinaryTree r) {
name = n;
value = v;
left = l;
right = r;
}

// For
public void setSubtrees(BinaryTree l, BinaryTree r) {

this.left = l;
this.right = r;
}

// two different ways to implement the iterative form

public void printLeftIterative (BinaryTree t) {

BinaryTree temp = t;
while (temp != null) {
System.out.println(temp.name);
temp = temp.left;
}
}

public void printLeftIterative () {
BinaryTree temp = this;
while (temp != null) {
System.out.println(temp.name);
temp = temp.left;
}
}

// two ways to do the recursive form

public void printLeftRecursive (BinaryTree t) {

if (t != null) {
System.out.println(t.name);
printLeftRecursive(t.left);
}
}

public void printLeftRecursive () {

System.out.println(this.name);
if (this.left != null) {
BinaryTree temp = this.left;
temp.printLeftRecursive();
}
}

// preorder (tree v)    visit each node before its children
// visit (v);
// for each child w of v,
//     preorder (w)

// note: we don't need to check for this being null --
// the method can't have been called on a null object

public void printPreOrder () {

System.out.println(this.name);

if (this.left != null)
this.left.printPreOrder();

if (this.right != null)
this.right.printPreOrder();

}

// inorder(tree v)   visit the left subtree, visit v, visit the right subtree

public void printInOrder () {

if (this.left != null)
this.left.printInOrder();

System.out.println(this.name);

if (this.right != null)
this.right.printInOrder();
}

public void printPostOrder () {

if (this.left != null)
this.left.printPostOrder();

if (this.right != null)
this.right.printPostOrder();

System.out.println(this.name);

}

// for a tree, Depth First Traversal is equivalent to preorder traversal

public void printDFS() {
printPreOrder();
}

//  Depth First Search: Here we are looking for a particular object
// When we find the node that matches the name, we will return the
// value stored at that node.  If the node is not found we'll return -1

public int searchDFS(String name) {

int val = -1;
if (this.name.equals(name))
return this.value;           // this ends the method

if (this.left != null)
val = this.left.searchDFS(name);

if (val > -1) return val;     // if found, skip the right side

if (this.right != null)
val = this.right.searchDFS(name);

return val;
}

/* Breadth First Traversal is different than the others --
it requires us to keep track of information about which
nodes have been visited so far.  We can use our Queue!
Two methods work together here.
Note: this is not recursive
*/

private void printBFSHelper(Queue queue) {

BinaryTree t;
// this is for debugging only
//  System.out.println("Contents of the queue");
//  queue.printQueue();

while ((t = (BinaryTree) queue.deQueue()) != null) {

System.out.println(t.name);
if (t.left != null)
queue.enQueue(t.left);

if (t.right != null)
queue.enQueue(t.right);

}
}

// The main work is done by printBFSHelper
public void printBFS() {

Queue queue = new Queue();
queue.enQueue(this);
printBFSHelper(queue);
}

public static void main (String args[]) {

BinaryTree root = new BinaryTree("root", 0);
BinaryTree a      = new BinaryTree("a", 1);
BinaryTree b        = new BinaryTree("b", 1);
root.setSubtrees(a, b);
a.setSubtrees(new BinaryTree("aa",2), new BinaryTree("ab",2));
a.left.setSubtrees(new BinaryTree("aaa",3), new BinaryTree("aab",3));

System.out.println("Printing left subtrees recursively");
root.printLeftRecursive(root);
System.out.println("Printing left subtrees recursively another way");
root.printLeftRecursive();

System.out.println("Printing InOrder");
root.printInOrder();
System.out.println("Printing PreOrder");
root.printPreOrder();
System.out.println("Printing PostOrder");
root.printPostOrder();
System.out.println("Printing BFS");
root.printBFS();

System.out.println("Searching for " + "aa " + root.searchDFS("aa"));
System.out.println("Searching for " + "bb " + root.searchDFS("bb"));
}

}
0

Author Commented:
Thanks for the code but im still getting errors :S
In that code i want to have to binary trees which in the BinaryTree2 i want to count all the nodes that have ONE CHILD but it returns an error ".class expected"
another thing is that i want to compare the two binary trees i've the code but i don't know if its correct.
if anyone can tell me what's going wrong it 'd be appreciable !

Also in the second part of code snippet, this code i want to return the node with the smallest value
but the point is that i cant figure out if its going to return just the value or the node.

and at the end can anyone tell me if the placing of an unsorted array to a binary tree is the heapsort ???

class BinaryTree {

// instance variables
private String name;        // data to store in the node
private  int        value;       // data to store in the node
private  BinaryTree left;
private BinaryTree right;

// constructor
BinaryTree () {
name = "default";
value  = 0;
left = null;
right = null;
}

// constructor
BinaryTree (String n, int v) {
name = n;
value = v;
left = null;
right = null;
}

// constructor
BinaryTree (String n, int v, BinaryTree l, BinaryTree r) {
name = n;
value = v;
left = l;
right = r;
}

// For
public void setSubtrees(BinaryTree l, BinaryTree r) {

this.left = l;
this.right = r;
}

public static void main (String args[]) {

BinaryTree root = new BinaryTree("root", 0);
BinaryTree a      = new BinaryTree("a", 1);
BinaryTree b        = new BinaryTree("b", 1);
root.setSubtrees(a, b);
a.setSubtrees(new BinaryTree("aa",2), new BinaryTree("ab",2));
a.left.setSubtrees(new BinaryTree("aaa",3), new BinaryTree("aab",3));

}
}

public class BinaryTree2 {

// instance variables
private String name;        // data to store in the node
private  int        value;       // data to store in the node
private  BinaryTree2 left;
private BinaryTree2 right;

// constructor
BinaryTree2 () {
name = "default";
value  = 0;
left = null;
right = null;
}

// constructor
BinaryTree2 (String n, int v) {
name = n;
value = v;
left = null;
right = null;
}

// constructor
BinaryTree2 (String n, int v, BinaryTree2 l, BinaryTree2 r) {
name = n;
value = v;
left = l;
right = r;
}

public void printLeftRecursive (BinaryTree2 t) {

if (t != null) {
System.out.println(t.name);
printLeftRecursive(t.left);
}
}

public void printLeftRecursive () {

System.out.println(this.name);
if (this.left != null) {
BinaryTree2 temp = this.left;
temp.printLeftRecursive();
}
}

public void setSubtrees(BinaryTree2 l, BinaryTree2 r) {

this.left = l;
this.right = r;
}

//Count Leaves of the BinaryTree1
public static int countLeaves(BinaryTree2 node)
{
if (node == null)
return 0;
else if (node.left == null && node.right == null)
return 1;
else
return countLeaves(node.left) + countLeaves(node.right);
}

//Count nodes from BinaryTree1 that have exactly one child
public static int countNodesOne(BinaryTree2 node)
{
if (node == null)
{
return 0;
}
else
{
if (int leftCount = countNodesOne(node.left = 1))
{
else if (int rightCount = countNodesOne(node.right = 1)
{
return leftCount + rightCount;
}
}
}
}

//Count nodes from BinaryTree1 that have two children
//i.e count all nodes
public static int countNodes(BinaryTree2 node)
{
if (node == null)
{
return 0;
}
else
{
int leftCount = countNodes(node.left);
int rightCount = countNodes(node.right);
return 1+ leftCount + rightCount;
}
}

//It checks if BinaryTree is equal to BinaryTree2
public boolean sameTree(BinaryTree2 other)
{
return (sameTree(root, other.root) );
}

boolean sameTree(BinaryTree2 a, BinaryTree b)
{
if (a == null && b == null) return true;

else if (a != null && b != null){
return(BinaryTree2.data == BinaryTree.data && sameTree(BinaryTree2.left, BinaryTree.left) &&
sameTree(BinaryTree2.right, BinaryTree.right));
}

else
return false;
}
}

public static void main (String args[]) {

BinaryTree2 root = new BinaryTree2("root", 0);
BinaryTree2 a      = new BinaryTree2("a", 1);
BinaryTree2 b        = new BinaryTree2("b", 1);
root.setSubtrees(a, b);
a.setSubtrees(new BinaryTree2("aa",2), new BinaryTree2("ab",2));
a.left.setSubtrees(new BinaryTree2("aaa",3), new BinaryTree2("aab",3));

System.out.println("Printing left subtrees recursively");
root.printLeftRecursive(root);
System.out.println("Printing left subtrees recursively another way");
root.printLeftRecursive();

}

}

//  FIND THE NODE WITH THE SMALLEST VALUE

public class BinaryTree {

// instance variables
private String name;        // data to store in the node
private  int        value;       // data to store in the node
private  BinaryTree left;
private BinaryTree right;

// constructor
BinaryTree () {
name = "default";
value  = 0;
left = null;
right = null;
}

// constructor
BinaryTree (String n, int v) {
name = n;
value = v;
left = null;
right = null;
}

// constructor
BinaryTree (String n, int v, BinaryTree l, BinaryTree r) {
name = n;
value = v;
left = l;
right = r;
}

// For
public void setSubtrees(BinaryTree l, BinaryTree r) {

this.left = l;
this.right = r;
}

public static void main (String args[]) {

BinaryTree root = new BinaryTree("root", 0);
BinaryTree a      = new BinaryTree("a", 1);
BinaryTree b        = new BinaryTree("b", 1);
root.setSubtrees(a, b);
a.setSubtrees(new BinaryTree("aa",2), new BinaryTree("ab",2));
a.left.setSubtrees(new BinaryTree("aaa",3), new BinaryTree("aab",3));

}

protected BinaryTree findMin( BinaryTree value ) {
if( value != null )
while( value.left != null )
value = value.left;

return value;
}
}
0

Author Commented:
can anyone tell me what's going wrong ?????????????????????????????
0