Go语言视频零基础入门到精通

javalearner

In java, the key points in the recursion are exactly the same as in C or C++. In fact, I created the Java solutions by just copying the C solutions, and then making the syntactic changes. The recursion is the same, however the outer structure is slightly different.
                                                                                    
    In Java, we will have a BinaryTree object that contains a single root pointer. The root pointer points to an internal Node class that behaves just like the node struct in the C/C++ version. The Node class is private -- it is used only for internal storage inside the BinaryTree and is not exposed to clients. With this OOP structure, almost every operation has two methods: a one-line method on the BinaryTree that starts the computation, and a recursive method that works on the Node objects. For the lookup() operation, there is a BinaryTree.lookup() method that the client uses to start a lookup operation. Internal to the BinaryTree class, there is a private recursive lookup(Node) method that implements the recursion down the Node structure.   
  
  
  This second, private recursive method is basically the same as the recursive C/C++ functions above -- it takes a Node argument and uses recursion to iterate over the pointer structure.  Java Binary Tree Structure To get started, here are the basic definitions for the Java BinaryTree class, and the lookup() and insert() methods as examples...  // BinaryTree.java
public class BinaryTree {
   // Root node pointer. Will be null for an empty tree.
   private Node root;
      /*
    --Node--
    The binary tree is built using this nested node class.
    Each node stores one data element, and has left and right
    sub-tree pointer which may be null.
    The node is a "dumb" nested class -- we just use it for
    storage; it does not have any methods.
   */
   private static class Node {
     Node left;
     Node right;
     int data;      Node(int newData) {
       left = null;
       right = null;
       data = newData;
     }
   }    /**
    Creates an empty binary tree -- a null root pointer.
   */
   public void BinaryTree() {
     root = null;
   }
      /**
    Returns true if the given target is in the binary tree.
    Uses a recursive helper.
   */
   public boolean lookup(int data) {
     return(lookup(root, data));
   }
      /**
    Recursive lookup  -- given a node, recur
    down searching for the given data.
   */
   private boolean lookup(Node node, int data) {
     if (node==null) {
       return(false);
     }      if (data==node.data) {
       return(true);
     }
     else if (data<node.data) {
       return(lookup(node.left, data));
     }
     else {
       return(lookup(node.right, data));
     }
   }
      /**
    Inserts the given data into the binary tree.
    Uses a recursive helper.
   */
   public void insert(int data) {
     root = insert(root, data);
   }
      /**
    Recursive insert -- given a node pointer, recur down and
    insert the given data into the tree. Returns the new
    node pointer (the standard way to communicate
    a changed pointer back to the caller).
   */
   private Node insert(Node node, int data) {
     if (node==null) {
       node = new Node(data);
     }
     else {
       if (data <= node.data) {
         node.left = insert(node.left, data);
       }
       else {
         node.right = insert(node.right, data);
       }
     }      return(node); // in any case, return the new pointer to the caller
   }
    OOP Style vs. Recursive Style From the client point of view, the BinaryTree class demonstrates good OOP style -- it encapsulates the binary tree state, and the client sends messages like lookup() and insert() to operate on that state. Internally, the Node class and the recursive methods do not demonstrate OOP style. The recursive methods like insert(Node) and lookup (Node, int) basically look like recursive functions in any language. In particular, they do not operate against a "receiver" in any special way. Instead, the recursive methods operate on the arguments that are passed in which is the classical way to write recursion. My sense is that the OOP style and the recursive style do not be combined nicely for binary trees, so I have left them separate. Merging the two styles would be especially awkward for the "empty" tree (null) case, since you can"t send a message to the null pointer. It"s possible to get around that by having a special object to represent the null tree, but that seems like a distraction to me. I prefer to keep the recursive methods simple, and use different examples to teach OOP.  Java Solutions Here are the Java solutions to the 14 binary tree problems. Most of the solutions use two methods:a one-line OOP method that starts the computation, and a recursive method that does the real operation. Make an attempt to solve each problem before looking at the solution -- it"s the best way to learn.  1. Build123() Solution (Java) /**
  Build 123 using three pointer variables.
*/
public void build123a() {
   root = new Node(2);
   Node lChild = new Node(1);
   Node rChild = new Node(3);   root.left = lChild;
   root.right= rChild;
}  /**
  Build 123 using only one pointer variable.
*/
public void build123b() {
   root = new Node(2);
   root.left = new Node(1);
   root.right = new Node(3);
}
    /**
  Build 123 by calling insert() three times.
  Note that the "2" must be inserted first.
*/
public void build123c() {
   root = null;
   root = insert(root, 2);
   root = insert(root, 1);
   root = insert(root, 3);
}
    2. size() Solution (Java) /**
  Returns the number of nodes in the tree.
  Uses a recursive helper that recurs
  down the tree and counts the nodes.
*/
public int size() {
   return(size(root));
} private int size(Node node) {
   if (node == null) return(0);
   else {
     return(size(node.left) + 1 + size(node.right));
   }
}
    3. maxDepth() Solution (Java) /**
  Returns the max root-to-leaf depth of the tree.
  Uses a recursive helper that recurs down to find
  the max depth.
*/
public int maxDepth() {
   return(maxDepth(root));
} private int maxDepth(Node node) {
   if (node==null) {
     return(0);
   }
   else {
     int lDepth = maxDepth(node.left);
     int rDepth = maxDepth(node.right);      // use the larger + 1
     return(Math.max(lDepth, rDepth) + 1);
   }
}
    4. minValue() Solution (Java) /**
  Returns the min value in a non-empty binary search tree.
  Uses a helper method that iterates to the left to find
  the min value.
*/
public int minValue() {
  return( minValue(root) );
}
    /**
  Finds the min value in a non-empty binary search tree.
*/
private int minValue(Node node) {
   Node current = node;
   while (current.left != null) {
     current = current.left;
   }    return(current.data);
}  5. printTree() Solution (Java) /**
  Prints the node values in the "inorder" order.
  Uses a recursive helper to do the traversal.
*/
public void printTree() {
  printTree(root);
  System.out.println();
} private void printTree(Node node) {
  if (node == null) return;   // left, node itself, right
  printTree(node.left);
  System.out.print(node.data + "  ");
  printTree(node.right);
}
    6. printPostorder() Solution (Java) /**
  Prints the node values in the "postorder" order.
  Uses a recursive helper to do the traversal.
*/
public void printPostorder() {
  printPostorder(root);
  System.out.println();
} public void printPostorder(Node node) {
   if (node == null) return;    // first recur on both subtrees
   printPostorder(node.left);
   printPostorder(node.right);    // then deal with the node
  System.out.print(node.data + "  ");
}
    7. hasPathSum() Solution (Java) /**
  Given a tree and a sum, returns true if there is a path from the root
  down to a leaf, such that adding up all the values along the path
  equals the given sum.  Strategy: subtract the node value from the sum when recurring down,
  and check to see if the sum is 0 when you run out of tree.
*/
public boolean hasPathSum(int sum) {
  return( hasPathSum(root, sum) );
}  boolean hasPathSum(Node node, int sum) {
   // return true if we run out of tree and sum==0
   if (node == null) {
     return(sum == 0);
   }
   else {
   // otherwise check both subtrees
     int subSum = sum - node.data;
     return(hasPathSum(node.left, subSum) || hasPathSum(node.right, subSum));
   }
}
    8. printPaths() Solution (Java) /**
  Given a binary tree, prints out all of its root-to-leaf
  paths, one per line. Uses a recursive helper to do the work.
*/
public void printPaths() {
   int[] path = new int[1000];
   printPaths(root, path, 0);
} /**
  Recursive printPaths helper -- given a node, and an array containing
  the path from the root node up to but not including this node,
  prints out all the root-leaf paths.
*/
private void printPaths(Node node, int[] path, int pathLen) {
   if (node==null) return;    // append this node to the path array
   path[pathLen] = node.data;
   pathLen++;    // it"s a leaf, so print the path that led to here
   if (node.left==null && node.right==null) {
     printArray(path, pathLen);
   }
   else {
   // otherwise try both subtrees
     printPaths(node.left, path, pathLen);
     printPaths(node.right, path, pathLen);
   }
}  /**
  Utility that prints ints from an array on one line.
*/
private void printArray(int[] ints, int len) {
   int i;
   for (i=0; i<len; i++) {
    System.out.print(ints + " ");
   }
   System.out.println();
}
    9. mirror() Solution (Java)
/**
  Changes the tree into its mirror image.   So the tree...
        4
       /  
      2   5
     /  
    1   3   is changed to...
        4
       /  
      5   2
         /  
        3   1   Uses a recursive helper that recurs over the tree,
  swapping the left/right pointers.
*/
public void mirror() {
   mirror(root);
}  private void mirror(Node node) {
   if (node != null) {
     // do the sub-trees
     mirror(node.left);
     mirror(node.right);      // swap the left/right pointers
     Node temp = node.left;
     node.left = node.right;
     node.right = temp;
   }
}
    10. doubleTree() Solution (Java) /**
  Changes the tree by inserting a duplicate node
  on each nodes"s .left.
   
     So the tree...
     2
    /  
   1   3   Is changed to...
        2
       /  
      2   3
     /   /
    1   3
   /
  1   Uses a recursive helper to recur over the tree
  and insert the duplicates.
*/
public void doubleTree() {
  doubleTree(root);
}  private void doubleTree(Node node) {
   Node oldLeft;    if (node == null) return;    // do the subtrees
   doubleTree(node.left);
   doubleTree(node.right);    // duplicate this node to its left
   oldLeft = node.left;
   node.left = new Node(node.data);
   node.left.left = oldLeft;
}
    11. sameTree() Solution (Java) /*
  Compares the receiver to another tree to
  see if they are structurally identical.
*/
public boolean sameTree(BinaryTree other) {
  return( sameTree(root, other.root) );
} /**
  Recursive helper -- recurs down two trees in parallel,
  checking to see if they are identical.
*/
boolean sameTree(Node a, Node b) {
   // 1. both empty -> true
   if (a==null && b==null) return(true);    // 2. both non-empty -> compare them
   else if (a!=null && b!=null) {
     return(
       a.data == b.data &&
       sameTree(a.left, b.left) &&
       sameTree(a.right, b.right)
     );
   }
   // 3. one empty, one not -> false
   else return(false);
}
    12. countTrees() Solution (Java) /**
  For the key values 1...numKeys, how many structurally unique
  binary search trees are possible that store those keys?  Strategy: consider that each value could be the root.
  Recursively find the size of the left and right subtrees.
*/
public static int countTrees(int numKeys) {
   if (numKeys <=1) {
     return(1);
   }
   else {
     // there will be one value at the root, with whatever remains
     // on the left and right each forming their own subtrees.
     // Iterate through all the values that could be the root...
     int sum = 0;
     int left, right, root;      for (root=1; root<=numKeys; root++) {
       left = countTrees(root-1);
       right = countTrees(numKeys - root);        // number of possible trees with this root == left*right
       sum += left*right;
     }      return(sum);
   }
}
    13. isBST1() Solution (Java) /**
  Tests if a tree meets the conditions to be a
  binary search tree (BST).
*/
public boolean isBST() {
   return(isBST(root));
} /**
  Recursive helper -- checks if a tree is a BST
  using minValue() and maxValue() (not efficient).
*/
private boolean isBST(Node node) {
   if (node==null) return(true);    // do the subtrees contain values that do not
   // agree with the node?
   if (node.left!=null && maxValue(node.left) > node.data) return(false);
   if (node.right!=null && minValue(node.right) <= node.data) return(false);    // check that the subtrees themselves are ok
   return( isBST(node.left) && isBST(node.right) );
} 14. isBST2() Solution (Java) /**
  Tests if a tree meets the conditions to be a
  binary search tree (BST). Uses the efficient
  recursive helper.
*/
public boolean isBST2() {
  return( isBST2(root, Integer.MIN_VALUE, Integer.MAX_VALUE) );
} /**
   Efficient BST helper -- Given a node, and min and max values,
   recurs down the tree to verify that it is a BST, and that all
   its nodes are within the min..max range. Works in O(n) time --
   visits each node only once.
*/
private boolean isBST2(Node node, int min, int max) {
   if (node==null) {
     return(true);
   }
   else {
    // left should be in range  min...node.data
     boolean leftOk = isBST2(node.left, min, node.data);      // if the left is not ok, bail out
     if (!leftOk) return(false);      // right should be in range node.data+1..max
     boolean rightOk = isBST2(node.right, node.data+1, max);      return(rightOk);
   }
}

   
     
     
      
      

        
      

        
      
     
   

  


源码下载：http://file.javaxxz.com/2014/11/9/000432375.zip