Löschen Sie den linken Teilbaumknoten (binäre Suchbaum) in C

Question

Ich arbeite an einer C-binären Suchbaumbibliothek und ich versuche, eine Funktion zu schreiben, die den linken Knoten des Baumunterbaums löschen wird. Hier ist die Struktur von meinem Baum:

struct Node { 
    int value; 
    struct Node *left; 
    struct Node *right; 
}; 

typedef struct Node TNode; 
typedef struct Node *binary_tree; 

Der Baum wie folgt erstellt:

binary_tree NewBinaryTree(int value_root) { 
    binary_tree newRoot = malloc(sizeof(TNode)); 
    if (newRoot) { 
     newRoot->value = value_root; 
     newRoot->left = NULL; 
     newRoot->right = NULL; 
    } 
    return newRoot; 
} 

Hinzufügen Element, um es:

void Insert(binary_tree *tree, int val) { 
    if (*tree == NULL) { 
     *tree = (binary_tree)malloc(sizeof(TNode)); 
     (*tree)->value = val; 
     (*tree)->left = NULL; 
     (*tree)->right = NULL; 
    } else { 
     if (val < (*tree)->value) { 
      Insert(&(*tree)->left, val); 
     } else { 
      Insert(&(*tree)->right, val); 
     } 
    } 
} 

Die delleftsubtreenode ich getan habe:

void delleftsubtree(binary_tree *tree){ 

    if((*tree)->value!=NULL) 

    { 
      free(&(*tree)->left); 
      delleftsubtree(&(*tree)->left); 
    } 
    else 
    { 
     printf("end"); 
    } 
} 

Diese Methode kompilieren jedoch w Wenn ich versuche, es das Programm nur Crash nennen. Ich verstehe nicht, warum oder wie sonst diese Funktion zu tun.

danke!

Answer 1

Wie Olaf in seinem Kommentar sagte, haben Sie mehrere Probleme; Aufrufen von "free()" mit einem Zeiger, der dann versucht, es zu dereferenzieren, und Verwendung der doppelten Indirektion.

Sofern Sie nicht beabsichtigen, den Wert des Zeigers zu ändern, ist dies zusätzliche Arbeit, die Sie nicht tun möchten. All diese "(*tree)->member" Ausdrücke werden nicht benötigt, wenn Sie den üblichen Konventionen folgen, und ich bin nicht überzeugt, dass Sie verstehen, was "& (* tree) -> left" tut.

Ich sage nicht, dass Sie nie einen Zeiger auf einen Zeiger verwenden sollten, ich habe es selbst getan, aber Sie sollten es nur tun, wenn es einen Grund gibt, den Wert des referenzierten Zeigers zu ändern, oder mit ein flüchtiger Zeiger, der von einem externen Akteur verändert werden könnte; Dies ist unwahrscheinlich und ziemlich selten außerhalb von Garbage Collected und Compacted Pools (z. B. Strings in einigen BASIC-Interpretern) und dergleichen.

Beachten Sie, dass der "linke" Teilbaum eines Knotens im Baum selbst ein Binärbaum ist; Es hat sowohl linke als auch rechte Knoten. Sie müssen eine Funktion schreiben, die einen Teilbaum an und unter einem bestimmten Knoten löscht. Sobald das verstanden wird, ist die Entfernung des linken Unterbaum unterhalb eines Knotens so einfach wie:

void delSubtree(NodeT* subRoot) 
{ 
    if (subRoot != NULL) 
    { 
     delSubtree(subRoot->left); 
     delSubtree(subRoot->right); 
     free(subRoot); 
    } 
} 

void delLeftSubtree(NodeT* root) 
{ 
    if (root != NULL) 
    { 
     delSubtree(root->left); 
     root->left = NULL; 
    } 
} 

Wenn diese Hausaufgaben ist, sollten Sie sich diese Probleme werden lösen, und ich mache Ihnen keinen Gefallen zu geben Sie Codebeispiele . Zu verstehen, wie man Zeiger und verknüpfte Datenstrukturen (Listen, Bäume und andere Graphen) verwendet, ist wesentlich, um ein vollendeter C-Programmierer zu werden.