Baum Traversierung Postorder

[bradig]

Hi
ich habe ein kleines problem mit der traversePostOrder()-Methode .
Ich habe das Gefühl,dass etwas in meinem Code fehlt .
Bitte um Hilfe
Herzlich
Bradig

public class TreeNode {

    /**
     * Der Wert dieses Knotens.
     */
    private final int value;

    /**
     * Der linke Nachfolgerknoten dieses Knotens.
     */
    private TreeNode leftChild;

    /**
     * Der rechte Nachfolgerknoten dieses Knotens.
     */
    private TreeNode rightChild;

    /**
     * Erzeugt einen neuen Knoten mit dem gegebenen Wert. Die Nachfolgerknoten bekommen beide
     * den Wert {@code null}.
     *
     * @param theValue der Wert für den neuen Knoten
     */
    public TreeNode(final int theValue) {
        value = theValue;
    }

    public void setLeftChild(final TreeNode node) {
        leftChild = node;
    }

    public void setRightChild(final TreeNode node) {
        rightChild = node;
    }

    public String traversePostOrder() {

        final TreeNode root=new TreeNode(value);
        String a="";
      
        if(leftChild!=null){
           leftChild.traversePostOrder();
         
        }
        if(rightChild!=null){
            rightChild.traversePostOrder();
        }
      
    
        a=traversePostOrder();
            return a;

    }

}

 

[mrBrown]

Problem=Stackoverflow?

Am Ende vom traversePostOrder() rufst du wieder traversePostOrder() auf, und gelangst nie aus der Funktion, irgendwann läuft dadurch der Stack über.


Ich tippe mal drauf, dass du zuerst linkes Kind ausgeben willst, dann rechtes Kind und dann den Knoten selbst?
Wenn a deine Rückgabe sein soll, musst du zuerst das Ergebnis von leftChild.traversePostOrder() dranhängen, dann das gleiche für rechts und dann noch den Wert des aktuellen Knoten selbst.

 

[bradig]

ja .ich möchte das linke Kind,das rechte Kind,und den wert des aktuellen knoten ausgeben in Form eines Strings ausgeben.

 

[mrBrown]

Lösung steht schon in meinem Post, musst du nur noch umsetzten 😉
Oder hast du dabei noch Probleme?

 

[Xyz1]

Bei Postorder links,rechts,wurzel; also dann so:

public void traversePostOrder(TreeNode tn) {
  if (tn == null)
    return;
  traversePostOrder(tn.leftChild);
  traversePostOrder(tn.rightChild);
  sout("" + tn.value);
}

oder:

public void traversePostOrder() {
  if (leftChild != null)
    leftChild.traversePostOrder();
  if (rightChild != null)
    rightChild.traversePostOrder();
  sout("" + value);
}

 

[kneitzel]

Oder man kann das natürlich auch mit Rückgabe machen:

public String traversePostOrder() {
  String result = leftChild != null ? leftChild.traversePostOrder() + " " : "";
  result += rightChild != null ? rightChild.traversePostOrder() + " " : "";
  result += value;
  return result;
}

 

[bradig]

es hat geklappt.
Danke

public class TreeNode {

    /**
     * Der Wert dieses Knotens.
     */
    private final int value;

    /**
     * Der linke Nachfolgerknoten dieses Knotens.
     */
    private TreeNode leftChild;

    /**
     * Der rechte Nachfolgerknoten dieses Knotens.
     */
    private TreeNode rightChild;

    /**
     * Erzeugt einen neuen Knoten mit dem gegebenen Wert. Die Nachfolgerknoten bekommen beide
     * den Wert {@code null}.
     *
     * @param theValue der Wert für den neuen Knoten
     */
    public TreeNode(final int theValue) {
        value = theValue;
    }

    public void setLeftChild(final TreeNode node) {
        leftChild = node;
    }

    public void setRightChild(final TreeNode node) {
        rightChild = node;
    }

    public String traversePostOrder() {

    
        String result="";
    
        if(leftChild!=null){
          result=leftChild.traversePostOrder();
        
        }
        if(rightChild!=null){
           result=result+ rightChild.traversePostOrder();
        }
    
   result=result+Integer.toString(value);
    
            return result;

    }

}