Tree Traversals

In the code for Topic 5 (Trees), the implementation of BinaryTree includes a method for in-order traversalof the tree, printing out each node as it is visited.

The main() method in BinaryTreeDemo creates a binary tree manually of height 3, displays statistics, and performs an in-order traversal.

For this assignment, you have to make the following changes to the code:

Part 1: Add methods implementing pre-order and post-order traversals to the BinaryTree class, as described in the lecture notes. (6 marks: 3 for pre-order and 3 for post-order).

Part 2: Add a method implementing breadth-first traversal of the BinaryTree class, as was discussed in lectures see additional notes below. (6 marks)

Part 3: Create a binary tree of height 4 and test your code for pre-order, post-order and breadth-first traversals on it. Present the test results in your report. To get full marks for your testing, you must describe clearly how you verified that your traversals are correct. Diagrams and accompanying explanations may help. (8 marks)

Information on breadth-first traversal:

This is more complicated than depth-first traversal. As discussed in lectures, the general procedure is a non-recursive one in which you use a Queue to keep track of the order in which to visit nodes:

1. Begin with the root node on the queue

2. At each iteration, dequeue the node at the head of the queue, and enqueue its children to the end of the queue (if it has any), and visit the removed node

3. Repeat this until the queue is empty

you may opt to use the standard library class java.util.ArrayList as the queue: remove(0) removes the item at index 0 (head), while add(el) adds the specified element to the end of the ArrayList. Youll need to use the notation for generics.

public class BinaryTree implements BinaryTreeInterface, java.io.Serializable { private static final long serialVersionUID = -1932834476575953631L; private BinaryNodeInterface root; public BinaryTree() { root = null; } // end default constructor public BinaryTree(T rootData) { root = new BinaryNode(rootData); } // end constructor public BinaryTree(T rootData, BinaryTree leftTree, BinaryTree rightTree) { privateSetTree(rootData, leftTree, rightTree); } // end constructor public void setTree(T rootData) { root = new BinaryNode(rootData); } // end setTree public void setTree(T rootData, BinaryTreeInterface leftTree, BinaryTreeInterface rightTree) { privateSetTree(rootData, (BinaryTree)leftTree, (BinaryTree)rightTree); } // end setTree // 26.08 private void privateSetTree(T rootData, BinaryTree leftTree, BinaryTree rightTree) { root = new BinaryNode(rootData); if ((leftTree != null) && !leftTree.isEmpty()) root.setLeftChild(leftTree.root); if ((rightTree != null) && !rightTree.isEmpty()) { if (rightTree != leftTree) root.setRightChild(rightTree.root); else root.setRightChild(rightTree.root.copy()); } // end if if ((leftTree != null) && (leftTree != this)) leftTree.clear(); if ((rightTree != null) && (rightTree != this)) rightTree.clear(); } // end privateSetTree private BinaryNode copyNodes() // not essential { return (BinaryNode)root.copy(); } // end copyNodes // 26.09 public T getRootData() { T rootData = null; if (root != null) rootData = root.getData(); return rootData; } // end getRootData // 26.09 public boolean isEmpty() { return root == null; } // end isEmpty // 26.09 public void clear() { root = null; } // end clear // 26.09 protected void setRootData(T rootData) { root.setData(rootData); } // end setRootData // 26.09 protected void setRootNode(BinaryNodeInterface rootNode) { root = rootNode; } // end setRootNode // 26.09 protected BinaryNodeInterface getRootNode() { return root; } // end getRootNode // 26.10 public int getHeight() { return root.getHeight(); } // end getHeight // 26.10 public int getNumberOfNodes() { return root.getNumberOfNodes(); } // end getNumberOfNodes // 26.12 public void inorderTraverse() { inorderTraverse(root); } // end inorderTraverse private void inorderTraverse(BinaryNodeInterface node) { if (node != null) { inorderTraverse(node.getLeftChild()); System.out.println(node.getData()); inorderTraverse(node.getRightChild()); } // end if } // end inorderTraverse } // end BinaryTree

public class BinaryTreeDemo { public static void main(String[] args) { // Create a tree System.out.println("Constructing a test tree ..."); BinaryTree testTree = new BinaryTree(); createTree1(testTree); // Display some statistics about it System.out.println(" Some statistics about the test tree ..."); displayStats(testTree); // Perform in-order traversal System.out.println(" In-order traversal of the test tree, printing each node when visiting it ..."); testTree.inorderTraverse(); } // end of main public static void createTree1(BinaryTree tree) { // To create a tree, build it up from the bottom: // create subtree for each leaf, then create subtrees linking them, // until we reach the root. System.out.println(" Creating a treee that looks like this: "); System.out.println(" A "); System.out.println(" / \\ "); // '\\' is the escape character for backslash System.out.println(" B C "); System.out.println(" / \\ / \\"); System.out.println("D E F G "); System.out.println(); // First the leaves BinaryTree dTree = new BinaryTree(); dTree.setTree("D"); // neater to use the constructor the initialisation ... BinaryTree eTree = new BinaryTree("E"); BinaryTree fTree = new BinaryTree("F"); BinaryTree gTree = new BinaryTree("G"); // Now the subtrees joining leaves: BinaryTree bTree = new BinaryTree("B", dTree, eTree); BinaryTree cTree = new BinaryTree("C", fTree, gTree); // Now the root tree.setTree("A", bTree, cTree); } // end createTree1 public static void displayStats(BinaryTree tree) { if (tree.isEmpty()) System.out.println("The tree is empty"); else System.out.println("The tree is not empty"); System.out.println("Root of tree is " + tree.getRootData()); System.out.println("Height of tree is " + tree.getHeight()); System.out.println("No. of nodes in tree is " + tree.getNumberOfNodes()); } // end displayStats }

public interface BinaryTreeInterface extends TreeInterface { /** Task: Sets an existing binary tree to a new one-node binary tree. * @param rootData an object that is the data in the new trees root */ public void setTree(T rootData); /** Task: Sets an existing binary tree to a new binary tree. * @param rootData an object that is the data in the new trees root * @param leftTree the left subtree of the new tree * @param rightTree the right subtree of the new tree */ public void setTree(T rootData, BinaryTreeInterface leftTree, BinaryTreeInterface rightTree); } // end BinaryTreeInterface

public interface TreeInterface { public T getRootData(); public int getHeight(); public int getNumberOfNodes(); public boolean isEmpty(); public void clear(); } // end TreeInterface

interface BinaryNodeInterface { /** Task: Retrieves the data portion of the node. * @return the object in the data portion of the node */ public T getData(); /** Task: Sets the data portion of the node. * @param newData the data object */ public void setData(T newData); /** Task: Retrieves the left child of the node. * @return the node that is this nodes left child */ public BinaryNodeInterface getLeftChild(); /** Task: Retrieves the right child of the node. * @return the node that is this nodes right child */ public BinaryNodeInterface getRightChild(); /** Task: Sets the nodes left child to a given node. * @param leftChild a node that will be the left child */ public void setLeftChild(BinaryNodeInterface leftChild); /** Task: Sets the nodes right child to a given node. * @param rightChild a node that will be the right child */ public void setRightChild(BinaryNodeInterface rightChild); /** Task: Detects whether the node has a left child. * @return true if the node has a left child */ public boolean hasLeftChild(); /** Task: Detects whether the node has a right child. * @return true if the node has a right child */ public boolean hasRightChild(); /** Task: Detects whether the node is a leaf. * @return true if the node is a leaf */ public boolean isLeaf(); /** Task: Counts the nodes in the subtree rooted at this node. * @return the number of nodes in the subtree rooted at this node */ public int getNumberOfNodes(); /** Task: Computes the height of the subtree rooted at this node. * @return the height of the subtree rooted at this node */ public int getHeight(); /** Task: Copies the subtree rooted at this node. * @return the root of a copy of the subtree rooted at this node */ public BinaryNodeInterface copy(); } // end BinaryNodeInterface

class BinaryNode implements BinaryNodeInterface, java.io.Serializable { private static final long serialVersionUID = 6828929352995534482L; // needed for serializable objects private T data; private BinaryNode left; private BinaryNode right; public BinaryNode() { this(null); // call next constructor } // end default constructor public BinaryNode(T dataPortion) { this(dataPortion, null, null); // call next constructor } // end constructor public BinaryNode(T dataPortion, BinaryNode leftChild, BinaryNode rightChild) { data = dataPortion; left = leftChild; right = rightChild; } // end constructor public T getData() { return data; } // end getData public void setData(T newData) { data = newData; } // end setData public BinaryNodeInterface getLeftChild() { return left; } // end getLeftChild public BinaryNodeInterface getRightChild() { return right; } // end getRightChild public void setLeftChild(BinaryNodeInterface leftChild) { left = (BinaryNode)leftChild; } // end setLeftChild public void setRightChild(BinaryNodeInterface rightChild) { right = (BinaryNode)rightChild; } // end setRightChild public boolean hasLeftChild() { return left != null; } // end hasLeftChild public boolean hasRightChild() { return right != null; } // end hasRightChild public boolean isLeaf() { return (left == null) && (right == null); } // end isLeaf // 26.06 public BinaryNodeInterface copy() { BinaryNode newRoot = new BinaryNode(data); if (left != null) newRoot.left = (BinaryNode)left.copy(); if (right != null) newRoot.right = (BinaryNode)right.copy(); return newRoot; } // end copy // 26.11 public int getHeight() { return getHeight(this); // call private getHeight } // end getHeight // 26.11 private int getHeight(BinaryNode node) { int height = 0; if (node != null) height = 1 + Math.max(getHeight(node.left), getHeight(node.right)); return height; } // end getHeight // 26.11 public int getNumberOfNodes() { int leftNumber = 0; int rightNumber = 0; if (left != null) leftNumber = left.getNumberOfNodes(); if (right != null) rightNumber = right.getNumberOfNodes(); return 1 + leftNumber + rightNumber; } // end getNumberOfNodes } // end BinaryNode

if there is any code needed let me know

For post-order traversal: visit root after visiting the subtrees This is the classic depth-first traversal algorithm, though Pre-Order and In-Order are also depth-first Algorithm postOrder(v) for each child w of v postOrder (w) 10 visiv) 4