BinaerBaeume unter C "richtig" ausgeben...

[neverbeenhere]

einfach show_tree noch einen parameter x und y mitgeben, wenn du eine ebene tiefer gehst, also show_tree aufrufst, muss y größer werden. beim show_tree-aufruf für links muss x wieder etwas kleiner als das übergebene x sein und beim show_tree-aufgruf für rechts halt größer... sollte man grafisch irgendwie lösen, rein konsolen/textbasiert ist das nicht so einfach, brauch man ne menge ausgabe-formatierungen -> umständlich

[PAD]

wofür brauchst du parent ?

[neverbeenhere]

nur für show_tree ist es sinnlos, aber ansonsten für baumstrukturen unabdingbar, weil es mit sicherheit vorkommt, dass du das eine oder andere mal auch den baum von unten hochsteigen musst...

[PAD]

Verstehe ich nicht ganz, da ja normalerweise vom Rootnode aus rekursive gearbeitet wird?

[neverbeenhere]

schon klar, aber wenn du z.b. ein node löschen willst und nicht vom root ausgehst (weil den die funktion z.b. nicht hat), dann ist parent ziemlich nützlich

[PAD]

Wo willst du den Bauzm ausgeben Screen, Drucker, File?
Das einfachste ist File in ASCII.
den Baum durchlaufen das tiefste Element = größter Abstand zu Rootbestimmen
Im Baum das äußerst linke Element aufsuchen
von dort beginnend Blatt und Ast ablaufen und in die Datei drucken.
File:

Nodename
               Nodecontents  
               Tiefe 4        \ 
Nodename                        Nodename 
Nodecontents                    Nodecontents
Tiefe 5      \                / Tiefe 3      \
               NodeName         
               Nodecontents  
               Tiefe 4         

.......

Aus dieser Darstellung im File kann man dann jede beliebige Drucker/Graphik/Bilschirm erzeugen

Viel Spaß

[seraphin]

Danke erstmal bis hier!

@PAD: wie todo schon vermutet hat brauch den *parent um den baum nach dem loeschen eines Knotens wieder richtig zu verknuepfen.

Deine Loesung ist im Prinzip das was ich meine...nur...und da steh ich immer noch aufm schlauch...mir is das prinzip klar nur will mir nicht die passende syntax dazu kommen

Ich poste vielleicht mal meinen kompletten source:

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

// Einfacher eigener Datentyp node
typedef struct node {
  char *name;
  struct node *parent;
  struct node *left;
  struct node *right;
} node;

// Funktionsdefinitionen
node *create_node(void);
int insert_node(char *s);
int delete_node(char *s);
int show_tree(node *knoten);

node *anfang;

int main(void)
{
        //Auswahl  
	int choice=99;
	//Name des zu erstellenden Knotens
	char newname[10];
	//Name des zu loeschenden Knotens
	char delname[10];

	printf("BinaerBaum mit Loeschfunktion\n\n\n");

	//...letzendlich die Abbruchbedingung fuer das ganze Programm
	while (choice!=0)
	{

	printf("Knoten erstellen (1),loeschen (2),ausgabe (3) oder exit (0): ");
	scanf("%d",&choice);
	//Menuefuehrung
	switch(choice)
		{

	case 1:

	printf("\nBitte Bezeichnung des Knotens waehlen\n");
	//Eingabe des Bezeichners fuer den neuen Knoten
	scanf("%s",newname);
	//Erstellt den neuen Knoten
	insert_node(newname);
	printf("\nKnoten %s erstellt\n",newname);
		break;

	case 2:
	printf("\nBitte die EXAKTE(!!!) Bezeichnung des zu loeschenden Knotens eingeben\n");
	//Dasselbe in Gruen...
	scanf("%s",delname);
	delete_node(delname);
	printf("\nKnoten %s geloescht\n",delname);
		break;

	case 3:
		printf("\n Baum wird ausgegeben:\n\n");
		// Gib den Baum aus
		 show_tree(anfang);
			break;

		}
	printf("\n\n\n\n");
	}

printf("Programmende\n\n");
  return 0;
}

// Erstelle einen neuen Knoten (Speicher reservieren + Anfangswerte setzen)
node *create_node(void)
{
  // Reserviere Speicher fuer einen neuen Knoten
  node *knoten = malloc(sizeof(struct node));

  // Startwerte setzen
  knoten->name = NULL;
  knoten->parent = NULL;
  knoten->left = NULL;
  knoten->right = NULL;
  return knoten;
}

// Fuege einen neuen Knoten in den Baum ein
int insert_node(char *s)
{
  node *knoten, *current, *last;
  int richtung = 0;
  int vergleich = 0;

  // Neuen Knoten erstellen
  if( (knoten = create_node()) == NULL) 
    { 
      printf("Duh! We ran out of memory! :-(\n");
      exit(1);
    }

  // Speicher fuer den String allozieren
  knoten->name = malloc(sizeof(*s));
  strcpy(knoten->name,s);

  // Hat der Baum schon eine Wurzel?
  if(anfang == NULL)
    {
      anfang = knoten;
    }
  else
    {
      // Hangel Dich vom Anfang durch den Baum...
      current = anfang;

      // ...und suche die passende Speicherstelle
      while(current != NULL)
	{
	  // Merke Dir den letzten Ast
	  last = current;

	  // Vergleiche die Strings
	  vergleich = strcmp(knoten->name,current->name);

	  // Wenn der einzufuegende String "kleiner" ist,
	  // dann gehts links lang
	  if(vergleich < 0)
	    {
	      richtung = 0;
	      current = current->left;
	    }

	  // Wenn er groesser ist, gehts rechts lang
	  else if(vergleich > 0)
	    {
	      richtung = 1;
	      current = current->right;
	    }

	  // Diesen String gibt es schon im Baum
	  else
	    {
	      printf("insert_node(): String %s exists!\n",s);
	      return 1;
	    }
	}

      // Vater des einzufuegenden Knotens setzen
      knoten->parent = last;

      // Ist der neue Knoten links oder rechts vom Vater?
      if(richtung == 0)
	{
	  last->left = knoten;
	}
      else
	{
	  last->right = knoten;
	}
    }

  return 0;
}

// Loesche einen Knoten aus dem Baum
int delete_node(char *s)
{
  node *current, *parent, *new;
  int vergleich = 0;
  int richtung = 0;

  // Suche den zu loeschenden Knoten
  current = anfang;

  while(current != NULL)
    {
      // Vergleiche die Strings
      vergleich = strcmp(s,current->name);

      // Wenn der String "kleiner" ist, bieg links ab
      if(vergleich < 0)
	{
	  richtung = 0;
	  current = current->left;
	}

      // Ist der String "groesser", bieg rechts ab
      else if(vergleich > 0)
	{  
	  richtung = 1;
	  current = current->right;
	}

      // Wir haben den passenden Knoten gefunden
      else
	{
	  break;
	}
    }

  // Keinen passenden Eintrag gefunden?
    if(current == NULL)
    {
      printf("delete_node(): Cant find node %s!\n",s);
      return 1;
    }

  // Loeschen wir gerade das Wurzel Element?
  if(current == anfang)
    {
      // Ist das Wurzel Element das letzte Element des Baums?
      if( (current->left == NULL) && (current->right == NULL) )
	{
	  anfang = NULL;
	}
      else
	{
	  // Gibt es einen linken Knoten?
	  if(current->left != NULL)
	    {
	      anfang = current->left;
	    }

	  // Ansonsten wird der rechte genommen
	  else
	    {
	      anfang = current->right;
	    }
	}
    }

  // Es wird nicht das Wurzel Element geloescht
  else
    {
      // Hat der zu loeschende Knoten noch Kindknoten?
      if( (current->left != NULL) || (current->right != NULL) )
	{
	  // Falls es einen linken Knoten gibt, nimmt dieser
	  // den Platz des zu loeschenden ein
	  if(current->left != NULL)
	    {
	      new = current->left;
	    }

	  // Ansonsten wird der rechte genommen
	  else
	    {
	      new = current->right;
	    }
	}
      else
	{
	  new = NULL;
	}

      // An welchem Ast des Vaters haengt der zu loeschende Knoten?
      parent = current->parent;

      if(richtung == 0)
	{
	  parent->left = new;
	}
      else
	{
	  parent->right = new;
	}
    }

  // Speicher des Knotens deallozieren
  free(current);

  return 0;
}

int show_tree(node *knoten)
{
  if(knoten != NULL)
    {

      // Funktion rekursiv fuer den linken und rechten Ast aufrufen

      show_tree(knoten->left);
	  // String ausgeben
	  if (knoten->parent != 0)
	// printf("%s hat den Elternknoten %s\n",knoten->name,knoten->parent->name);
	printf("%s\n",knoten->name);

      show_tree(knoten->right);
    }

  return 0;
}

sry wenn ich den eindruck erwecke das man mir es vorkauen muss...mit 4 stunden mehr schlaf faellts mir auch mit sicherheit ein...

[PAD]

dann hol dir den Schlaf

Wenn man einen Knoten löschen möchte mache ich dies immer an der Stelle wo der Parent steht, kann mit diesen dann lokal in einer Temporären Variablen merken, und muß nicht einen Pointer mitschleifen und sicherstellen, das er Richtig ist.

Was meinst du mit passender Syntax.

Das durchlaufen eines Binarbaums ist eine einfache Übung. Siehe Donald E Knuth.

Man fängt das meistens damit an, das man von Root aus solange den linken Ast wählt bis man bei einem Blatt ist.
danach geht man eins hoch prüft ob rechts eine Blatt ist falls jeht geht man dorthin und sucht wieder das äußerst linke Blatt in diesem Ast auf, falls nein geht man den Ast eins höher und fängt von vorne an.
..... Somit sieht man das ein rekursiver Prozess ist mit sinnvolen Wegebschreibungen und Abbruchbedingungen.

Beim ersten durchlauf sollte man sich die Tiefe des Baums mit merken jede Ebene die man tiefer hineinsteigt sollte man sich merken ist dies tiefer als die bisherige tiefste merkt man sich diese. Sinn der sache damit weis ich beim zweiten Durchlauf des Baumes wievele Leerzeichen ich vor den aktuellen Block drucken muß damit der tiefste ganz links steht und meiner aktuelle Knoten an der Richtigen Stelle ist.

Das zweite Durchlaufen (Traversieren??) sucht den äußerst linken Ast auf schreibt die bnötigte Anzahl von Leerzeichen (Maximaltiefe - aktueller Tiefe)* Anzahl_Zeichen_Pro_Block vor den Daten des aktuellen Blocks.
somit hast du deine Ausgabe

[neverbeenhere]

PAD schrieb:

Wenn man einen Knoten löschen möchte mache ich dies immer an der Stelle wo der Parent steht, kann mit diesen dann lokal in einer Temporären Variablen merken, und muß nicht einen Pointer mitschleifen und sicherstellen, das er Richtig ist.

irgendwie hab ich den eindruck, dass du was gegen parent hast... bist du so ein speichergeizkragen wenn die lösch-funktion als parameter nur einen ptr auf das zu löschende element bekommt, ist so ein parent-ptr ziemlich praktisch. ok, man kann natürlich, wenn der root-node global bekannt ist, vom root-node aus den node suchen, deren left oder right dem zu löschenden element entspricht, ist aber (vorallem bei größeren bäumen) ziemlich ineffizient, schon rein vom algo her....

[PAD]

Wenn man sinnvoll sparen kann, warum nicht . ich brauch doch nicht jedesmal von root aus suchen.
in der rekursion 1 Ebene höher und schon ist der Fisch geputzt. da muß ich ja sowieso hin um die Verknüpfung nach unten wieder zu machen.

Aber ich glaub das ist nicht das Primaerproblem von seraphin was hier behandelt wird.