The following Program in java implements a BST. The BST node (TNode) contains a data part as well as two links to its right and left children. 1. Draw (using paper and pen) the BST that results from the insertion of the values 60,30, 20, 80, 15, 70, 90, 10, 25, 33 (in this order). These values are used by the program 2. Traverse the tree using preorder, inorder and postorder algorithms (using paper and pen) 3. Write the program in c++, follow its steps, then compile and run. - Compare the results to what you obtained in (2) above. - Try different values class TestBST { public static void main(String []args) { int i; int x[] = {60,30, 20, 80, 15, 70, 90, 10, 25, 33}; BST t = new BST(); for (i=0; i < 10; i++) { System.out.print(" Adding: "+x[i]+" to the BST "); t.insert(x[i]); } System.out.println("\nPreorder traversal result:"); t.preorder(t.root); System.out.println("\nInorder traversal result:"); t.inorder(t.root); System.out.println("\nPostorder traversal result:"); t.postorder(t.root); } } class TNode { TNode() { data = 0; left = null; right = null;} TNode(int d) { data = d; left = null; right = null;} public int getData() { return data;} public TNode getRight() { return right; } public TNode getLeft() { return left; } public void setRight(TNode tn) { right = tn; } public void setLeft(TNode tn) { left = tn; } private int data; private TNode right = null, left = null; } class BST { public BST() { root = null;} public boolean empty() { return (root == null); } public int getRoot() { return root.getData();} public void insert(int d) { TNode newNode = new TNode(d); if (empty()) { root = newNode; return; } TNode temp = root, parent = root; int direction = 0; // 0 left 1 right while (temp != null) { parent = temp; if (d > temp.getData()) { temp = temp.getRight(); direction = 1; } else { temp = temp.getLeft(); direction = 0; } } if (direction == 0) parent.setLeft(newNode); else parent.setRight(newNode); } void visit(TNode t) { System.out.print(" "+t.getData()+" "); } void inorder (TNode r) //yields ordered sequence { if (r !=null) { inorder(r.getLeft()); // L visit(r); // V inorder(r.getRight()); // R } } void preorder(TNode r) { if (r != null) { visit(r); // V preorder(r.getLeft()); // L preorder(r.getRight()); // R } } void postorder(TNode r) { if (r != null) { postorder(r.getLeft()); // L postorder(r.getRight()); // R visit (r); // V } } public TNode root = null ; }
The following Program in java implements a BST. The BST node (TNode) contains a data part as well as two links to its right and left children.
1. Draw (using paper and pen) the BST that results from the insertion of the values 60,30, 20, 80, 15, 70, 90, 10, 25, 33 (in this order). These values are used by the program
2. Traverse the tree using preorder, inorder and postorder
3. Write the program in c++, follow its steps, then compile and run.
- Compare the results to what you obtained in (2) above.
- Try different values
class TestBST
{
public static void main(String []args)
{
int i;
int x[] = {60,30, 20, 80, 15, 70, 90, 10, 25, 33};
BST t = new BST();
for (i=0; i < 10; i++)
{
System.out.print(" Adding: "+x[i]+" to the BST ");
t.insert(x[i]);
}
System.out.println("\nPreorder traversal result:");
t.preorder(t.root);
System.out.println("\nInorder traversal result:");
t.inorder(t.root);
System.out.println("\nPostorder traversal result:");
t.postorder(t.root);
}
}
class TNode
{
TNode()
{ data = 0; left = null; right = null;}
TNode(int d)
{ data = d; left = null; right = null;}
public int getData()
{ return data;}
public TNode getRight()
{ return right; }
public TNode getLeft()
{ return left; }
public void setRight(TNode tn)
{ right = tn; }
public void setLeft(TNode tn)
{ left = tn; }
private int data;
private TNode right = null, left = null;
}
class BST
{
public BST() { root = null;}
public boolean empty() { return (root == null); }
public int getRoot() { return root.getData();}
public void insert(int d)
{
TNode newNode = new TNode(d);
if (empty())
{
root = newNode;
return;
}
TNode temp = root, parent = root;
int direction = 0; // 0 left 1 right
while (temp != null)
{
parent = temp;
if (d > temp.getData())
{
temp = temp.getRight();
direction = 1;
}
else
{
temp = temp.getLeft();
direction = 0;
}
}
if (direction == 0)
parent.setLeft(newNode);
else
parent.setRight(newNode);
}
void visit(TNode t)
{
System.out.print(" "+t.getData()+" ");
}
void inorder (TNode r) //yields ordered sequence
{
if (r !=null)
{
inorder(r.getLeft()); // L
visit(r); // V
inorder(r.getRight()); // R
}
}
void preorder(TNode r)
{
if (r != null)
{
visit(r); // V
preorder(r.getLeft()); // L
preorder(r.getRight()); // R
}
}
void postorder(TNode r)
{
if (r != null)
{
postorder(r.getLeft()); // L
postorder(r.getRight()); // R
visit (r); // V
}
}
public TNode root = null ;
}
Step by step
Solved in 4 steps with 4 images
