二進制搜索樹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,*,*)} 

中的一個子集的第一個數字是根節點，和左，右節點是左，右的孩子。在循環迭代之後，左側子節點成爲根節點。一切正常，直到我到達一個子集中只存在一個節點的地方。它只是打印（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

我終於想通了，謝謝大家的幫助。這是我最後遞歸地打印二叉搜索樹

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

    } 

Answer 2

對於初學者來說，我想你想擁有所有四個子句在IF-THEN-ELSE結構。目前，前兩種情況（一個孩子）也將執行「其他」條款。

主要問題是，你永遠不會回到正確的子樹上工作：唯一的移動邏輯走向左側。你的循環爲樹的每個元素執行一次，但你唯一的遍歷是在左邊。你需要花六個步驟才能到達節點1，但是你永遠不會回到任何合適的孩子身上。

我懷疑你會想要用遞歸例程處理這個問題，一個爲左右分支調用自身的例程。

這會讓你走嗎？

Answer 3

這聽起來像你想要的是toString到（幾乎）生成如下：

1. 一個{
2. 三重根節點
3. 一個逗號和toString左節點，如果它不爲空
4. 逗號和toString爲正確的節點，如果它不是空的
5. A }

唯一的問題是遞歸調用應該是而不是打印括號;我將把它作爲一個練習。

Answer 4

這種方法取決於你如何設置對象，但我通常有一個執行遞歸操作的類Node。如果以這種方式實現的，你應該會看到像這樣

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

輸出在這個例子中，我們將有一個返回的Node類的(data,left,right)格式的方法。

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類，你可以有

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 

}