Binary Tree help


Joined
Oct 6, 2009
Messages
1
Reaction score
0
Using the codes below.....

Add the following methods to BinaryTree.java and implement them.

/**
* Prints the level order traversal of the binary tree.
*/
public void printLevelOrderTraversal() {
}

/**
* Checks if this binary tree and other binary tree are structurally identical
*/
public boolean sameTree(BinaryTree<T> other) {
}

/**
* Changes the structure of the binary tree into its mirror image
*
*/
public void mirror() {
}

_______________________________________________________

BinaryTree.java

public class BinaryTree<T> {
private BTNode<T> root; // root of the binary tree

/**
* Initializes the binary tree
*/
public BinaryTree() {
root = null;
}

/**
* Initializes the binary tree
*
* @param key the key of the root of the binary tree
* @param leftSubtree the left subtree of the node
* @param rightSubtree the right subtree of the node
*/
public BinaryTree(T key, BTNode<T> leftSubtree, BTNode<T> rightSubtree) {
root = new BTNode<T>(key, leftSubtree, rightSubtree);
}

/**
* Checks if the binary tree is empty
* @return true if the binary tree is empty. Otherwise, false.
*/
public boolean isEmpty() {
return (root == null);
}

/**
* Determines the number of nodes in the binary tree
*
* @return the number of the nodes in the binary tree
*/
public int size() {
return size(root);
}

/**
* Recursive way of getting the nodes of a binary tree
*
* @param node root of the binary tree
* @return the number of descendants of the the node
*/
private int size(BTNode<T> node) {
if (node == null) {
return 0;
}
else {
return (size(node.getLeftChild()) + 1 + size(node.getRightChild()));
}
}

/**
* Determine the height of the binary tree
* @return height of the binary tree
*/
public int height() {
return height(root);
}

private int height(BTNode<T> node) {
if (node == null) {
return -1;
}
else {
int lDepth = height(node.getLeftChild());
int rDepth = height(node.getRightChild());

return (Math.max(lDepth, rDepth) + 1);
}
}

/**
* Prints the preorder traversal of the binary tree.
*/
public void printPreorder() {
printPreorder(root);
}

private void printPreorder(BTNode<T> node) {
if (node != null) {
System.out.print(node + " ");
printPreorder(node.getLeftChild());
printPreorder(node.getRightChild());
}
}

/**
* Prints the postorder traversal of the binary tree
*/
public void printPostorder() {
printPostorder(root);
}

private void printPostorder(BTNode<T> node) {
if (node != null) {
printPostorder(node.getLeftChild());
printPostorder(node.getRightChild());
System.out.print(node + " ");
}
}

/**
* Prints the inorder traversal of the binary tree
*/
public void printInorder() {
printInorder(root);
}

private void printInorder(BTNode<T> node) {
if (node != null) {
printInorder(node.getLeftChild());
System.out.print(node + " ");
printInorder(node.getRightChild());
}
}

/**
* Prints the converse preorder traversal of the binary tree.
*/
public void printConversePreorder() {
printConversePreorder(root);
}

private void printConversePreorder(BTNode<T> node) {
if (node != null) {
System.out.print(node + " ");
printConversePreorder(node.getRightChild());
printConversePreorder(node.getLeftChild());
}
}

/**
* Prints the converse inorder traversal of the binary tree.
*/
public void printConverseInorder() {
printConverseInorder(root);
}

private void printConverseInorder(BTNode<T> node) {
if (node != null) {
printConverseInorder(node.getRightChild());
System.out.print(node + " ");
printConverseInorder(node.getLeftChild());
}
}

/**
* Prints the converse postorder traversal of the binary tree.
*/
public void printConversePostorder() {
printConversePostorder(root);
}

private void printConversePostorder(BTNode<T> node) {
if (node != null) {
printConversePostorder(node.getRightChild());
printConversePostorder(node.getLeftChild());
System.out.print(node + " ");
}
}
}

_______________________________________________________________

BinaryTreeUnitTest.java


import junit.framework.TestCase;


public class BinaryTreeUnitTest extends TestCase {
public void testBasicCase() {
BTNode<Character> o = new BTNode<Character>('o', null, null);
BTNode<Character> r = new BTNode<Character>('r', null, null);
BTNode<Character> m = new BTNode<Character>('m', null, null);
BTNode<Character> g = new BTNode<Character>('g', o, r);
BTNode<Character> i = new BTNode<Character>('i', null, null);
BTNode<Character> h = new BTNode<Character>('h', null, m);
BTNode<Character> s = new BTNode<Character>('s', null, null);
BTNode<Character> l = new BTNode<Character>('l', g, i);
BTNode<Character> t = new BTNode<Character>('t', h, s);

BinaryTree<Character> tree = new BinaryTree<Character>('a', l, t);

assertEquals(10, tree.size());
assertEquals(3, tree.height());

tree.printPreorder();
System.out.println();
tree.printInorder();
System.out.println();
tree.printPostorder();
System.out.println();
tree.printConversePreorder();
System.out.println();
tree.printConverseInorder();
System.out.println();
tree.printConversePostorder();
}
}

_______________________________________________________

BTNode.java

/**
* Node class for binary class.
*
* @author Richard Bryann Chua
*
*/
public class BTNode<T> {
private T element; // holds the key or element of the node
private BTNode leftChild; // left child of the node
private BTNode rightChild; // right child of the node
private BTNode parent; // parent of the node

/**
* Initializes with the element, left child and right child
* set to null.
*/
public BTNode() {
this(null, null, null, null);
}

/**
* Initializes the node
*
* @param element the key of the node
* @param leftChild the left child of the node
* @param rightChild the right child of the node
*/
public BTNode(T element, BTNode leftChild, BTNode rightChild) {
this(element, leftChild, rightChild, null);
}

/**
* Initializes the node
*
* @param element the key of the node
* @param leftChild the left child of the node
* @param rightChild the right child of the node
* @param parent the parent of the node
*/
public BTNode(T element, BTNode leftChild, BTNode rightChild, BTNode parent) {
this.element = element;
this.leftChild = leftChild;
this.rightChild = rightChild;
this.parent = parent;
}


/**
* @return the element or key of the node
*/
public T getElement() {
return element;
}

/**
*
* @return the left child of the node
*/
public BTNode getLeftChild() {
return leftChild;
}

/**
*
* @return the right child of the node
*/
public BTNode getRightChild() {
return rightChild;
}

/**
* Changes the key or element of the node
*
* @param element the new key or element of the node
*/
public void setElement(T element) {
this.element = element;
}

/**
* Changes the left child of the node
*
* @param leftChild the new left child of the node
*/
public void setLeftChild(BTNode leftChild) {
this.leftChild = leftChild;
}

/**
* Changes the right child of the node
*
* @param rightChild the new right child of the node
*/
public void setRightChild(BTNode rightChild) {
this.rightChild = rightChild;
}

@Override
public String toString() {
return ("{" + element + "}");
}
}

________________________________________________________________

BTNodeUnitTest.java

import junit.framework.TestCase;


public class BTNodeUnitTest extends TestCase {

public void testBasicCase() {
BTNode<String> node = new BTNode<String>("Richard", null, null);
assertEquals("Richard", node.getElement());

BTNode<Integer> node1 = new BTNode<Integer>(10, null, null);
assertEquals(10, node1.getElement().intValue());
}

}
 
Ad

Advertisements


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

Top