n-ärer Baum

[Stormi1234]

Hallo,

ich hoffe ich bin hier richtig.
Ich versuche einen Baum zu implementieren, welchem ich die Höhe und den Verzweigungsfaktor angebe, und dieser sich dann mit zufälligen nummern erstellt (erstmal zweitrangig).
Allerdings komme ich nun einfach nicht weiter.
Hier mein momentaner Versuch:

public Tree(int b, int h) {   
    for (int i = 0; i <= h; i++) {
            insert();
        }

    }

    public void insert() {
        if (root == null) {
            root = new Node(t);
            root.setHeight(h);
        } else {
            insert(root);
        }

    }

    private void insert(Node parent) {
        for(int i=0;i<b;i++){
            Node child = new Node(t+1);
            child.setHeight(h-1);
            parent.addDaughter(child);   
           
            if(child.getHeight()!=0){
            insert(child);
            }

Ich bekomme einen StackOverflowError.

Vielen Dank für eure Hilfe.

 

[Tarrew]

Poste doch mal bitte deinen kompletten Code. Also inklusiv main-Methode und Node-Klasse etc.

 

[Stormi1234]

Hier meine main

public class Main {

    public static void main(String[] args) {
       
        Scanner scanner = new Scanner(System.in);
        System.out.println("Provide Branching Factor");
        int b= scanner.nextInt();
        System.out.println("Provide height");
        int h= scanner.nextInt();
        System.out.println("Provide Approximation");
        int approx= scanner.nextInt();
       
        System.out.println("Values provided:"+b+" , "+ h + " , " + approx);
       
        Tree newTree = new Tree(b,h,approx);
       
       
    }

}

Die Node Class:

public class Node {
    int e;
    private ArrayList<Node> daughter;
    int height;

   
    public Node(int e){
        this.daughter = new ArrayList<Node>();
        this.e = e;
    }
   
    public void addDaughter(Node childNode){
        this.daughter.add(childNode);
    }

    @Override
    public String toString() {
        return "Node [e=" + e + " height: " + height + ", daughter= " + daughter + "]\n";
    }

    public void setHeight(int h){
        this.height=h;
    }
   
    public int getHeight(){
        return this.height;
    }
   
}

Und die Tree Klasse:

public class Tree {
    public int b;
    public int h;
    public int approx;

    private Node root;
    public int t;
    private ArrayList<Node> tree;

    public Tree(int b, int h, int approx) {
        super();
        this.b = b;
        this.h = h;
        this.approx = approx;
        root = null;
        tree = new ArrayList<Node>();

        // Random T between -250 and +250
        Random randomGenerator = new Random();
        t = (randomGenerator.nextInt(500) - 250);

        for (int i = 0; i <= h; i++) {
            insert();
           
        }
        System.out.println(tree.toString());

    }

    public void insert() {
        if (root == null) {
            root = new Node(t);
            root.setHeight(h);
            tree.add(root);
   
        } else {
            insert(root);
        }

    }

    private void insert(Node parent) {
        for(int i=0;i<b;i++){
            int height=h-1;
            Node child = new Node(t+1);
            child.setHeight(height);
            parent.addDaughter(child);   
            tree.add(parent);
           
        }
    }

}

Alles etwas chaotisch.

 

[Tarrew]

Also ich habs mal mit ein paar Werten durchgespielt und kriege nie einen StackOverflow. Bei welchen Werten passiert das denn bei dir?

 

[Stormi1234]

Hab zwischen erstem und zweitem Post etwas an der Tree Klasse verändert. In der letzteren ist ja garkeine Rekursion drin. Sorry.
Aber es tut ja auch nicht was es tun soll.
Denn ich müsste ja für jeden Kindsknoten wieder b viele Kindsknoten erstellen, bis zur Höhe h.
Eigentlich dürfte dass ja nicht so schwer sein. Aber ich stecke irgendwie fest.

private void insert(Node parent) {
        for(int i=0;i<b;i++){
            int height=h-1;
            Node child = new Node(t+1);
            child.setHeight(height);
            parent.addDaughter(child);  
            tree.add(parent);
           // Rekursiver Aufruf
           insert(child);
        }
    }

 

[Tarrew]

Also ich habs mal kurz überflogen. Die Höhe des Baumes regelt sich ja eig. automatisch über die Rekursion. Deswegen solltest du die for-Schleife im Konstruktor nicht brauchen.

Außerdem willst du in der insert-Methode nicht jedes Kind zur tree-List hinzufügen. Jeder Knoten hat ja seine eigene Liste mit Kindern.

Hab das mal kurz angepasst:

import java.util.ArrayList;
import java.util.Random;

public class Tree {
    public int b;
    public int h;
    public int approx;

    private Node root;
    public int t;
    private ArrayList<Node> tree;

    public Tree(int b, int h, int approx) {
        super();
        this.b = b;
        this.h = h;
        this.approx = approx;
        root = null;
        tree = new ArrayList<Node>();

        // Random T between -250 and +250
        Random randomGenerator = new Random();
        t = (randomGenerator.nextInt(500) - 250);

        insert();

        System.out.println(tree.toString());

    }

    public void insert() {
        if (root == null) {
            root = new Node(t);
            root.setHeight(h);
            tree.add(root);

        }
        if(h>0){
            insert(root);
        }

    }

    private void insert(Node parent) {
        for (int i = 0; i < b; i++) {
            int height = parent.getHeight()-1;
            Node child = new Node(t + 1);
            child.setHeight(height);
            parent.addDaughter(child);
           
            // Rekursiver Aufruf
            if (height > 0) {
                insert(child);
            }
        }
    }

}

Es sah mir auf den ersten Blick relativ richtig aus. Aber ich kann diese Ausgabe schwer lesen und so spät kann ich mich eh schlecht konzentrieren

 

[Stormi1234]

Super, Danke dir.
So ne Kleinigkeit. Aber das kommt davon wenn man so spät abends noch programmiert.