Baum Knoten zählen

[Lazyyy]

Hallo Zusammen,
Beschäftige mich derzeit mit Graphen spezieller mit Bäumen:
Problem ist Folgendes: gegeben ist ein Baum bzw ein Wurzelknoten und ich soll nun alle vorhandenen Knoten finden bzw zählen in meiner countNodes Methode:

Mein Gedanke ich packe jeden Knoten auf den Stack und zähle dabei einfach mit.
Der Stack ist mir allerings auch noch neu und bin mir nicht sicher ob ich das so richtig handhabe.. Vorallem das ich beim Stack so einen Integerwert benötige.

package de.ur.iw.adp.tree;

import java.util.Stack;

public class TreeNode {
    private final int content;
    private TreeNode left;
    private TreeNode right;

    public TreeNode(int content) {
        this.content = content;
    }

    public int content() {
        return content;
    }

    public TreeNode left() {
        return left;
    }

    public void setLeft(TreeNode node) {
        left = node;
    }

    public TreeNode right() {
        return right;
    }

    public void setRight(TreeNode node) {
        right = node;
    }

    public static int countNodes(TreeNode root) {
       int counter = 1;
       if(root == null){
           return 0;
       }
       Stack<Integer> stapel = new Stack<>();
       
       if(root != null){
           stapel.push(root.content());
       }
       while(stapel.empty() == false){
           TreeNode Node = new TreeNode(stapel.pop());      
           if(Node.right()!= null){
               stapel.push(Node.right().content());
               counter++;
           }
           if(Node.left()!= null){
               stapel.push(Node.left().content());
               counter++;
           }
           
       }
       
        return counter;
    }

VG Lazy

 

[fhoffmann]

Du solltest das rekursiv lösen:
Eine Methode countNodes() (bitte nicht static) zählt sich selbst mit 1 und addiert dazu den Rückgabewert von left.countNodes() (falls left != null) und den Rückgabewert von right.countNodes() (falls right!= null).
Wenn du diese Methode für root aufrufst, erhälst du die Anzahl der Knoten des Baumes.

 

[mihe7]

Mal als Hinweis: die Kindknoten sind Wurzelknoten der Teilbäume.

 

[Lazyyy]

Du solltest das rekursiv lösen:
Eine Methode countNodes() (bitte nicht static) zählt sich selbst mit 1 und addiert dazu den Rückgabewert von left.countNodes() (falls left != null) und den Rückgabewert von right.countNodes() (falls right!= null).
Wenn du diese Methode für root aufrufst, erhälst du die Anzahl der Knoten des Baumes.

ah ok so klappt es. Danke

Interesse halber würde mich noch die möglichkeit Interessieren die aufgabe mit dem Stack zu lösen. an welcher Stelle muss ich da in meinem Kode ansetzen ?

 

[Lazyyy]

Mal als Hinweis: die Kindknoten sind Wurzelknoten der Teilbäume.

gedanklich kann ich folgen .. ^^

 

[fhoffmann]

Interesse halber würde mich noch die möglichkeit Interessieren die aufgabe mit dem Stack zu lösen.

Wenn du es unbedingt mit einem Stack lösen willst, solltest du einen Stack<TreeNode> verwenden.

 

[Joah]

Ich glaube du hast einen Denkfehler gemacht. Ein Blatt im Baum kann nämlich beliebig viele Kinder haben...
Außerdem kannst du nicht den content des Knotens auf den Stack pushen und dann später daraus einen neuen TreeNode konstruieren, weil dann die Kindknoten (left / right verloren gehen).

Deine korrigierte (iterative) countNodes-Methode würde also so aussehen (getestet):

    public static int countNodes(TreeNode root) {
       int counter = 1;
       if(root == null) { // klammer nicht benoetigt
           return 0;
       }
       Stack<TreeNode> stapel = new Stack<>(); // korrektur auf treenode
      
       if(root != null){ //if nicht benoetigt da bereits oben abgefangen
           stapel.push(root);
       }
       while(stapel.empty() == false){
           TreeNode Node = stapel.pop(); // Korrektur    
           if(Node.right()!= null){
               stapel.push(Node.right()); // Korrektur. Ausserdem koennte man right direkt abrufen
               counter++;
           }
           if(Node.left()!= null){
               stapel.push(Node.left()); // Korrektur
               counter++;
           }
          
       }
      
        return counter;
    }

Schöner wäre aber so:

public int countNodes()
{
    int counter = 0;
    Stack<TreeNode> s = new Stack<>();
    s.push(this);
    while (!s.empty())
    {
        counter++;
        TreeNode n = s.pop();
        if (n.left != null)
            s.push(n.left);
        if (n.right != null)
            s.push(n.right);
    }
    return counter;
}

Wäre nur noch die Frage was schneller ist (iterativ oder rekursiv).