package com.cici.深圳同城快跑;import java.util.Stack;class Node{public char cData;              // data item (key)public Node leftChild;         // this node's left childpublic Node rightChild;        // this node's right childpublic void displayNode()      // display ourself   {   System.out.print('{');   System.out.print(cData);   System.out.print("} ");   }}  // end class Nodeclass Tree{public Node root;             // first node of treepublic int size;//-------------------------------------------------------------public Tree()                  // constructor   { root = null; }            // no nodes in tree yet//-------------------------------------------------------------public Node find(char key)      // find node with given key   {                           // (assumes non-empty tree)   Node current = root;               // start at root   while(current.cData != key)        // while no match,      {      if(key < current.cData)         // go left?         current = current.leftChild;      else                            // or go right?         current = current.rightChild;      if(current == null)             // if no child,         return null;                 // didn't find it      }   return current;                    // found it   }  // end find()//-------------------------------------------------------------public void insert(char c){Node newNode = new Node();    // make new nodenewNode.cData = c;           // insert dataif(root==null)                // no node in root   root = newNode;else                          // root occupied   {    //make a new node which is stands for the new node   Node current = root;       // start at root   Node parent;   while(true)                // (exits internally)      {       //parent node is the root node      parent = current;      //go left ?        if(check(c)){          current = current.leftChild;          if(current == null)  // if end of the line,             {                 // insert on left             parent.leftChild = newNode;             return;             }      } // end if go left      else                    // or go right?         {         current = current.leftChild;         if(current == null)  // if end of the line            {                 // insert on right            parent.rightChild = newNode;            return;            }         }  // end else go right      }  // end while   }  // end else not root}  // end insert()//-------------------------------------------------------------public boolean delete(char key) // delete node with given key   {                           // (assumes non-empty list)   Node current = root;   Node parent = root;   boolean isLeftChild = true;   while(current.cData != key)        // search for node      {      parent = current;      if(key < current.cData)         // go left?         {         isLeftChild = true;         current = current.leftChild;         }      else                            // or go right?         {         isLeftChild = false;         current = current.rightChild;         }      if(current == null)             // end of the line,         return false;                // didn't find it      }  // end while   // found node to delete   // if no children, simply delete it   if(current.leftChild==null &&                                current.rightChild==null)      {      if(current == root)             // if root,         root = null;                 // tree is empty      else if(isLeftChild)         parent.leftChild = null;     // disconnect      else                            // from parent         parent.rightChild = null;      }   // if no right child, replace with left subtree   else if(current.rightChild==null)      if(current == root)         root = current.leftChild;      else if(isLeftChild)         parent.leftChild = current.leftChild;      else         parent.rightChild = current.leftChild;   // if no left child, replace with right subtree   else if(current.leftChild==null)      if(current == root)         root = current.rightChild;      else if(isLeftChild)         parent.leftChild = current.rightChild;      else         parent.rightChild = current.rightChild;   else  // two children, so replace with inorder successor      {      // get successor of node to delete (current)      Node successor = getSuccessor(current);      // connect parent of current to successor instead      if(current == root)         root = successor;      else if(isLeftChild)         parent.leftChild = successor;      else         parent.rightChild = successor;      // connect successor to current's left child      successor.leftChild = current.leftChild;      }  // end else two children   // (successor cannot have a left child)   return true;                                // success   }  // end delete()//-------------------------------------------------------------// returns node with next-highest value after delNode// goes to right child, then right child's left descendentsprivate Node getSuccessor(Node delNode)   {   Node successorParent = delNode;   Node successor = delNode;   Node current = delNode.rightChild;   // go to right child   while(current != null)               // until no more      {                                 // left children,      successorParent = successor;      successor = current;      current = current.leftChild;      // go to left child      }                                        // if successor not   if(successor != delNode.rightChild)  // right child,      {                                 // make connections      successorParent.leftChild = successor.rightChild;      successor.rightChild = delNode.rightChild;      }   return successor;   }//-------------------------------------------------------------public void traverse(int traverseType)   {   switch(traverseType)      {      case 1: System.out.print("\nPreorder traversal: ");              preOrder(root);              break;      case 2: System.out.print("\nInorder traversal:  ");              inOrder(root);              break;      case 3: System.out.print("\nPostorder traversal: ");              postOrder(root);              break;      }   System.out.println();   }//-------------------------------------------------------------public void preOrder(Node localRoot)   {   if(localRoot != null)      {      preOrder(localRoot.leftChild);      System.out.print(localRoot.cData + " ");      preOrder(localRoot.rightChild);      }   }//-------------------------------------------------------------public Node inOrder(Node localRoot)   {   if(localRoot != null)      {      inOrder(localRoot.leftChild);      System.out.print(localRoot.cData + " ");      inOrder(localRoot.rightChild);      }   return localRoot;   }//-------------------------------------------------------------public void postOrder(Node localRoot)   {   if(localRoot != null)      {      postOrder(localRoot.leftChild);      postOrder(localRoot.rightChild);      System.out.print(localRoot.cData + " ");      }   }//check the whether a node is a signalpublic static boolean check(Character ch){    if(ch.equals(new Character('+')) || ch.equals(new Character('-'))            || ch.equals(new Character('*'))            || ch.equals(new Character('\\') )                    || ch.equals(new Character('^'))        )                      {                return true;    }    return false;}public long calculate( ){    long result = 0;    result+=this.root.cData-48;    Node localRoot= root.leftChild;    while(localRoot!=null){            if(localRoot.cData=='+'){                if(localRoot.rightChild!=null){                    result+=localRoot.rightChild.cData-48;                }            }            if(localRoot.cData=='-'){                if(localRoot.rightChild!=null){                    result-=localRoot.rightChild.cData-48;                }            }            if(localRoot.cData=='/'){                if(localRoot.rightChild!=null){                    result/=localRoot.rightChild.cData-48;                }            }            if(localRoot.cData=='*'){                if(localRoot.rightChild!=null){                    result*=localRoot.rightChild.cData-48;                }            }                         /*int m = 4;             int n = 2;             int result = 1;             for(int i=0;i

 以上代码没有考虑优先级别顺序 以下代码考虑四则运算符号有限级别 先* / ^ 再 + -

但是没有输出正确答案.因为calculate()方法还是有误.以此本人得到的结论利用节点树形结构太复杂了.尽量避免.本人有空闲时间会参考jdk的tree.

不过依然太难了.调试很多次都没有输出正确结果.今天打算放弃了.有会修改程序的高手希望您看到了改一下.我实在不想改了.

 

package com.cici.深圳同城快跑;import java.util.Stack;class Node{public char cData;              // data item (key)public Node leftChild;         // this node's left childpublic Node rightChild;        // this node's right childpublic  Node(char cData){    this.cData = cData;}public void displayNode()      // display ourself   {   System.out.print('{');   System.out.print(cData);   System.out.print("} ");   }}  // end class Nodeclass Tree{public Node root;             // first node of treepublic int size;//-------------------------------------------------------------public Tree()                  // constructor   { root = null; }            // no nodes in tree yet//-------------------------------------------------------------public Node find(char key)      // find node with given key   {                           // (assumes non-empty tree)   Node current = root;               // start at root   while(current.cData != key)        // while no match,      {      if(key < current.cData)         // go left?         current = current.leftChild;      else                            // or go right?         current = current.rightChild;      if(current == null)             // if no child,         return null;                 // didn't find it      }   return current;                    // found it   }  // end find()//-------------------------------------------------------------public void insert(char c){    Node newNode = new Node(c);    // make new nodeif(root==null&&!check(c)){    root = new Node(' ');    root.rightChild=newNode;    size++;    return;}                // no node in root    else if(root!=null&!check(root.cData)){        Node temp = root.rightChild;        root=new Node(c);        root.rightChild=temp;    size++;    return;}else                          // root occupied   {    //make a new node which is stands for the new node   Node current = root;       // start at root   Node parent;   while(true)                // (exits internally)      {       //parent node is the root node      parent = current;      //go left ?        if(check(c)){          current = current.leftChild;          if(current.cData == ' ')  // if end of the line,             {                 // insert on left              newNode=new Node(c);              newNode.rightChild=current.rightChild;              parent.leftChild = newNode;             size++;             return;             }          else continue;       } // end if go left      else                    // or go right?          {         current = current.leftChild;         if(current == null)  // if end of the line            {                 // insert on right            newNode = new Node(' ');    // make new node               newNode.rightChild=new Node(c);                         parent.leftChild = newNode;            size++;            return;            }        }  // end else go right      }  // end while  }  // end else not root}  // end insert()//-------------------------------------------------------------public boolean delete(char key) // delete node with given key   {                           // (assumes non-empty list)   Node current = root;   Node parent = root;   boolean isLeftChild = true;   while(current.cData != key)        // search for node      {      parent = current;      if(key < current.cData)         // go left?         {         isLeftChild = true;         current = current.leftChild;         }      else                            // or go right?         {         isLeftChild = false;         current = current.rightChild;         }      if(current == null)             // end of the line,         return false;                // didn't find it      }  // end while   // found node to delete   // if no children, simply delete it   if(current.leftChild==null &&                                current.rightChild==null)      {      if(current == root)             // if root,         root = null;                 // tree is empty      else if(isLeftChild)         parent.leftChild = null;     // disconnect      else                            // from parent         parent.rightChild = null;      }   // if no right child, replace with left subtree   else if(current.rightChild==null)      if(current == root)         root = current.leftChild;      else if(isLeftChild)         parent.leftChild = current.leftChild;      else         parent.rightChild = current.leftChild;   // if no left child, replace with right subtree   else if(current.leftChild==null)      if(current == root)         root = current.rightChild;      else if(isLeftChild)         parent.leftChild = current.rightChild;      else         parent.rightChild = current.rightChild;   else  // two children, so replace with inorder successor      {      // get successor of node to delete (current)      Node successor = getSuccessor(current);      // connect parent of current to successor instead      if(current == root)         root = successor;      else if(isLeftChild)         parent.leftChild = successor;      else         parent.rightChild = successor;      // connect successor to current's left child      successor.leftChild = current.leftChild;      }  // end else two children   // (successor cannot have a left child)   return true;                                // success   }  // end delete()//-------------------------------------------------------------// returns node with next-highest value after delNode// goes to right child, then right child's left descendentsprivate Node getSuccessor(Node delNode)   {   Node successorParent = delNode;   Node successor = delNode;   Node current = delNode.rightChild;   // go to right child   while(current != null)               // until no more      {                                 // left children,      successorParent = successor;      successor = current;      current = current.leftChild;      // go to left child      }                                        // if successor not   if(successor != delNode.rightChild)  // right child,      {                                 // make connections      successorParent.leftChild = successor.rightChild;      successor.rightChild = delNode.rightChild;      }   return successor;   }//-------------------------------------------------------------public void traverse(int traverseType)   {   switch(traverseType)      {      case 1: System.out.print("\nPreorder traversal: ");              preOrder(root);              break;      case 2: System.out.print("\nInorder traversal:  ");              inOrder(root);              break;      case 3: System.out.print("\nPostorder traversal: ");              postOrder(root);              break;      }   System.out.println();   }//-------------------------------------------------------------public void preOrder(Node localRoot)   {   if(localRoot != null)      {      preOrder(localRoot.leftChild);      System.out.print(localRoot.cData + " ");      preOrder(localRoot.rightChild);      }   }//-------------------------------------------------------------public Node inOrder(Node localRoot)   {   if(localRoot != null)      {      inOrder(localRoot.leftChild);      System.out.print(localRoot.cData + " ");      inOrder(localRoot.rightChild);      }   return localRoot;   }//-------------------------------------------------------------public void postOrder(Node localRoot)   {   if(localRoot != null)      {      postOrder(localRoot.leftChild);      postOrder(localRoot.rightChild);      System.out.print(localRoot.cData + " ");      }   }//check the whether a node is a signalpublic static boolean check(Character ch){    if(ch.equals(new Character('+')) || ch.equals(new Character('-'))            || ch.equals(new Character('*'))            || ch.equals(new Character('/') )                    || ch.equals(new Character('^'))        )                      {                return true;    }    return false;}public long calculate(){    Node current = this.root;    Node parent  = this.root;    long result = 0;    //handle * / ^    while(current.cData!=' '){        int item1 = current.rightChild.cData-48;        int item2 = current.leftChild.rightChild.cData-48;        long temp = 1;        if(current!=null && current.cData=='*'){            result =item1*item2;            Node next = current.leftChild;            next.rightChild=new Node(((char) (result+48)));        //    parent.cData=next.cData;            parent.leftChild = next;            current = next;             continue;        }if(current!=null && current.cData=='/'){            result =item1/item2;            Node next = current.leftChild;            next.rightChild=new Node(((char) (result+48)));        //    parent.cData=next.cData;            parent.leftChild = next;            current = next;             continue;        }if(current!=null && current.cData=='^'){            for(int i=0;i