iven codes: ------------------------------------------------------------------------------------ //Node.java public class Node{ protected String data; protected Node left; protected Node right; public Node(String data){ this(data, null, null); } public Node(String data, Node left, Node right){ this.data = data; this.left = left; this.right = right; }
Given codes:
------------------------------------------------------------------------------------
//Node.java
public class Node{
protected String data;
protected Node left;
protected Node right;
public Node(String data){
this(data, null, null);
}
public Node(String data, Node left, Node right){
this.data = data;
this.left = left;
this.right = right;
}
public String getData(){return this.data;}
public Node getLeft(){ return this.left;}
public Node getRight(){ return this.right;}
public void setData(String s){ this.data = s;}
public void setLeft(Node left){ this.left = left;}
public void setRight(Node right){ this.right = right;}
public void setLeftRight(Node left, Node right){
this.left = left;
this.right = right;
}
public void setAll(String data, Node left, Node right){
this.data = data;
this.left = left;
this.right = right;
}
}
------------------------------------------------------------------------------------
//PrintBinaryTree.java
public class PrintBinaryTree{
public static boolean alt_display = !false;
public static String toString(BinaryTree bt){
return toString(bt.getRoot(), new StringBuilder(), true, new StringBuilder()).toString();
}
public static void print(BinaryTree bt){
System.out.println( toString(bt) );
}
public static StringBuilder toString(Node root, StringBuilder prefix, boolean isTail, StringBuilder sb) {
if(root == null){return sb;}
if(root.getRight() != null) {
toString(root.getRight(), new StringBuilder().append(prefix).append(isTail ? "| " : " "), false, sb);
}
if(alt_display){
sb.append(prefix).append(isTail ? "\\-- " : "/-- ").append(root.getData().toString()).append("\n");
}else{
sb.append(prefix).append(isTail ? "└── " : "┌── ").append(root.getData().toString()).append("\n");
}
if(root.getLeft() != null) {
toString(root.getLeft(), new StringBuilder().append(prefix).append(isTail ? " " : "| "), true, sb);
}
return sb;
}
}
------------------------------------------------------------------
looking to make changes to these codes:
//BinaryTree.java
import java.io.File;
import java.util.Scanner;
public class BinaryTree {
protected Node root = null;
protected int size = 0;
public BinaryTree(){
size = 0;
}
public BinaryTree(String s){
root = new Node(s);
size = 1;
}
public int getSize(){ return this.size; }
public Node getRoot(){ return this.root; }
public boolean contains(String target){
if( root == null ){ return false; }
if( root.getData().equals(target) ){
return true;
}
return false;
}
public void loadFromFile(String fname){
BinaryTree bt = new BinaryTree();
try{
Scanner file = new Scanner( new File(fname) );
while( file.hasNextLine()){
bt.add(file.nextLine().strip());
}
}catch(Exception e){
System.out.println("Something went wrong!!");
}
this.root = bt.root;
this.size = bt.size;
}
public void add(String s){
addRandom(s);
}
/* add a node in a random place in the tree. */
private void addRandom(String s){
if(root == null && size == 0){
root = new Node(s);
}else{
Node tmp = root;
boolean left = Math.random() < 0.5;
Node child = left ? tmp.getLeft() : tmp.getRight();
while(child != null){
tmp = child;
left = Math.random() < 0.5;
child = left ? tmp.getLeft() : tmp.getRight();
}
// assert: child == null
// yea! we have a place to add s
if(left){
tmp.setLeft(new Node(s));
}else{
tmp.setRight(new Node(s));
}
}
size += 1;
}
/** Computes the height of the binary tree
*
* The height is the length of the longest path from
* the root of the tree to any other node.
*
* @return the height of the tree
*/
public final int height(){
if( root == null ){ return -1; }
if( size == 1){ return 0; }
return heightRecursive(root);
}
protected final static int heightRecursive(Node root){
if( root == null ){
return -1;
}
int leftHeight = heightRecursive(root.getLeft());
int rightHeight = heightRecursive(root.getRight());
if( leftHeight < rightHeight){
return 1 + rightHeight;
}else{
return 1 + leftHeight;
}
}
public static void main(String[] args){
BinaryTree t = new BinaryTree("cat");
System.out.println("height = " + t.height() + ", size = " + t.getSize());
t.add("dog");
t.add("eel");
t.add("cow");
t.add("rat");
System.out.println("height = " + t.height() + ", size = " + t.getSize());
System.out.println(t);
System.out.println("height = " + t.height() + ", size = " + t.getSize());
t.loadFromFile("sample.txt");
System.out.println(t);
}
@Override
public String toString() {
return PrintBinaryTree.toString(this);
}
}
-------------------------------------------------------------------------
//BST
public class BST extends BinaryTree{
// You MUST have a zero argument constructor that
// creates an empty binary search tree
// You can can add code to this if you want (or leave it alone).
// We will create all BSTs for testing using this constructor
public BST(){}
@Override
public boolean contains(String s){
return false;
}
@Override
public void add(String s){
}
public BST makeBalanced(){
return null;
}
public boolean saveToFile(String fname){
return false;
}
}
Step by step
Solved in 2 steps
