Modify the class BinarySearchTree so that it contains the toString method, inste

Question

Modify the class BinarySearchTree so that it contains the toString method, instead of the display method that was given originally.

public class BinarySearchTree
{
public BinarySearchTree()
{
root = new Node(); //dummy node as the root
root.setLeftChild(null);
root.setRightChild(null);
root.setInfo(-1);
}

public boolean isEmpty()
{
return root.getLeftChild()==null;
}

public void display()
{
inorderDisplay(root.getLeftChild());
System.out.println();
}

public boolean contains(int x)
{
return search(x, root.getLeftChild());
}

public void add(int x)
{
if (root.getLeftChild() == null)
{
Node p = new Node();
p.setNode(x, null, null);
root.setLeftChild(p);
}
else insert(x, root.getLeftChild());
}

public int getMin()
{
return getMin(root);
}

private Node root;

private void inorderDisplay(Node p)
{
if (p != null)
{
inorderDisplay(p.getLeftChild());
System.out.print(p.getInfo() + " ");
inorderDisplay(p.getRightChild());
}
}

private boolean search(int x, Node p)
{
if (p == null) return false;
else
if (x == p.getInfo()) return true;
else
if (x < p.getInfo()) return search(x, p.getLeftChild());
else return search(x, p.getRightChild());
}


private void insert(int x, Node p)
{
if (x < p.getInfo())
if (p.getLeftChild() == null)
{
Node q = new Node();
q.setNode(x, null, null);
p.setLeftChild(q);
}
else insert(x, p.getLeftChild());
else
if (p.getRightChild() == null)
{
Node q = new Node();
q.setNode(x, null, null);
p.setRightChild(q);
}
else insert(x, p.getRightChild());
}

private int getMin(Node p)
{
if (p.getLeftChild() == null) return p.getInfo();
else return getMin(p.getLeftChild());
}
}
 

Here is the node:

class Node
{
 Node()
 {
  info = 0;
  left = right = null;
 }

 void setNode(int x, Node l, Node r)
 {
  info = x;
  left = l;
  right = r;
 }

 int getInfo()
 {
  return info;
 }

 Node getLeftChild()
 {
  return left;
 }

 Node getRightChild()
 {
  return right;
 }

 void setInfo(int x)
 {
  info = x;
 }

 void setLeftChild(Node l)
 {
  left = l;
 }

 void setRightChild(Node r)
 {
  right = r;
 }

 private int info;
 private Node left;
 private Node right;
}

Here is the Main:

public class Main
{
 public static void main(String[] args)
 {
  BinarySearchTree bst = new BinarySearchTree();
  for (int i=0; i < 10; i++)
  {
   int x = (int)(Math.random()*100);
   System.out.print(x + " ");
   bst.add(x);
  }

  System.out.println();
  bst.display();
 }
}

Explanation / Answer

//I included the whole code because of the import statment but the ToString method is all you need.

import java.util.Stack;

public class BinarySearchTree
{
    public BinarySearchTree()
    {
        root = new Node(); //dummy node as the root
        root.setLeftChild(null);
        root.setRightChild(null);
        root.setInfo(-1);
    }

    public boolean isEmpty()
    {
        return root.getLeftChild()==null;
    }
    public String toString(){
        String str="";
        Stack<Node> stack=new Stack<Node>();
        Node tmp =root.getLeftChild();
        if (tmp==null){
            return "";
        }
        stack.push(tmp);

        while(!stack.isEmpty()){
            if(tmp==null){
                tmp=stack.pop();
                str=str + " "+ (new Integer(tmp.getInfo()).toString());
                tmp=tmp.getRightChild();
            } else {
                stack.push(tmp);
                tmp=tmp.getLeftChild();
            }
        }
        return str.trim().substring(0,str.length()-(new Integer(root.getLeftChild().getInfo()).toString().length()+1));
    }
   
    public void display()
    {
        inorderDisplay(root.getLeftChild());
        System.out.println();
    }

    public boolean contains(int x)
    {
        return search(x, root.getLeftChild());
    }

    public void add(int x)
    {
        if (root.getLeftChild() == null)
        {
            Node p = new Node();
            p.setNode(x, null, null);
            root.setLeftChild(p);
        }
        else insert(x, root.getLeftChild());
    }

    public int getMin()
    {
        return getMin(root);
    }

    private Node root;

    private void inorderDisplay(Node p)
    {
        if (p != null)
        {
            inorderDisplay(p.getLeftChild());
            System.out.print(p.getInfo() + " ");
            inorderDisplay(p.getRightChild());
        }
    }

    private boolean search(int x, Node p)
    {
        if (p == null) return false;
        else
            if (x == p.getInfo()) return true;
            else
                if (x < p.getInfo()) return search(x, p.getLeftChild());
                else return search(x, p.getRightChild());
    }


    private void insert(int x, Node p)
    {
        if (x < p.getInfo())
            if (p.getLeftChild() == null)
            {
                Node q = new Node();
                q.setNode(x, null, null);
                p.setLeftChild(q);
            }
            else insert(x, p.getLeftChild());
        else
            if (p.getRightChild() == null)
            {
                Node q = new Node();
                q.setNode(x, null, null);
                p.setRightChild(q);
            }
            else insert(x, p.getRightChild());
    }

    private int getMin(Node p)
    {
        if (p.getLeftChild() == null) return p.getInfo();
        else return getMin(p.getLeftChild());
    }
}

Related Questions

Navigate

• Browse (All)
• Browse M
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.