import java.util.ArrayList; import java.util.Scanner; import java.util.List; pub

Question

import java.util.ArrayList;

import java.util.Scanner;
import java.util.List;

public class BST{

class Node {
int data;
//TODO...
}

public static Node buildTree(List<Integer> A) {
//TODO
return null;
}

public static void preorder(Node root, ArrayList<Integer> result) {
//TODO
}

public static void inorder(Node root, ArrayList<Integer> result) {
//TODO
}

public static void postorder(Node root, ArrayList<Integer> result) {
//TODO
}

public static void levelorder(Node root, ArrayList<Integer> result) {
//TODO Add numbers in the order encountered in a breadth first search
// The numbers at a given level of the tree should print from left to right
// This may take some thought
}

public static ArrayList<Integer> preorder(Node root) {
ArrayList<Integer> result = new ArrayList<Integer>();
preorder(root, result);
return result;
}

public static ArrayList<Integer> inorder(Node root) {
ArrayList<Integer> result = new ArrayList<Integer>();
inorder(root, result);
return result;
}
  
public static ArrayList<Integer> postorder(Node root) {
ArrayList<Integer> result = new ArrayList<Integer>();
postorder(root, result);
return result;
}

public static ArrayList<Integer> levelorder(Node root) {
ArrayList<Integer> result = new ArrayList<Integer>();
levelorder(root, result);
return result;
}

public static void main(String[] args) {
//Test your code here

Scanner sc = new Scanner(System.in);

System.out.println("BST Test Program");
System.out.println("Enter numbers separated by whitespace.");
System.out.println("Type Ctrl+D when you are done.");
System.out.println("The program will print the numbers in preorder, inorder, and postorder, and levelorder.");

  
ArrayList<Integer> numbers = new ArrayList<Integer>();

while (sc.hasNextInt()){
numbers.add(sc.nextInt());
}

Node root = buildTree(numbers);

System.out.println("preorder:");
for (int i: preorder(root)){
System.out.print(" ");
System.out.print(i);
}
System.out.println();

System.out.println("inorder:");
for (int i: inorder(root)){
System.out.print(" ");
System.out.print(i);
}
System.out.println();

System.out.println("postorder:");
for (int i: postorder(root)){
System.out.print(" ");
System.out.print(i);
}
System.out.println();

System.out.println("levelorder:");
for (int i: levelorder(root)){
System.out.print(" ");
System.out.print(i);
}
System.out.println();

}
}

Explanation / Answer

import java.util.NoSuchElementException; public class BST { private Node root; // root of BST private class Node { private Key key; // sorted by key private Value val; // associated data private Node left, right; // left and right subtrees private int N; // number of nodes in subtree public Node(Key key, Value val, int N) { this.key = key; this.val = val; this.N = N; } } // is the symbol table empty? public boolean isEmpty() { return size() == 0; } // return number of key-value pairs in BST public int size() { return size(root); } // return number of key-value pairs in BST rooted at x private int size(Node x) { if (x == null) return 0; else return x.N; } /*********************************************************************** * Search BST for given key, and return associated value if found, * return null if not found ***********************************************************************/ // does there exist a key-value pair with given key? public boolean contains(Key key) { return get(key) != null; } // return value associated with the given key, or null if no such key exists public Value get(Key key) { return get(root, key); } private Value get(Node x, Key key) { if (x == null) return null; int cmp = key.compareTo(x.key); if (cmp < 0) return get(x.left, key); else if (cmp > 0) return get(x.right, key); else return x.val; } /*********************************************************************** * Insert key-value pair into BST * If key already exists, update with new value ***********************************************************************/ public void put(Key key, Value val) { if (val == null) { delete(key); return; } root = put(root, key, val); assert check(); } private Node put(Node x, Key key, Value val) { if (x == null) return new Node(key, val, 1); int cmp = key.compareTo(x.key); if (cmp < 0) x.left = put(x.left, key, val); else if (cmp > 0) x.right = put(x.right, key, val); else x.val = val; x.N = 1 + size(x.left) + size(x.right); return x; } /*********************************************************************** * Delete ***********************************************************************/ public void deleteMin() { if (isEmpty()) throw new NoSuchElementException("Symbol table underflow"); root = deleteMin(root); assert check(); } private Node deleteMin(Node x) { if (x.left == null) return x.right; x.left = deleteMin(x.left); x.N = size(x.left) + size(x.right) + 1; return x; } public void deleteMax() { if (isEmpty()) throw new NoSuchElementException("Symbol table underflow"); root = deleteMax(root); assert check(); } private Node deleteMax(Node x) { if (x.right == null) return x.left; x.right = deleteMax(x.right); x.N = size(x.left) + size(x.right) + 1; return x; } public void delete(Key key) { root = delete(root, key); assert check(); } private Node delete(Node x, Key key) { if (x == null) return null; int cmp = key.compareTo(x.key); if (cmp < 0) x.left = delete(x.left, key); else if (cmp > 0) x.right = delete(x.right, key); else { if (x.right == null) return x.left; if (x.left == null) return x.right; Node t = x; x = min(t.right); x.right = deleteMin(t.right); x.left = t.left; } x.N = size(x.left) + size(x.right) + 1; return x; } /*********************************************************************** * Min, max, floor, and ceiling ***********************************************************************/ public Key min() { if (isEmpty()) return null; return min(root).key; } private Node min(Node x) { if (x.left == null) return x; else return min(x.left); } public Key max() { if (isEmpty()) return null; return max(root).key; } private Node max(Node x) { if (x.right == null) return x; else return max(x.right); } public Key floor(Key key) { Node x = floor(root, key); if (x == null) return null; else return x.key; } private Node floor(Node x, Key key) { if (x == null) return null; int cmp = key.compareTo(x.key); if (cmp == 0) return x; if (cmp < 0) return floor(x.left, key); Node t = floor(x.right, key); if (t != null) return t; else return x; } public Key ceiling(Key key) { Node x = ceiling(root, key); if (x == null) return null; else return x.key; } private Node ceiling(Node x, Key key) { if (x == null) return null; int cmp = key.compareTo(x.key); if (cmp == 0) return x; if (cmp < 0) { Node t = ceiling(x.left, key); if (t != null) return t; else return x; } return ceiling(x.right, key); } /*********************************************************************** * Rank and selection ***********************************************************************/ public Key select(int k) { if (k < 0 || k >= size()) return null; Node x = select(root, k); return x.key; } // Return key of rank k. private Node select(Node x, int k) { if (x == null) return null; int t = size(x.left); if (t > k) return select(x.left, k); else if (t 0) return 1 + size(x.left) + rank(key, x.right); else return size(x.left); } /*********************************************************************** * Range count and range search. ***********************************************************************/ public Iterable keys() { return keys(min(), max()); } public Iterable keys(Key lo, Key hi) { Queue queue = new Queue(); keys(root, queue, lo, hi); return queue; } private void keys(Node x, Queue queue, Key lo, Key hi) { if (x == null) return; int cmplo = lo.compareTo(x.key); int cmphi = hi.compareTo(x.key); if (cmplo < 0) keys(x.left, queue, lo, hi); if (cmplo = 0) queue.enqueue(x.key); if (cmphi > 0) keys(x.right, queue, lo, hi); } public int size(Key lo, Key hi) { if (lo.compareTo(hi) > 0) return 0; if (contains(hi)) return rank(hi) - rank(lo) + 1; else return rank(hi) - rank(lo); } // height of this BST (one-node tree has height 0) public int height() { return height(root); } private int height(Node x) { if (x == null) return -1; return 1 + Math.max(height(x.left), height(x.right)); } // level order traversal public Iterable levelOrder() { Queue keys = new Queue(); Queue queue = new Queue(); queue.enqueue(root); while (!queue.isEmpty()) { Node x = queue.dequeue(); if (x == null) continue; keys.enqueue(x.key); queue.enqueue(x.left); queue.enqueue(x.right); } return keys; } /************************************************************************* * Check integrity of BST data structure *************************************************************************/ private boolean check() { if (!isBST()) StdOut.println("Not in symmetric order"); if (!isSizeConsistent()) StdOut.println("Subtree counts not consistent"); if (!isRankConsistent()) StdOut.println("Ranks not consistent"); return isBST() && isSizeConsistent() && isRankConsistent(); } // does this binary tree satisfy symmetric order? // Note: this test also ensures that data structure is a binary tree since order is strict private boolean isBST() { return isBST(root, null, null); } // is the tree rooted at x a BST with all keys strictly between min and max // (if min or max is null, treat as empty constraint) // Credit: Bob Dondero's elegant solution private boolean isBST(Node x, Key min, Key max) { if (x == null) return true; if (min != null && x.key.compareTo(min) = 0) return false; return isBST(x.left, min, x.key) && isBST(x.right, x.key, max); } // are the size fields correct? private boolean isSizeConsistent() { return isSizeConsistent(root); } private boolean isSizeConsistent(Node x) { if (x == null) return true; if (x.N != size(x.left) + size(x.right) + 1) return false; return isSizeConsistent(x.left) && isSizeConsistent(x.right); } // check that ranks are consistent private boolean isRankConsistent() { for (int i = 0; i

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

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