Baum: Pfad ausgeben

[P_P]

Hallo Forum!
Ich bin neu hier und habe auch gleich ein Problem...
Ich habe wie folgt einen Baum deklariert:

Delphi-Quellcode:

TYPE TPtr = ^TNode;

TNode = RECORD

      i: integer;

      c: string[2];

      left, right: TPtr;

END;

Desweiteren habe ich einen Typ TNodesArray deklariert:

Delphi-Quellcode:

TNodesArray = ARRAY OF TNode;

Dann baue ich aus einem solchen Array einen Baum:

Delphi-Quellcode:

PROCEDURE HuffTreeBauen(var BlaArray: TNodesArray; var root: TNode);
VAR node, node2: TPtr;

    hs: string[2];

    i: integer;

BEGIN

  Sort(BlaArray);

   WHILE length(BlaArray) > 1 DO

   BEGIN

      new(node);

      node^ := BlaArray[0];

                new(node2);

                node2^ := BlaArray[1];

                BlaArray[0].i := BlaArray[0].i + BlaArray[1].i;

                BlaArray[0].left := node;

                BlaArray[1].right := node2;

                Test(BlaArray[0], 1);

      FOR i := 1 TO length(BlaArray) - 2 DO

         BlaArray[i] := BlaArray[i + 1];

      SetLength(BlaArray, (length(BlaArray) - 1));

      Sort(BlaArray); 

   END;

   root := BlaArray[0];

END;

... um dann den Pfad zu einem Zeichen als Folge von 0en und 1en ausgeben zu können:

Delphi-Quellcode:

FUNCTION Pfad(root: TPtr; x: char): string;
BEGIN
   found := FALSE;
   IF root^.c[1] <> x THEN
   BEGIN
        IF ((root^.left <> NIL)) THEN
                  BEGIN
                    result := '0' + Pfad(root^.left, x); 
                    IF ((NOT found){  AND (root^.right <> NIL)}) THEN
                       result := '1' + Pfad(root^.right, x);
      END;
  END
  ELSE
  BEGIN
      result := '';
      found := TRUE;
  END;
END;

Und hier kommt mein Problem:
Wenn ich den auskommentierten Teil in der letzten Funktion weglasse, krieg ich ne Access Violation, wenn der Teil als Bedingung dabeibleibt, wird die Anweisung nie ausgeführt...
Ich bekomme immer nur '00' oder '000' oder dergleichen raus...

Hoffentlich kann mir hier jemand helfen!

Liebe Grüße,
Peter

[daywalker9]

Was ist den in deiner letzten Funktion "X" ?

[P_P]

Oh, sorry ich editiere mal den ertsen Beitrag...

So..
Hab ihn editiert:
x ist ein das Zeichen, nach dem gesucht werden soll!

[himitsu]

Wo ist found deklariert?

Wenn du AND (root^.right <> NIL) wegläßt, dann kann es vorkommen, daß root^.right auch mal NIL ist.
Und wenn dieses NIL ist, dann will das nächste (nach dem neuen Aufruf von Pfad) root^ einen NIL-Pointer dereferenzieren, was natürlich nicht geht.


Sicher daß root^.right innerhalb der root^.left-Befingung ausgewertet werden muß?

[P_P]

Argh!
found ist lokale Variable in "Pfad".

Naja, so wie der Baum aufgebaut wird, ist an allen Knoten, die links auf NIL zeigen auch rechts Ende, also zeigen beide auf NIL.

Ich bin mir inzwischen garnicht mehr sicher, ob da überhaupt etwas richtig ist...

[himitsu]

Zitat:

Zitat von P_P

Argh!
found ist lokale Variable in "Pfad".

Das ab ich gehofft. :mrgreen:
(wobei viele ja gerne globale Variablen verwenden :wall: )

Es ist aber auch immer schön, wenn wichtige Dinge einfach weggelassen werden, so wie z.B. irgendwelche Dekarationen. :zwinker:

So ala:

Delphi-Quellcode:

FUNCTION Pfad(root: TPtr; x: char): string;

VAR fount: Boolean;

BEGIN 
  ...

Zitat:

IF ((NOT found){

Gut, dann geh mal von diesem IF nach oben
und schau ob/wo dieses "found" überhaupt mal TRUE werden kann.

Wenn nicht, dann ist es immer FALSE und somit würde dieser IF-Zweig immer ausgeführt, selbst wenn er es womöglich nicht sollte.


[add]
Eventuell meinst du es so?

Delphi-Quellcode:

FUNCTION Pfad(root: TPtr; x: char): string;
BEGIN
   IF root^.c[1] <> x THEN
   BEGIN
      IF Assigned(root^.left) THEN
          result := '0' + Pfad(root^.left, x)
      ELSE
          IF Assigned(root^.right) THEN
              result := '1' + Pfad(root^.right, x)
          ELSE
              result := '';
  END
  ELSE
      result := '';
END;

[P_P]

Ja, kann es, wenn

Delphi-Quellcode:

root^.c[1] <> x

erfüllt ist...
Ich verstehe jetzt nicht, wie du das meinst?!

Ich glaube nicht, dass dein Edit den Zweck erfüllt, da ich denke, dass die Suche in den Teilbäumen rechts/links ja "auf der selben Ebene" erfolgen müsste...
Das funktioniert so denke ich mal nicht, da ja eigentlich dort, wo root^.left = NIL ist, auch root^.right = NIL ist, oder zumindest sein sollte...

[himitsu]

Delphi-Quellcode:

FUNCTION Pfad(root: TPtr; x: char): string;
var found: Boolean;
BEGIN
   found := FALSE;
   IF root^.c[1] <> x THEN
   BEGIN
      IF ((root^.left <> NIL)) THEN
      BEGIN
          result := '0' + Pfad(root^.left, x);
          IF ((NOT found){  AND (root^.right <> NIL)}) THEN
              result := '1' + Pfad(root^.right, x);
          // vor diesem IF ist found immer false, da es nirgendwo "vorher" auf TRUE gesetzt wird.
      END;
  END
  ELSE
  BEGIN
      result := '';
      found := TRUE;
      // hier ist die einzige Stelle, wo found auf True umgestellt wird
      // aber hiernach wird die Funktion verlassen und es ist demnach eh egal
  END;
END;

[P_P]

Wieso wird die Funktion dort verlassen?
Ich könnte doch auch THEN und ELSE vertauschen, wenn ich die Bedingung ändere:

Delphi-Quellcode:

FUNCTION Pfad(root: TPtr; x: char): string;

VAR   found: boolean;

BEGIN


   found := FALSE;

   IF root^.c[1] = x THEN

BEGIN

      result := '';
        found := TRUE;

   END
ELSE
   
BEGIN

        IF ((root^.left <> NIL)) THEN

      BEGIN

        result := '0' + Pfad(root^.left, x); 

        IF (NOT found  AND (root^.right <> NIL)) THEN result := '1' + Pfad(root^.right, x);
      END;

  END;
END;

[himitsu]

Na weil nach dem ELSE-Block die Funktion zu Ende ist?

Und selbst wenn du es vertauschst, bleibt es dabei, da ENTWEDER der IF-Block ODER der ELSE-Block ausgeführt wird.

[P_P]

Okay... Dann lasse ich es eben weg.
Aber dein obig genanntes funktioniert m.E. trotzdem nicht, da ja für alle Knoten entweder root^.left UND root^.right = NIL sind oder eben keines...

[himitsu]

Zitat:

Zitat von P_P

da ja für alle Knoten entweder root^.left UND root^.right = NIL sind oder eben keines...

Das kann etwas nicht stimmen, denn dann würde es mit und ohne deinen auskommentierten Teil keinen unterschied geben, da dieser in diesem Fall immer True ergeben würde (da ja Links existiert) und es somit keinen Unterschied macht.

Und wenn das Stimmt, dann wäre wohl dein Baum defekt, bzw. er würde nicht deiner Spezifikation entsprechen.




Nja, ich weiß aber auch nicht wie die Daten in diesem Baum liegen
und da kann man auch schlecht etwas planen.

Hatte da einfach nur versucht logisch zu denken
- entweder X ist gefunden, dann wird hier abgebrochen
- oder ist Links etwas, dann wird eine 0 angehängt
- oder Rechts ist was, dann wird eine 1 angehängt
- oder es gibt nichts, dann wird hier abgebrochen

Der Code von dir macht
(das lokale "found" ignoriert, da es ja eh nichts macht
und der auskommentierte Teil ist enthalten)
- entweder X ist gefunden, dann wird hier abgebrochen
- entweder ist Links etwas, dann wird eine 0 angehängt
- oder Links und Rechts ist was (und found ist false), dann wird eine 1 angehängt
- oder es gibt nichts, dann wird hier abgebochen und Result ist zufällig, da es nicht initialisiert wurde (aber dieses würde maximal nur das Ende des String/Result mit eventuell zufälligen Werten belegen und keine Exception auslösen)

[P_P]

Also ich habe einen kleinen Fehler beim Erstellen des Baumes.
Eigentlich hab ich den Quellcode dazu mitgeposted, damit man ja sieht, wie der Baum gebaut wird...

Deine o.g. Funktion bringt ebenfalls nur '0', '00', '000' etc. ...