二进制搜索树toString [英] Binary Search Tree 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
}
这篇关于二进制搜索树toString的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!