Tiefe eines Baums (Java)

Archiv Algorithmik II
1

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

2

Tiefe eines Baums (Java)
Klausur 03/2002, Aufgabe 10 d)

Hier wurde ja mal ne Lösung zu dieser Klausur gepostet, die ist leider unvollständig. Und da ich jetzt nicht wirklich nen Plan hab, wie ich die Tiefe eines (binären) Baums rauskriegen soll, Frage an euch!

Ich kann mich erinnern, dass wir sowas mal in Algo1 mit Scheme und den Bäumen hatten, kann hier aber leider keine Aufgabe dazu finden.

Es war jedenfalls irgendwas mit: rekursiver Aufruf, Tiefe immer um 1 erhöhen, damit ich weiß, wo ich grad bin, und jedes Mal mit einem überlieferten Maximum vergleichen… genauer kann ich mich nicht erinnern. Reicht leider nicht für ein fertiges Programm :confused:

3

Du musst dazu einen Backtraking Algorithmus verwenden, und jedes Blatt besuchen(prüfen).

4

Ähm, muss ich mal nachschauen, was das ist.

Ich hab das nochmal ausprobiert und bin jetzt dieser Meinung:

class TreeNode
{
	//...
	int height(int depth)
	{
		if (left == null && right == null) return depth;

		int l = 0;
		int r = 0;
		if (left != null)  l = left.height(depth + 1);
		if (right != null) r = right.height(depth + 1);

		return Math.max(l, r);
	}
}

class Tree
{
	//...
	int height()
	{
		if (root == null) return 0;
		return root.height(1);
	}
}

Und hab meine bisherige Gesamtlösung zur 10 als Attachment drangehängt. Es lässt sich compilieren, aber ich hab die Funktion nicht getestet. Hab kein Bock da jetzt noch riesige Visualisierungen à la [m]toString()[/m] zu machen.

Attachment:
BinTree.zip: https://fsi.cs.fau.de/unb-attachments/post_7654/BinTree.zip

5

ja das sieht doch ziemlich gut aus!
duerfte funktionieren, wuerde ich sagen…

6

Hi

Du machst das etwas umständlich.

Vor allem aber musst du beachten, dass bei einem “leeren” Baum, also nur Wurzel, 0 rauskommen muss und nicht 1. Das ist explizit in der Aufgabenstellung verlangt.

deshalb würde ich sagen return root.height(1); müsste return root.height(0); heißen.

Ansonsten hab ich das irgendwie doch etwas “ganz anders” gemacht. Im Prinzip ist deine Lösung aber der richtige Ansatz bzw. sie ist wohl auch richtig :wink:

cu
Ford Prefect

p.s.: In Scheme war das aber viel toller :cool:

7

du mit deinem elendigen - räusper - scheme schon wieder… :wink:

[quote] if (root == null) return 0; [/quote]

ist dir das genug für die null?

[edit]
nee, habs nochmal gelesen. also ich versteh das so, dass

  • leer → 0 (“leerer Baum”)
  • nur wurzel → 1 (“ein Baum mit nur einem Knoten in der Wurzel”)
  • mehr → 2+ (“usw”)
    [/edit]

du könntest ja eigentlich mal deinen ansatz hier posten. würd mich mal interessieren, wie das (in java) noch zu vereinfachen wäre.

8

ich wuerde das so schreiben:

public class Tree {
    //...
    public int height () {
        return heightrek (root);
    }
    public int heightrek (TreeNode n) {
        if (n == null) {
            return 0;
        else {
            return 1 + Math.max (heightrek (n.right), heightrek (n.left));
        }
    }
}

das ist doch nochmal ein ganzes stueck kuerzer @yves und vom prinzip her so, wie wir es in scheme geloest haben @ford, oder?

9

leider kannst du von ‘außen’ nicht auf das left/right des nodes zugreifen.

10

wenn ich sie public definiere, schon!
und wenn nicht, dann muessen schnittstellenfunktionen à la TreeNode.getLeft() oder TreeNode.getRight() existieren, die ich dann benutze. aber public definieren ist einfacher…

11

du hast wohl das grundlegende konzept von klassen und private elementen nicht verstanden? :finger:

:wink:

12

davon steht ja nix in der angabe.

ausserdem habe ich es ja verstanden, bloss benutze ich es fuer solche pipifaxaufgaben nicht, wenn es nicht explizit verlangt ist :cool: .

13

Hi

Also dann hier mal meine Lösung. Ich finde es immer voll toll, wenn man Objekte einen Job erledigen lassen kann :-). Deswegen arbeite ich eigentlich immer mit objekteigenen Funktionen.

Da ich bei meinen Programmen gerne ein sparsamer Mensch bin, habe ich Treenode von Tree erben lassen, denn Treenode braucht alles, was Tree braucht + Parent.

Die folgende Funktion ist also in der Klasse Tree definiert und ruft sich selbst bei den weiterführenden Treenodes auf…
Deshalb muss man darauf Rücksicht nehmen, dass evtl. keine weiteren Treenodes anhängen. Hier nun der Code:

int height () {
	if (links == null) if (rechts == null) return 0;
		else return rechts.height() + 1;
	else if /* ich vermisse sehr elseif ;) */ (rechts == null) return links.height() + 1;
	else return Math.max(links.height(), rechts.height()) + 1;
}

Da ich davon ausgehe, dass es um die Ebenen geht und man bei 0 anfangen muss zu zählen, wird das hier auch so gehandhabt. Will man bei 1 anfangen zu zählen, returne man 1 beim ersten return.

Achja, die Lösung entspricht ungefähr der von Steppenwolf.

cu
Ford Prefect

14

mir faellt gerade auf, dass mir in meiner methode ein „static“ fehlt - jetzt ist sie korrekt: