二进制搜索树toString

本文介绍了二进制搜索树toString的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我无法以教授想要的格式打印二进制搜索树.

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

他的格式如下:

{(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,*,*)}

子集中的第一个数字是根节点，左边和右边的节点是左边和右边的子节点.然后，循环迭代后，左子节点将成为根节点.一切正常，直到我到达子集中只有一个节点的位置.它只会打印(1，*，*)到最后，而我不知道该怎么做.是否可以递归地执行此toString方法?

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?

我的代码:

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 += "}"; }

推荐答案

此方法取决于您如何设置对象，但是我通常有一个执行递归操作的Node类.如果以这种方式实施，您应该会看到类似

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,*,*)}

在此示例中，我们将有一个方法返回Node类上的(data,left,right)格式.

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 }

然后，递归字符串将像这样在toString中实现.

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(); } }

然后，在某些BinaryTree类中，您可以拥有

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 }