Method to Display a Splay Tree

问题:

I have built a splay tree and I am trying to print it out reverse in order so that when you turn your head to the left you can see the tree in a normal manner. I have written the following code and it outputs the tree somewhat correctly but it adds extra spaces in on the rightmost node and it doesn't add spaces for all of the child nodes that should be placed below the root node:

   public void printReverseInOrder() {
       if (root != null) {
           reverseInOrder(root, 0);
       }
       else {
           System.out.println();
       }
   }

public void reverseInOrder(BSTnode h, int indent) { 
    if (h != null) {
        for (int i = 0; i < indent; i++) {
            System.out.print("  ");
        }

        indent++;
        reverseInOrder(h.right, indent);


        reverseInOrder(h.left, indent);

        System.out.println(h.data);
        indent--;
    }

}

I feel like it may be an error with either my recursion or the placement of my indent additions and subtractions.

回答1:

This works pretty well, reordered a few things...

public class test {

   public static void main(String[] args){
      node rootNode = new node(5);
      rootNode.r = new node(4);
      rootNode.l = new node(3);
      rootNode.r.r = new node(2);
      rootNode.r.l = new node(1);
      rootNode.l.r = new node(6);
      rootNode.l.l = new node(7);

      reverseInOrder(rootNode, 0);
   }

   public static void reverseInOrder(node h, int indent) { 
      if (h != null) {
         indent++;
         reverseInOrder(h.r, indent);

         for (int i = 0; i < indent; i++) {
            System.out.print("  ");
         }
         System.out.println(h.value);

         reverseInOrder(h.l, indent);
      }
   }
}

your indent-- at the end of your call isn't really doing anything since the function ends and it jumps back up. Also as indent increases the spacing is actually going up exponentially in your example code (because it prints spaces on entering each time so 1space + 2 space + 3 space), I just changed it to add the spaces only right before it prints the value itself (so it is always equal to indent itself instead of indent factorial).

output looks like this:

      2
    4
      1
  5
      6
    3
      7