二进制搜索树toString

我无法以我教授想要的格式打印出二叉搜索树。

他的格式如下：

{(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方法？

我的代码：

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

Answer 1

这种方法取决于您如何设置对象，但我通常有一个Node类来执行递归操作。 如果以这种方式实现，您应该看到这样的输出

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

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

 public class Node protected T data; protected Node left; protected Node 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实现，就像这样。

  @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类中，你可以拥有

 public class BinaryTree> { protected Node root; @Override public String toString() { return "{" + (root == null ? "" : String.valueOf(this.root)) + "}"; } // other methods } 

Answer 2

首先，我想你想在if-then-else结构中使用所有四个子句。 目前，前两个案例（一个孩子）也将执行“else”子句。

主要问题是你永远不会回来使用正确的子树：唯一的移动逻辑向左移动。 您的循环对树的每个元素执行一次，但您的唯一遍历是在左侧。 您需要六个步骤才能进入节点1，但您永远不会回溯到任何合适的孩子。

我怀疑你会想要用一个递归例程处理这个问题，这个例程自称为左右分支。

这会让你前进吗？

Answer 3

这听起来像你想要的toString （几乎）生成以下内容：

1. 一个{
2. 根节点的三元组
3. 左侧节点的逗号和toString ，如果它不为空
4. 右侧节点的逗号和toString ，如果它不为空
5. A }

唯一的问题是递归调用不应该打印封闭的大括号; 我会把它留作练习。

Answer 4

我终于明白了，谢谢大家的帮助。 这是我最后写的递归打印二叉搜索树

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