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 }

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 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