Programming Resources
For Fun and Learning
Charles Cusack
Computer Science
Hope College
main

Python
C++

JAVA


PHP
SQL
Alice

TruthTableQuiz


Description

Run it

BinaryTree.java
Connectives.java
FontFixer.java
Proposition.java
TreeNode.java
TruthTable.java
TruthTableQuiz.java

BinaryTree.java

//----------------------------------------------------------------------
public class BinaryTree {
public static void main(String argv[]) {
}
//----------------------------------------------------------------------
public static final int LOGIC_PROP=30;
public static final int SET=31;
//----------------------------------------------------------------------
private TreeNode root;

public BinaryTree()                   { root=null; }
public BinaryTree(TreeNode Root)         { root=Root; }
public BinaryTree(TreeNode Root,TreeNode Left, TreeNode Right) {
         root=Root; 
         root.setLeft(Left); 
         root.setRight(Right); }
public BinaryTree(TreeNode Root,BinaryTree Left, BinaryTree Right) {
         root=Root; 
         root.setLeft(Left.getRoot()); 
         root.setRight(Right.getRoot()); }
public BinaryTree(char Key)           { root=new TreeNode(Key);  }
public BinaryTree(char Key,int Index) { root=new TreeNode(Key,Index); }
public BinaryTree(String S,int type) {
       if(type==LOGIC_PROP)
         setProposition(S);
       else
         root=null;
       }
//----------------------------------------------------------------------
public TreeNode getRoot()       { return root; }
public void setRoot(TreeNode R) { root=R; }
public void setRoot(char info)         { root=new TreeNode(info); }
//----------------------------------------------------------------------
public String InOrder() {
  return InOrder(false);
  }
public String InOrder(boolean addParens) {
  return InOrder(root,addParens);
  }
public String InOrder(TreeNode r) {
    return InOrder(r,false);
    }
public String InOrder(TreeNode r,boolean addParens) {
    StringBuffer T=new StringBuffer();
    InOrder(r,T,addParens);
    return new String(T);
    }
private void InOrder(TreeNode r, StringBuffer S,boolean AddParens) {
  if(r!=null) {
    if(AddParens==true && !r.isLeaf()) S.append('(');
    InOrder(r.getLeft(),S,AddParens);
    S.append(r.getKey());
    InOrder(r.getRight(),S,AddParens);
    if(AddParens==true && !r.isLeaf()) S.append(')');
    }
  }
//----------------------------------------------------------------------
public boolean spliceOut(TreeNode thenode) {
  if(thenode==null)                                       return true;
  if(thenode.getLeft()!=null && thenode.getRight()!=null) return false;

  TreeNode child;

  if(thenode.getLeft()!=null)       { child=thenode.getLeft(); }
  else if(thenode.getRight()!=null) { child=thenode.getRight(); }
  else                              { child=null; }
  TreeNode P=thenode.getParent();
  if(P==null)                   { root=child; child.setParent(null); }
  else if(thenode==P.getLeft()) { P.setLeft(child); }
  else                          { P.setRight(child); }
  return true;
}
//----------------------------------------------------------------------
/**
 * Splice the first node into the tree as the parent of
 * the second node, making it the left child, and setting
 * the right child to null.
 *
 * @param currentNode the node in the tree.
 * @parem newNode the node add.
 *
 */
public void spliceInLeft(TreeNode currentNode, TreeNode newNode) {
  if(currentNode==root) { root=newNode; }
  else {
     TreeNode P=currentNode.getParent();
     if(currentNode==P.getLeft()) { P.setLeft(newNode); }
     else                         { P.setRight(newNode); }
  }
  newNode.setLeft(currentNode); 
}

/**
 * Splice the first node into the tree as the parent of
 * the second node, making it the right child, and setting
 * the left child to null.
 *
 * @param currentNode the node in the tree.
 * @parem newNode the node add.
 *
 */
public void spliceInRight(TreeNode currentNode, TreeNode newNode) {
  if(currentNode==root) { root=newNode; }
  else {
     TreeNode P=currentNode.getParent();
     if(currentNode==P.getLeft()) { P.setLeft(newNode); }
     else                         { P.setRight(newNode); }
  }
  newNode.setRight(currentNode); 
}

//----------------------------------------------------------------------
/**
 * Replace the subtree rooted at R with the subtree rooted at N
 *
 * @param R the original subtree
 * @parem N the new subtree
 *
 */
public void replaceSubtree(TreeNode R, TreeNode N) {
  if(R==root) { root=N; }
  else {
     TreeNode P=R.getParent();
     if(R==P.getLeft()) { P.setLeft(N); }
     else               { P.setRight(N); }
  }
}

//----------------------------------------------------------------------
public void leftRotate(TreeNode x) {
   TreeNode y=x.getRight();
   x.setRight(y.getLeft());
   TreeNode px=x.getParent();
   if(px==null)             { root=y; y.setParent(null); }
   else if(x==px.getLeft()) { px.setLeft(y); }
   else                     { px.setRight(y); }
   y.setLeft(x);
}
//----------------------------------------------------------------------
public void rightRotate(TreeNode x) {
   TreeNode y=x.getLeft();
   x.setLeft(y.getRight());
   TreeNode px=x.getParent();
   if(px==null)             { root=y; y.setParent(null); }
   else if(x==px.getLeft()) { px.setLeft(y); }
   else                     { px.setRight(y); }
   y.setRight(x);
}
//----------------------------------------------------------------------
// This assumes the index variables are used in an in-order fashion.
public BinaryTree substringTree(int firstindex,int lastindex) {
  TreeNode p=root;
  while(p!=null && !p.isLeaf() &&
        (p.getIndex()<firstindex || p.getIndex()>=lastindex) ) {
       if(p.getIndex()<firstindex) {
         p=p.getRight();
       }
       else if(p.getIndex()>=lastindex) {
         p=p.getLeft();
       }
  }
  return new BinaryTree(p);
}
//----------------------------------------------------------------------
/**
  * Construct the binary tree corresponding to the boolean proposition
  * in string S.
  * @return true if it succeeds, and false if it does not
  * (for instance, if the string is not a logical proposition.)
  * Given a string, construct a Proposition from S and return the root of the
  * constructed Proposition.
  */
public boolean setProposition(String S) {
  if(S.length()==0) {
    root=null;
    return false;
    }
  root=new TreeNode(' ',-1);
  TreeNode C=root;
  for(int i=0;i<S.length();i++) {
     if(C==null) {
        root=null;
        return false;
     }
     char current=S.charAt(i);
     if(current=='(') {
        C.blankLeft();
        C=C.getLeft();
        }
     else if(Connectives.isConnective(current)) {
        if(Connectives.isNEGATION(current) && C!=root) {
                             // Wrong node inserted, remove it.
           C=C.getParent();
           C.removeLeft();
           }
        if(C==null) {
           root=null;
           return false;
           }
        C.setData(Connectives.toUnicode(current),i);
        C.blankRight();
        C=C.getRight();
        }
     else if(Character.isLetter(current)) {
        C.setData(current,i);
        C=C.getParent();
        }
     else if(current==')') {
        if(C!=null)
          C=C.getParent();
        }
     else {   // Something is wrong--return false and make tree empty.
        root=null;
        return false;
        }
     }
  if(Connectives.toUnicode(S).equals(InOrder(true))) {
      return true;
      }
  else { 
     root=null;
     return false;
     }
  }
//----------------------------------------------------------------------
}