Methoden BinaryTree transformieren Aufgabe

Diskutiere BinaryTree transformieren Aufgabe im Java Basics - Anfänger-Themen Bereich.
T

TobiCodi

Ich hänge seit Stunden über dieser Aufgabe und komme einfach nicht weiter... daher schick ich sie jetzt einfach mal rein, vielleicht kann mir jemand weiterhelfen :)

Aufgabe:
Implementieren Sie die Methode transformTree(), welche eine Wurzel des Types TreeNo- deBinary, und somit auch den Baum, übergeben bekommt, und einen neuen Baum des Types TreeNodeBinaryLevel konstruiert. Der neue Baum soll um die Information current- Level erweitert werden, welche beschreibt, auf welcher Höhe sich der betrachtete Knoten befindet, wobei eine Wurzel immer die Höhe 0 hat, und bei jeder weiteren Ebene das Attribut currentLevel um 1 inkrementiert wird. Zurückgegeben soll die Wurzel des neuen Baumes, wobei die Struktur des Baumes und die Arraylisten der Knoten identisch sein sollen, inklusive der neu berechneten Information currentLevel.

Zusatzinformationen:
Achten Sie darauf, dass alle Klassen, mit denen die Knoten initialisiert werden, gema ̈ß der Hierarchie in der Baumstruktur auch die Klassenhierarchie in Java umsetzen. Dies kann bedeuten, dass die Wurzel die Oberklasse aller anderen Klassen der Knoten nutzt, und die Bla ̈tter Unterklassen der Wurzel, als auch aller Klassen der Knoten nutzt, die auf dem Weg zu den Bla ̈ttern traversiert werden mu ̈ssen. Bedenken Sie jedoch, dass die Methoden Ihrer Implementierung u ̈ber kein Wissen der Klassenhierarchie verfu ̈gen. Dies fu ̈hrt dazu, dass Ihre Methoden schwa ̈chere Annahmen umsetzen mu ̈ssen, und implizieren somit, dass ggf. sich der generische Typ eines Ihrer Knoten und der dazu geho ̈rige Klassenparameter, der in der Klasse des Knotens gesetzt wird, unterscheiden.
Nehmen Sie auch zur Kenntnis, dass die Knoten der Klasse TreeNodeBinary u ̈ber ein Attribut keys des Types ArrayList verfu ̈gen, welches den Inhalt der Knoten darstellt. Diese Attribute sind abha ̈ngig von einem generischen Parameter.

Hier meine TreeNodeBinary Klasse:
Java:
import java.util.ArrayList;

public class TreeNodeBinary<T> {

    public Class<T> type;
    public ArrayList<T> keys;
    public TreeNodeBinary<? extends T> left;
    public TreeNodeBinary<? extends T> right;

    public TreeNodeBinary() {

    }

    public TreeNodeBinary(Class<T> type) {
        this.type = type;
    }

    /**
     * @return the generic type of the node
     */
    public Class<T> getType() {
        return type;
    }

}
Hier meine TreeNodeBinaryLevel Klasse:
Java:
import java.util.ArrayList;

public class TreeNodeBinaryLevel<T> {

    public Class<? extends T> type;
    public ArrayList<T> keys;
    public TreeNodeBinaryLevel<? extends T> left;
    public TreeNodeBinaryLevel<? extends T> right;
    public int currentLevel;

    public TreeNodeBinaryLevel(Class<? extends T> type) {
        this.type = type;
    }

    /**
     * @return the generic type of the node
     */
    public Class<? extends T> getType() {
        return type;
    }

}
Und hier nur das, wo mein Problem liegt: die transformTree() Methode, soweit wie ich es verstehe (ist halt nicht richtig):

Java:
public class GenericOperations {

    public static <T> TreeNodeBinaryLevel<T> transformTree(TreeNodeBinary<T> root) {
        int currentLevel;
        TreeNodeBinaryLevel newTree = new TreeNodeBinaryLevel(/*Class*/ null);

        if(/*node*/ == 0) {
            currentLevel = 0;
        }else {
            //calculate current Level
        }
        
        //expand newTree via information "currentLevel"
    
        return newTree.root; //return root of newTree
    }
}

Tausend Dank für jede Antwort!!!
 
mihe7

mihe7

Jeder Knoten eines Baums ist selbst wieder ein Baum -> Rekursion.

Ein TreeNodeBinaryLevel ist vom gleichen type und enthält die gleichen keys wie ein TreeNodeBinary, außerdem verfügt er über eine Höhe. Darüber hinaus hält er Zeiger auf die transformierten Kinder left und right, die sich eine Ebene tiefer befinden...
 
T

TobiCodi

@mihe7 vielen Dank für deine Antwort! Aber wie kann man sich das "Jeder Knoten eines Baums ist selbst wieder ein Baum" vorstellen? Jeder Knoten ist doch nur ein Knoten und erst mehrere Knoten bilden einen Baum, oder verstehe ich das falsch? :/

LG
 
mihe7

mihe7

Oops, da hast Du Recht, das war falsch formuliert: jeder Knoten eines Baums ist selbst Wurzel eines Baums.
 
mihe7

mihe7

Jetzt noch schnell die Kurve kriegen: ein Baum ist durch die Wurzel gegeben, daher die saloppe Formulierung "ist selbst wieder ein Baum" :)
 
T

TobiCodi

Wäre folgendes ein sinnvoller Pseudo-Code:
Java:
public static <T> TreeNodeBinaryLevel<T> transformTree(TreeNodeBinary<T> root) {
        
        transformNode(node, level){
            newNode = new TreeNodeBinaryLevel();
            newNode.level = level;
            if(node.left) {
                newNode.left=transformNode(left, level+1)
            }
            if(node.right) {
                newNode.right=transformNode(right, level+1)
            }
            return newNode;
        }
        
        return transformNode(root, 0);
    }
 
T

TobiCodi

Wäre folgendes ein sinnvoller Pseudo-Code:
Java:
public static <T> TreeNodeBinaryLevel<T> transformTree(TreeNodeBinary<T> root) {
      
        transformNode(node, level){
            newNode = new TreeNodeBinaryLevel();
            newNode.level = level;
            if(node.left) {
                newNode.left=transformNode(left, level+1)
            }
            if(node.right) {
                newNode.right=transformNode(right, level+1)
            }
            return newNode;
        }
      
        return transformNode(root, 0);
    }
Das bringt mich jetzt in die schwierigkeit, wie ich "node" und "level" bekomme... wobei ich doch ein public int currentLevel in den Klassen TreeNodeBinary bzw. TreeNodeBinaryLevel habe
 
Zuletzt bearbeitet:
T

TobiCodi

Stimmt :rolleyes::D.. mein Code sieht nun so aus:
Java:
public static <T> TreeNodeBinaryLevel<T> transformTree(TreeNodeBinary<T> root) {
 
         transformNode(root, TreeNodeBinaryLevel.currentLevel){
            newNode = new TreeNodeBinaryLevel();
            newNode.currentLevel = currentLevel;
            if(root.left) {
                newNode.left=transformNode(left, currentLevel+1)
            }
            if(root.right) {
                newNode.right=transformNode(right, currentLevel+1)
            }
            return newNode;
        }
        
        return transformNode(root, 0);
    }
 
T

TobiCodi

Stimmt :rolleyes::D.. mein Code sieht nun so aus:
Java:
public static <T> TreeNodeBinaryLevel<T> transformTree(TreeNodeBinary<T> root) {

         transformNode(root, TreeNodeBinaryLevel.currentLevel){
            newNode = new TreeNodeBinaryLevel();
            newNode.currentLevel = currentLevel;
            if(root.left) {
                newNode.left=transformNode(left, currentLevel+1)
            }
            if(root.right) {
                newNode.right=transformNode(right, currentLevel+1)
            }
            return newNode;
        }
       
        return transformNode(root, 0);
    }
Ich hab noch ein Problem mit dem currentLevel ... das ist doch wie schon geschrieben in den anderen Klassen initialisiert, soll ich das in meiner Methode irgendwie (durch TreeNodeBinaryLevel.currentLevel -> geht nicht, da nicht static) aufgreifen oder soll Ichs neu initialisieren? hmm..
 
mihe7

mihe7

Ein paar Korrekturen:
Java:
public static <T> TreeNodeBinaryLevel<T> transformTree(TreeNodeBinary<T> root) {
    return transformNode(root, 0);
}

public static <T> TreeNodeBinaryLevel<T> transformNode(TreeNodeBinary<T> node, int level) {
    TreeNodeBinaryLevel<T> newNode = new TreeNodeBinaryLevel<>(node.type);
    newNode.currentLevel = level;
    if(node.left) {
        newNode.left=transformNode(node.left, level+1)
    }
    if(root.right) {
        newNode.right=transformNode(node.right, level+1)
    }
    return newNode;
}
Hoffe mal, dass ich nichts übersehen habe.

EDIT: die keys fehlen natürlich noch...
 
T

TobiCodi

Ein paar Korrekturen:
Java:
public static <T> TreeNodeBinaryLevel<T> transformTree(TreeNodeBinary<T> root) {
    return transformNode(root, 0);
}

public static <T> TreeNodeBinaryLevel<T> transformNode(TreeNodeBinary<T> node, int level) {
    TreeNodeBinaryLevel<T> newNode = new TreeNodeBinaryLevel<>(node.type);
    newNode.currentLevel = level;
    if(node.left) {
        newNode.left=transformNode(node.left, level+1)
    }
    if(root.right) {
        newNode.right=transformNode(node.right, level+1)
    }
    return newNode;
}
Hoffe mal, dass ich nichts übersehen habe.
schonmal vieeeeelen Dank dass du mir noch hilfst!!! <3
 
T

TobiCodi

denkst du es gibt eine Möglichkeit das in eine Methode zu packen? Das wäre nämlich meine Aufgabe.. :/
 
mihe7

mihe7

Man kann jede Rekursion auch iterativ lösen. Zum Compiler-Problem: das muss if (node.right != null) { heißen.
 
T

TobiCodi

Nun noch die frage wie ich die keys mitschleppe.. ich hätte da an sowas gedacht:

Java:
public static <T> TreeNodeBinaryLevel<T> transformTree(TreeNodeBinary<T> root) {
        return transformNode(root, 0, root.keys);
    }

    public static <T> TreeNodeBinaryLevel<T> transformNode(TreeNodeBinary<T> node, int level, ArrayList<T> keys) {
        TreeNodeBinaryLevel<T> newNode = new TreeNodeBinaryLevel<>(node.type);
        newNode.currentLevel = level;
        if(node.left != null) {
            newNode.left=transformNode(node.left, level+1, node.keys);
        }
        if(node.right != null) {
            newNode.right=transformNode(node.right, level+1, node.keys);
        }
        return newNode;
    }
 
T

TobiCodi

Also wäre es damit gemacht
Java:
    public static <T> TreeNodeBinaryLevel<T> transformTree(TreeNodeBinary<T> root) {
        return transformNode(root, 0);
    }

    public static <T> TreeNodeBinaryLevel<T> transformNode(TreeNodeBinary<T> node, int level) {
        TreeNodeBinaryLevel<T> newNode = new TreeNodeBinaryLevel<>(node.type);
        newNode.currentLevel = level;
        if(node.left != null) {
            newNode.left=transformNode(node.left, level+1);
        }
        if(node.right != null) {
            newNode.right=transformNode(node.right, level+1);
        }
        newNode.keys = node.keys;
        return newNode;
    }
 
Thema: 

BinaryTree transformieren Aufgabe

Passende Stellenanzeigen aus deiner Region:
Anzeige

Neue Themen

Anzeige

Anzeige
Oben