hilfe bei programmierung eines suchbaumes

morpheus0023

hallo,

würde mich freuen wenn mir einer weiter helfen könnte.
ich möchte aus der kommandozeile zahlen in einen suchbaum(binärbaum) einsortieren, und mit entsprechender anschaulicher ausgabe ausgeben.
ich habe soweit alles programmiert, nur mit der ausgabe funzt es nicht so richtig.

kann mir damit jemand weiter helfen?

gruß
morpheus

prolog

Hallo,

Wo hängts denn bei der Ausgabe ? Zeig am besten mal den Code mit Beschreibung was nicht funktioniert.

morpheus0023

#include <stdio.h>
#include <stdlib.h>

struct knoten
{
	int wert;
	struct knoten *links;
	struct knoten *rechts;
};

typedef struct knoten KNOTEN;

int zahl;

KNOTEN *einordnen(KNOTEN *zeiger)
{
   if(zeiger==NULL)
      {
         zeiger=(KNOTEN *)malloc(sizeof(KNOTEN));
         if(zeiger==NULL)
            {
               printf("Konnte keinen Speicherplatz "
                      "reservieren!!!\n");
               return;
            }
         zeiger->wert=zahl;
         zeiger->links=zeiger->rechts=NULL;
      }
   else if(zeiger->wert >= zahl)
      zeiger->links=einordnen(zeiger->links);
   else if(zeiger->wert < zahl)
      zeiger->rechts=einordnen(zeiger->rechts);
   return (zeiger);
}
void zeige_baum(KNOTEN *zeiger)
{
   if(zeiger != NULL)
   {
      printf("\n%d->",zeiger->wert);
      zeige_baum(zeiger->rechts);
      zeige_baum(zeiger->links);
   }
}
int main(int argc, char *argv[])
{
  KNOTEN *wurzel=NULL;
	int i;

	for(i=1; i<argc; i++)
	{
		zahl=atoi(argv[i]);
	         wurzel=einordnen(wurzel);
	}
  zeige_baum(wurzel);

return 0;
}

ich weiß einfach nicht wie ich am besten die zeige_baum funktion programmieren soll, so dass man den baum dieser reihenfolge ausgegeben wird:
Rechter Teilbaum, Wurzel, Linker Teilbaum

elise

ich würde sagen, dazwischen..

du hast im grunde folgende möglichkeiten:

Infix (= in-order)
    linker Kindknoten, dann Information, dann rechter Kindknoten; 
Präfix (= pre-order)
    Information, dann linker Kindknoten, dann rechter Kindknoten; 
Postfix (= post-order)
    linker Kindknoten, dann rechter Kindknoten, dann Information;

hier ein kleiner pascalauszug:

procedure tidyup (t:pTree; h:integer);
var i:integer;
begin
    if (t <> nil) then
        with t^ do begin
            tidyup(right, h+1);
            for i :=1 to h do write ('-');
            writeln(data);
            tidyup(left, h+1);
    end
end;

morpheus0023

hmm ja also, könntest du mir das passent für mein programm schreiben?
dafür wäre ich dir sehr dankbar.

elise

ich schau mir die einfuegen nicht an, schreibe nur pascal eben um..

musst den kopf nach links drehen, und dir einen baum vorstellen.

void zeige_baum(KNOTEN *zeiger, int h)
{
   if(zeiger != NULL)
   {
      zeige_baum(zeiger->rechts, h+1);
	  for (int i =0; i<h; i++)
		  printf ("-"); 
	  printf("%d\n",zeiger->wert);
      zeige_baum(zeiger->links, h+1);
   }
}

ps: ich würde mit einem array testen, dann bist du sicher, ob alles stimmt, wie du es machen sollst.

int array[10]={3,2,7,11,555,4,2,5,4,0};
    for(i=0; i<10; i++)
    {
        zahl=array[i];
        wurzel=einordnen(wurzel);
    }
  zeige_baum(wurzel, 0);

hi torsten, na das haben wir doch gestern fein hingekriegt!

also elise (mhhh...)
gefragt war die ausgabe umgekehrt zum infix, also rechts, wurzel, links
hier die lösung des problems:

eine zählerschleife ist hierfür leider nicht geeignet da du damit nicht beliebige binärsuchbäume konstruiren kannst, eine rekursion umgeht dabei das parentproblem das du irgendwann einen zweig höher springen musst:

void zeige_baum(KNOTEN *zeiger)
{
   if(zeiger->rechts != NULL)zeige_baum(zeiger->rechts);

   printf("\n%d->",zeiger->wert);

   if(zeiger->links != NULL)zeige_baum(zeiger->links);
}

das war des rätsels lösung...

elise

??
ist doch meine lösung gewesen.. genau dasselbe, bis darauf, daß ich noch eine graphische ausgabe mit eingebaut habe.. (nur falls diese komische schleifenantwort auf meine strichschleife in der mitte folgte.. dann bitte den code nochmal genau anschauen und nachdenken )

na mir egal, war ja nicht meine aufgabe geht auch ohne schöne graphik.

sorry, ja jetzt wo du es sagst, hab da das letzte mal einfach zu schnell drübergeschaut, tausendfache entschuldigung und ehrerbietung...

elise

picknick weiter