Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.Iterator;
- public class BSTRefBased extends AbstractBinaryTree
- implements Iterable<WordRefs>
- {
- private TreeNode root;
- public BSTRefBased() {
- }
- public BSTRefBased(WordRefs item,
- AbstractBinaryTree left,
- AbstractBinaryTree right)
- {
- root = new TreeNode(item, null, null);
- if (left != null) {
- attachLeftSubtree(left);
- }
- if (right != null) {
- attachRightSubtree(right);
- }
- }
- public boolean isEmpty() {
- return (root == null);
- }
- public void makeEmpty() {
- root = null;
- }
- protected TreeNode getRoot() {
- return root;
- }
- protected void setRoot(TreeNode r) {
- this.root = r;
- }
- public WordRefs getRootItem() throws TreeException {
- if (root == null) {
- throw new TreeException("getRootItem() on empty tree");
- }
- return root.item;
- }
- public void setRootItem(WordRefs item) {
- if (root == null) {
- root = new TreeNode(item);
- } else {
- root.item = item;
- }
- }
- public void attachLeft(WordRefs item) throws TreeException {
- if (isEmpty()) {
- throw new TreeException("attachLeft to empty tree");
- }
- if (!isEmpty() && root.left != null) {
- throw new TreeException("attachLeft to occupied left child");
- }
- root.left = new TreeNode(item, null, null);
- return;
- }
- public void attachLeftSubtree(AbstractBinaryTree left) {
- if (isEmpty()) {
- throw new TreeException("attachLeftSubtree to empty tree");
- }
- if (!isEmpty() && root.left != null) {
- throw new
- TreeException("attachLeftSubtree to occupied right child");
- }
- root.left = left.getRoot();
- left.makeEmpty();
- return;
- }
- public void attachRight(WordRefs item) throws TreeException {
- if (isEmpty()) {
- throw new TreeException("attachRight to empty tree");
- }
- if (!isEmpty() && root.right != null) {
- throw new TreeException("attachRight to occupied right child");
- }
- root.right = new TreeNode(item, null, null);
- return;
- }
- public void attachRightSubtree(AbstractBinaryTree right) {
- if (isEmpty()) {
- throw new TreeException("attachRightSubtree to empty tree");
- }
- if (!isEmpty() && root.right != null) {
- throw new
- TreeException("attachRightSubtree to occupied right child");
- }
- root.right = right.getRoot();
- right.makeEmpty();
- return;
- }
- public AbstractBinaryTree detachLeftSubtree()
- throws TreeException
- {
- if (root == null) {
- throw new TreeException("detachLeftSubtree on empty tree");
- }
- BSTRefBased result = new BSTRefBased();
- result.setRoot(root.left);
- root.left = null;
- return result;
- }
- public AbstractBinaryTree detachRightSubtree()
- throws TreeException
- {
- if (root == null) {
- throw new TreeException("detachLeftSubtree on empty tree");
- }
- BSTRefBased result = new BSTRefBased();
- result.setRoot(root.right);
- root.right = null;
- return result;
- }
- public void insert(String word) {
- root=insertItem(root, word);
- }
- protected TreeNode insertItem(TreeNode r, String word) {
- if(r==null){
- r = new TreeNode(new WordRefs(word));
- r.left = null;
- r.right = null;
- }
- else if(word.compareTo(r.item.getWord()) < 0){
- r.left = insertItem(r.left, word);
- } else if (word.compareTo(r.item.getWord()) > 0){
- r.left = insertItem(r.right, word);
- }
- return r;
- }
- public WordRefs retrieve(String word) {
- TreeNode node = retrieveItem(root, word);
- if (node == null) {
- return null;
- } else {
- return new WordRefs(node.item.getWord());
- }
- }
- protected TreeNode retrieveItem(TreeNode r, String word) {
- if (r == null){
- return null;
- }
- if (word.compareTo(r.item.getWord()) < 0){
- return retrieveItem(r.left, word);
- } else if (word.compareTo(r.item.getWord()) > 0 ){
- return retrieveItem(r.right, word);
- }
- return r;
- }
- public void delete(String word) {
- root = deleteItem(root, word);
- }
- protected TreeNode deleteItem(TreeNode r, String word) {
- if (r == null){
- return r;
- }
- if(word.compareTo(r.item.getWord()) < 0){
- r.left = deleteItem(r.left, word);
- } else if (word.compareTo(r.item.getWord()) > 0){
- r.right = deleteItem(r.right, word);
- } else if(r.left != null && r.right != null)
- {
- root = findLeftMost(r.right);
- r.right = deleteItem(r.right, word).right;
- } else {
- return r;
- }
- return r;
- }
- protected TreeNode deleteNode(TreeNode node) {
- node = null;
- return node;
- }
- protected TreeNode findLeftMost(TreeNode node) {
- if(node == null){
- return null;
- } else {
- return findLeftMost(node.left);
- }
- }
- protected TreeNode deleteLeftMost(TreeNode node) {
- if (node == null){
- return null;
- } else if(node.left == null){
- return findLeftMost(node.left);
- } else {
- return deleteNode(node.left);
- }
- }
- public Iterator<WordRefs> iterator() {
- return new BSTIterator(this);
- }
- public static void main(String args[]) {
- BSTRefBased t;
- AbstractBinaryTree tt;
- int i;
- boolean result;
- String message;
- message = "Test 1: inserting 'humpty' -- ";
- t = new BSTRefBased();
- try {
- t.insert("humpty");
- result = t.getRootItem().getWord().equals("humpty");
- } catch (Exception e) {
- result = false;
- }
- System.out.println(message + (result ? "passed" : "FAILED"));
- message = "Test 2: inserting 'humpty', 'dumpty', 'sat' -- ";
- t = new BSTRefBased();
- try {
- t.insert("humpty");
- t.insert("dumpty");
- t.insert("sat");
- result = t.getRootItem().getWord().equals("humpty");
- tt = t.detachLeftSubtree();
- result &= tt.getRootItem().getWord().equals("dumpty");
- tt = t.detachRightSubtree();
- result &= tt.getRootItem().getWord().equals("sat");
- } catch (Exception e) {
- result = false;
- }
- System.out.println(message + (result ? "passed" : "FAILED"));
- message = "Test 3: deleting 'humpty' -- ";
- t = new BSTRefBased();
- try {
- t.delete("humpty");
- result = t.getRootItem().getWord().equals(null);
- } catch (Exception e) {
- result = false;
- }
- System.out.println(message + (result ? "passed" : "FAILED"));
- message = "Test 4: deleting 'dumpty' 'sat' -- ";
- t = new BSTRefBased();
- try {
- t.delete("dumpty");
- t.delete("sat");
- result = t.getRootItem().getWord().equals(null);
- tt = t.detachLeftSubtree();
- result &= tt.getRootItem().getWord().equals(null);
- } catch (Exception e) {
- result = false;
- }
- System.out.println(message + (result ? "passed" : "FAILED"));
- }
- }
- import java.util.LinkedList;
- public class BSTIterator implements java.util.Iterator<WordRefs> {
- private BSTRefBased t;
- private WordRefs currentItem;
- private LinkedList<WordRefs> list;
- public BSTIterator(BSTRefBased t) {
- this.t = t;
- currentItem = null;
- list = new LinkedList<>();
- setInorder();
- }
- public boolean hasNext() {
- return false;
- }
- public WordRefs next() throws java.util.NoSuchElementException {
- return null;
- }
- public void remove() throws UnsupportedOperationException {
- throw new UnsupportedOperationException();
- }
- public void setPreorder() {
- }
- public void setInorder() {
- }
- public void setPostorder() {
- }
- private void preorder(TreeNode node) {
- if(node == null)
- {
- return;
- }
- preorder(node.left);
- preorder(node);
- preorder(node.right);
- }
- private void inorder(TreeNode node) {
- if(node == null)
- {
- return;
- }
- inorder(node.left);
- inorder(node);
- inorder(node.right);
- }
- private void postorder(TreeNode node) {
- if(node == null)
- {
- return;
- }
- postorder(node.left);
- postorder(node);
- postorder(node.right);
- }
- }
- inorder == left node, the actual node, right node
- preorder == the actual node, left node,right node
- postorder == left node, right node, the actual node
- public void setInorder() {
- list = new LinkedList<>();
- }
- private void inorder(TreeNode node) {
- if(node != null)
- {
- inorder(node.left); //traverse left first
- list.add(node.data); //traverse the actual nodes data
- inorder(node.right); // then traverse right
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement