Binary Search Tree zu String

-1

Ich muss eine Methode erstellen, die eine BST in eine Zeichenfolge konvertiert, jedes Kind mit einem Einzug Zeichen vorangestellt.Binary Search Tree zu String

Beispiel:

BinaryTreeSet set=new BinaryTreeSet(); 
set.add(6); 
set.add(4); 
set.add(3); 
set.add(5); 
set.add(9); 
set.add(10); 
set.add(8); 
set.add(0); 
System.out.println(set.treeString());

sollte produzieren

=> 6 
    => 4 
    => 3 
     => 0 
    => 5 
    => 9 
    => 8 
    => 10

ich für ein paar Stunden jetzt versucht, aber ich mache keine Fortschritte.

Das Beste, was ich war

=> 6 
=> 0 
=> 3 
=> 5 
=> 4 
=> 8 
=> 10 
=> 9

mit folgendem Code bekommen konnte:

public String treeString() { 

    StringBuilder builder = new StringBuilder("=> " + root); 
    builder.append(System.getProperty("line.separator")); 

    nodeString(root, builder); 

    return builder.toString(); 

    } 

    private void nodeString(BinaryTreeNode node, StringBuilder builder) { 
     if (node == null) { 
      return; 
     } 
     if (node.left != null) { 
      nodeString(node.left, builder); 
      builder.append("=> " + node.left); 
      builder.append(System.getProperty("line.separator")); 
     } 
     if (node.right != null) { 
      nodeString(node.right, builder); 
      builder.append("=> " + node.right); 
      builder.append(System.getProperty("line.separator")); 
     } 
    }

Irgendwie kann ich nicht herausfinden, wie die Bestellung richtig machen ... Auch habe ich keine Ahnung über wie man den Einzug richtig macht.

Danke!

Quelle

2017-03-22 schoeni

Ihr Beispiel (wenn die Werte addiert) nicht die gewünschte Ausgabe entsprechen, wenn Sie BST verwenden. 'set.add (6); Satz.add (4); set.add (3); 'sollte 6 als Wurzel erzeugen, 4 als linkes Blatt und 3 als rechtes Blatt ... – KarelG

Dann haben wir eine andere Definition von BST gelernt! Unseres ist, dass das linke Kind kleiner sein muss als sein Elternteil, das Recht muss größer sein. Danke trotzdem, ich habe es funktioniert! – schoeni

@shoeni Nun ... du hast Recht. Ich habe einen anderen Baum im Kopf. mit 'set.add (6); Satz.add (4); set.add (3); 'in einer BST sollte in der Tat eine 6 eine Wurzel, 4 als links und 3 als links von 4 liefern. Meine schlechte. – KarelG

Versuchen Sie, die builder.append Linien vor die rekursive nodeString Anrufe platzieren. Wenn Sie wie in Ihrer Beispielausgabe zusätzlich einen Einzug benötigen, müssen Sie auch die Anruftiefe in Ihren rekursiven Aufrufen verfolgen.

Quelle

2017-03-22 12:54:14

danke, löste das Bestellproblem perfekt. Ich werde meinen fertigen Code veröffentlichen, sobald ich den Einzug fertig habe! – schoeni

Dies funktioniert das Problem für die Definition von BST lösen wir gelernt:

private void nodeString(BinaryTreeNode node, StringBuilder builder, int count) { 
     if (node == null) { 
      return; 
     } 
     // Left 
     if (node.left != null) { 
      for (int i = 0; i < count; i++) { // Adding indent 
       builder.append(" "); 
      } 
      builder.append("=> " + node.left); 
      builder.append(System.getProperty("line.separator")); 
      nodeString(node.left, builder, ++count); 
      --count; 
     } 
     // Right 
     if (node.right != null) { 
      for (int i = 0; i < count; i++) { // Adding indent 
       builder.append(" "); 
      } 
      builder.append("=> " + node.right); 
      builder.append(System.getProperty("line.separator")); 
      nodeString(node.right, builder, ++count); 
      --count; 
     } 
    }

Quelle

2017-03-22 13:50:09 schoeni

Binary Search Tree zu String

Antwort

Verwandte Themen