Binärer Baum mit Strukturen (in C)

Question

Ich habe einen binären Strukturbaum. Die Struktur ist

typedef struct hashtag { 
     char *name; 
     int acc; 
    } *Item; 

Die Knoten werden von der Zeichenfolge organisiert. Ich möchte den Knoten drucken, der den höchsten acc hat, aber zuerst in alphabetischer Reihenfolge. Mein Code so weit:

Item search_max(link h) { 
     int max; 
     char *word; 
     Item hashtag = (Item)malloc(sizeof(struct hashtag)); 
     Item left = (Item)malloc(sizeof(struct hashtag)); 
     Item right = (Item)malloc(sizeof(struct hashtag)); 
     hashtag = h->item; 
     max = h->item->acc; 
     word = h->item->name; 
     if (h == NULL) 
      return 0; 
     left = search_max(h->l); 
     if (max == left->acc && less(left->name, word)) 
      word = left->name; 
     if (max < left->acc){ 
      max = left->acc; 
      word = left->name; 
     } 
     right = search_max(h->r); 
     if (max == right->acc && less(right->name, word)) 
      word = right->name; 
     if (max < right->acc){ 
      max = right->acc; 
      word = right->name; 
     } 
     hashtag->acc = max; 
     hashtag->name = word; 
     return hashtag; 
    } 

h ist der Kopf des Baumes und weniger ist

#define less(a,b) (strcmp(a,b) < 0) 

und Link ist

typedef struct node{ 
     Item item; 
     struct node *l; 
     struct node *r; 
    } *link; 

Es hat einen Segmentierungsfehler gibt (core dumped). Zuvor habe ich den gleichen Code ausprobiert, ohne Speicher für Hashtag, links oder rechts, zuzuweisen (gleicher Fehler).

Answer 1

Sie reservieren Speicher für die Objektzeiger und überschreiben dann die Zeiger. Sie haben zwei Möglichkeiten: Sie könnten Artikelwerte verwenden oder Sie könnten Zeiger richtig verwenden:

Für die erste Wahl müssen Sie das * aus dem Item typedef entfernen und alle Verwendungen von Items ändern. Für die zweite Wahl (was in diesem Fall einfacher ist) sollten Sie alle mallocs von search_max entfernen. Dann nutzen:

Item left = search_max(h->l); 
... 

Beachten Sie, dass Sie nicht lokal die zweiten Kriterien überprüfen (lexicographic String Reihenfolge). Stattdessen haben Sie wieder zwei Möglichkeiten: Sammeln Sie alle Einträge mit dem höchsten Acc-Wert in einer anderen Sammlung, und wenn Sie mit dem Baum fertig sind, gehen Sie durch diese Sammlung, um diese einzelne Zeichenfolge zu finden. Zweite Wahl: Informationen über alle Aufrufe von search_max rekursiv übergeben - die Info ist die aktuelle Zeichenfolge und ihr acc-Wert.

Answer 2

Das Ergebnis ist entweder das Element im aktuellen Knoten oder ein Element unter seinem linken oder rechten Teilbaum. Teile und herrsche: (Ich entfernte die typedeffed Zeiger für Klarheit und Vernunft)

HINWEIS: Es sind keine malloc() s erforderlich. Sie untersuchen nur einen vorhandenen -Baum, nichts hinzuzufügen.

---

struct item { 
     char *name; 
     int acc; 
     }; 

struct node { 
     struct item *item; 
     struct node *left, *right; 
     }; 

int items_cmp(struct item *one, struct item *two) 
{ 
if (one->acc < two->acc) return -1; /* two is better */ 
if (one->acc > two->acc) return 1; /* one is better */ 
return strcmp(one->name, two->name); 
} 

struct item * find_max(struct node *np) 
{ 
struct item *ret, *sub; 

if (!np) return NULL; /* stop the recursion ! */ 

ret = np->item; 
sub = find_max(np->left); 
if (sub && items_cmp(ret, sub) > 0) 
     ret = sub; 

sub = find_max(np->right); 
if (sub && items_cmp(ret, sub) > 0) 
     ret = sub; 

return ret; 
}