二叉搜索树 toString

Question

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

他的格式是这样的：

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

子集中第一个数为根节点，左右节点为左右children。左边的child经过一个循环迭代后成为根节点。一切正常，直到我到达一个子集中只有一个节点的地方。它只是打印 (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

首先，我认为您希望将所有四个子句都放在 if-then-else 结构中。目前，前两种情况（一种child）也会执行"else"子句。

主要问题是你永远不会回到右边工作sub-tree：唯一的运动逻辑是向左。您的循环对树的每个元素执行一次，但您唯一的遍历是在左侧。你走了六个步骤才能到达节点 1，但你永远不会回溯到任何正确的 children.

我怀疑您希望使用递归例程来处理此问题，即为左右分支调用自身的例程。

这让你继续吗？

Answer 2

听起来您想要的是 toString 以（几乎）生成以下内容：

一个{
根节点的三元组
左节点的逗号和 toString，如果它不为空
一个逗号和 toString 代表右边的节点，如果它不为空的话
一个}

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

Answer 3

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

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

对于这个例子，我们将有一个方法将returns你的(data,left,right)格式放在Nodeclass上。

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 中实现，就像这样。

    @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 class 中，您可以

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

}

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

   }

二叉搜索树 toString

Binary Search Tree toString

java

recursion

binary-search-tree