Rekursive Suche in einem Baum

[Moch]

Hallo,
Tut mir leid so eine vermutlich simple Frage zu stellen, aber ich bin so langsam total am verzweifeln.

Folgendes Problem:
Ich habe einen Binär-Baum, dessen Blätter/Knoten bestimmte Merkmale enthalten. Derzeit brauche ich eine Such-Function, die rekursiv ein Blatt mit einer bestimmten Eigenschaft sucht.

Vereinfachtes Beispiel:
- Der Baum beinhaltet in jedem Knoten/Blatt einen Character (keine duplikate) und eine ID für diesen

Ich suche nun nach der ID für einen Char, als muss ich besagten charakter im baum finden.

Leider kriege ich die verdammte Rekursion überhaupt gar nicht mehr hin und weiß nicht warum.
Ich komme immer wieder nur auf null-Pointer oder nur den äußerst linken Knoten raus.

Könnte mir einer in Pseudecode nochmal verdeutlichen, wie ich diese rekursive Suche aufbauen muss, damit alle Knoten durchsucht werden bzw. solange gesucht wird, bis der passende gefunden wurde.
Vielleicht starre ich einfach schon zu lange auf den Quelltext (muss zeitig fertig werden) und stelle mich deswegen dumm an.
Egal, was ich auch anstelle, entweder gibt die function überall null zurück oder gibt nur den äußerst linken Knoten zurück.
Logisch ist also, dass meine Ansätze ins leere laufen, oder aber die rechten teilbäume nicht mehr ablaufen...

liebe Grüße
ein verzweifelter Moch

Edit: genutzt sprache ist Ada95, aber ich verstehe auch den Quellcode von Java, Delphi und Haskell sehr gut... Ada95 ist Delphi sehr ähnlich.

 

[XHelp]

Könnte so ähnlich wie das da aussehen:

public IdDatenTyp suche(Knoten k, char c) {
  if (k==null) {
    return null;
  }
  if (k.getChar()==c) {
    return k.getID();
  }
  IdDatenTyp id = suche(k.getLinkerKnoten(), c);
  if (id!=null) {
    return id;
  }
  return suche(k.getRechterKnoten(),c);
}

 

[Moch]

Irgendwie stehe ich trotzdem auf dem schlauch... vielleicht kannst Du hier den Fehler finden?

der HuffmanTree besteht aus folgendem:
Char: Character;
Anz: Integer; -- gibt Anzahl an
left: Huffmantree:
right: HuffmanTree;
Code: unbounded_String;

(Ada ist NICHT caseSensitiv)
Der zugehörige Baum sieht in etwa wie folgt aus
# sind nur Knoten, die hierbei nicht beachtet werden müssen

   #-------------------#
   |                           |
u---f                    #-----------#
                          |                  |
                       a -- h           m -- n

   FUNCTION FindNode(Huff: HuffmanTree; C: Character) RETURN HuffmanTree is
      HT: Huffmantree := Huff;
      CS: Character := C;
      HR: Huffmantree;
      HS: Huffmantree := huff;

      begin
         IF(Ht.Char = Cs) THEN
            RETURN Ht;
         END IF;
         
         IF(Ht.Left /= NULL) THEN
            Hr := FindNode(Ht.Left, Cs);
         END IF;
         IF(Hr /= NULL) THEN
            RETURN Hr;
         END IF;
         
         ht:= hs;
         IF(Hr = NULL) THEN
            IF(Ht.Right /= NULL) THEN
               Hr := FindNode(Ht.Right, Cs);
            END IF;
            
         END IF;
         
         IF(Hr /= NULL) THEN
            RETURN Hr;
         END IF;
         
         IF(Hr = NULL) THEN
            RETURN NEW HuffmanTreeNode'('/', 0, NULL, NULL, To_Unbounded_String("FAILED"));
         END IF;
         

      end findNode;

Ich kriege immer nur das u ausgegeben... der Rest sind null-Pointer... ich finds einfach nicht mehr raus -.-

 

[Moch]

Das Problem hat sich gelöst.
Habe jetzt einen Zähler eingebaut, der den Dummy nur dann erzeugt, wenn der zähler > 2 ist ... bei jedem Rekursionsschritt wird dieser um 1 erhöht.

Hier meine funtkionierende Function, falls noch wer auf dieses Problem stößt.

Danke für Deine Mithilfe 🙂

   FUNCTION FindNode(Huff: HuffmanTree; C: Character; Counter: Integer) RETURN HuffmanTree is
      HT: Huffmantree := Huff;
      CS: Character := C;
      HR: Huffmantree;
      HS: Huffmantree := Huff;
      Count : Integer := Counter +1;

      begin
         IF(Ht.Char = Cs) THEN
            RETURN Ht;
         END IF;
         
         IF(Ht.Left /= NULL) THEN
            Hr := FindNode(Ht.Left, Cs, Count);
         END IF;
         IF(Hr /= NULL) THEN
            RETURN Hr;
         END IF;
         
         ht:= hs;
         IF(Hr = NULL) THEN
            IF(Ht.Right /= NULL) THEN
               Hr := FindNode(Ht.Right, Cs, Count);
            END IF;
            
         END IF;
         
         IF(Hr /= NULL) THEN
            RETURN Hr;
         END IF;
         
         IF(Hr = NULL) THEN
            if(count < 2) then
               RETURN NEW HuffmanTreeNode'('/', 0, NULL, NULL, To_Unbounded_String("FAILED"));
               end if;
         END IF;
         return null;

      end findNode;