Binary Search Tree toString

问题:

I am having trouble printing out a binary search tree in the format my professor wants.

His format looks like this:

{(12,10,13),(10,8,11),(8,6,9),(6,4,7),(4,2,5),(2,1,3),(1,*,*),(3,*,*),(5,*,*),(7,*,*),(9,*,*),(11,*,*),(13,*,*)} 

The first number in a subset is the root node, and the left and right nodes are the left and right children. The left child then becomes the root node after a loop iterates. everything works fine until I reach where only one node exists in a subset. It just prints (1, *, *) till the end, and I can not figure out how to do it another way. Is it possible to recursively do this toString method?

My Code:

public String toString()
{
   if (root == null)
       return "{}";
   String str = "{";
   Node tmp = root;
   for (int i = 0; i < size; i++)
   {   
        if (tmp.right != null && tmp.left == null)
            str += "("+tmp.data+", "+tmp.right.data+", *)";
        if (tmp.left != null && tmp.right == null)
            str += "("+tmp.data+", "+tmp.left.data+", *)";
        if (tmp.left == null && tmp.right == null)          
            str += "("+tmp.data+", *, *)";
        else
            str += "("+tmp.data+", "+tmp.left.data+", "+tmp.right.data+")";

        if (tmp.left != null)
            tmp = tmp.left;
   }

   return str += "}";   
}

回答1:

This approach depends how you have your objects setup, but I typically have a Node class that performs the recursive operations. If implemented in this fashion, you should see output like so

{(12,10,13),(10,8,11),(8,*,*),(11,*,*),(13,*,*)}

For this example, we will have a method that returns your (data,left,right) format on the Node class.

public class Node<T>

    protected T data;
    protected Node<T> left;
    protected Node<T> right;

    public String tuple() {
        StringBuilder sb = new StringBuilder("(")
                .append(this.data)
                .append(",");
        sb.append(this.left == null ? "*" : this.left.data)
                .append(",");
        sb.append(this.right == null ? "*" : this.right.data)
                .append(")");
        return sb.toString();
    }

    // other methods
}

Then, the recursive string would be implemented in the toString like so.

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        String divider = ",";

        sb.append(this.tuple()).append(divider);

        if (this.left != null) {
            sb.append(this.left).append(divider); // recurse left
        }

        if (this.right != null) {
            sb.append(this.right).append(divider); // recurse right
        }

        if (sb.length() > divider.length() - 1) {
            sb.setLength(sb.length() - divider.length());
        }

        return sb.toString();
    }
}

Then, in some BinaryTree class, you could have

public class BinaryTree<E extends Comparable<? super E>> {

    protected Node<E> root;

    @Override
    public String toString() {
        return "{"
                + (root == null ? "" : String.valueOf(this.root)) +
                "}";
    }

    // other methods

}

回答2:

For starters, I think you want to have all four clauses in an if-then-else structure. At the moment, the first two cases (one child) will also execute the "else" clause.

The main problem is that you never come back to work with the right sub-tree: the only movement logic goes to the left. Your loop executes once for each element of the tree, but your only traversal is down the left side. You take six steps to get down to node 1, but you never backtrack to any of the right children.

I suspect that you'll want to handle this with a recursive routine, one that call itself for both the left and right branches.

Does that get you going?

回答3:

It sounds like what you want is for toString to (almost) generate the following:

1. A {
2. The triple for the root node
3. A comma and toString for the left node, if it isn't empty
4. A comma and toString for the right node, if it isn't empty
5. A }

The only problem is that the recursive calls should not print the enclosing braces; I'll leave that as an exercise.

回答4:

I finally figured it out, thank you everyone that helped. This is what I wrote in the end to recursively print the binary search tree

   public String toString()
   {   
       if (root == null)
           return "{}";   
       return "{"+toString(root) + "}";

   }
   private String toString(Node parent)
   {
       if (parent.left == null && parent.right == null)
           return "(" + parent.data + ", *, *)";
       else if (parent.left == null && parent.right != null)
           return "(" + parent.data + ", *,"+parent.right.data+" )" + toString(parent.right);
       else if (parent.left !=null && parent.right == null)
           return"(" + parent.data + ", "+parent.left.data+", *)"+ toString(parent.left);
       else
           return "(" + parent.data + ", "+parent.left.data+", "+parent.right.data+")" + toString(parent.left) + toString(parent.right);          

   }