Topic: Tree Traversal for Binary Search Tree

Policy: $1)$ Each lab is due at the end of each allocated Lab Section. The TA will be available at

HUM$301$ to help you for the lab$/$homework$.$

$2)$ Exception: if you plan to do the lab in advance, you must submit your lab answer before the

start of your allocated lab section.

Instruction:

$1.$ A java file is provided, please finish the required methods. You will be writing code in

the BST class to add more functionalities to it$.$

Questions:

$1.$ Write a method, public boolean search $($Comparable e$,$ BNode b$),$ that searches

for a key, e$,$ in a binary search tree. Think recursively. If root is null, or if root.data is

same as e$,$ the result is obvious. Otherwise, decide if you should search in the left subtree

or the right subtree, and this is where recursion comes in$.$

$2.$ Write a method, public void inorderscan$($BNode b$),$ that prints the in$-$order traversal of

the binary search tree.

$3.$ Write a method, public void preorderscan$($BNode b$),$ that prints the pre$-$order traversal of

the binary search tree.

$4.$ Write a method, public void postorderscan$($BNode b$),$ that prints the post$-$order traversal

of the binary search tree. Example Code: public class lab$3$CS$3\{$

public static void main$($String$[]$ args$)\{$

Integer a$1=9$;

Integer a$2=7$;

Integer a$3=-1$;

Integer a$4=-7$;

Integer a$5=1$;

Integer a$6=13$;

Integer a$7=2$;

Integer a$8=3$;

Integer a$9=8$;

Integer a$10=-10$;

Integer a$11=10$;

BST bst$=$new BST$($new BNode$($a$1))$;

bst$.$insert$($a$2)$;

bst$.$insert$($a$3)$;

bst$.$insert$($a$4)$;

bst$.$insert$($a$5)$;

bst$.$insert$($a$6)$;

bst$.$insert$($a$7)$;

bst$.$insert$($a$8)$;

bst$.$insert$($a$9)$;

bst$.$insert$($a$10)$;

bst$.$insert$($a$11)$;

System.out.println$("---$inorder Scan$----$should give $-10-7-11237891013----")$;

bst$.$inorderscan$()$;

System.out.println$()$;

System.out.println$("---$preorder Scan$---$should give $97-1-7-1012381310-------")$;

bst$.$preorderscan$()$;

System.out.println$()$;

System.out.println$("---$postorder Scan$---$should give $-10-7321-18710139-------")$;

bst$.$postorderscan$()$;

System.out.println$()$;

System.out.println$("$Height of the tree: $"+$bst$.$height$())$;

System.out.println$()$;

System.out.print$("$Enter an int to search for: $")$;

java.util.Scanner sc$=$ new java.util.Scanner$($System$.$in$)$;

int p$=$sc$.$nextInt$()$;

if$($bst$.$search$($p$,$ bst$.$root$))\{$

System.out.println$("$Found$")$;

$\}$

else$\{$

System.out.println$("$Not Found"$)$;

$\}$

$\}$

$\}$

$//$Class of Binary Search Tree, finish the methods in this class

class BST $\{$

BNode root;

public BST$($BNode r$)\{$

root$=$r;

$\}$

public BST$()\{$

root$=$null;

$\}$

public void insert$($Comparable e$)\{//$insert node with data e

if $($root$==$null$)$ root$=$ new BNode$($e$)$;

else$\{$

if $($root$.$getData$().$compareTo$(($Integer$)$ e$)>0)\{$

$/*$root$.$data is bigger, insert e into left subtree $*/$

insertNode$($e$,$ root$)$;

$\}$

else $\{$

$/*$root$.$data is smaller, insert e into right subtree $*/$

insertNode$($e$,$ root$)$;

$\}$

$\}$

$\}$

public void insertNode$($Comparable e$,$ BNode b$)\{$

if $($b$.$getData$().$compareTo$(($Integer$)$ e$)>0)\{$

if$($b$.$left$==$null$)\{$

b$.$setLeft$($new BNode$($e$))$;

$\}$

else$\{$

insertNode$($e$,$ b$.$left$)$;

$\}$

$\}$

else$\{$

if$($b$.$right$==$null$)\{$

b$.$setRight$($new BNode$($e$))$;

$\}$

else$\{$

insertNode$($e$,$ b$.$right$)$;

$\}$

$\}$

$\}$

public int height$($BNode b$)\{//$height of the tree, this has been finished for you

if$($b$==$null$)\{$

return $0$;

$\}$

if$($b$.$left $==$ null && b$.$right $==$ null$)\{$

return $1$;

$\}$

int lheight$=$height$($b$.$left$)$;

int rheight$=$height$($b$.$right$)$;

return $1+$ Math.max$($lheight$,$ rheight$)$;

$\}$

public int height$()\{$

return height$($this$.$root$)$;

$\}$

public boolean search $($Comparable e$,$ BNode b$)\{$

return false;

$\}$

public void inorderscan$($BNode b$)\{//$in$-$order scan of the tree

$\}$

public void inorderscan$()\{$

this.inorderscan$($this$.$root$)$;

$\}$

public void preorderscan$($BNode b$)\{//$pre$-$order scan of the tree

$\}$

public void preorderscan$()\{$

this.preorderscan$($this$.$root$)$;

$\}$

public void postorderscan$($BNode b$)\{//$post$-$order scan of the tree

$\}$

public void postorderscan$()\{$

this.postorderscan$($this$.$root$)$;

$\}$

$\}$

$//$Binary Node

class BNode $\{$

public Comparable data;

public BNode left;

public BNode right;

public BNode$($Comparable data$)\{$

this.data$=$data;

this.left$=$null;

this.right$=$null;

$\}$

public BNode$($Comparable data, BNode l$,$ BNode r$)\{$

this.data$=$data;

left$=$l;

right$=$r;

$\}$

public void setData$($Comparable data$)\{$

this.data$=$data;

$\}$