Ich versuche, rekursiv durch die binäre Suchbaumstruktur zu gehen, um einen Knoten hinzuzufügen

Question

Ich verstehe, dass Sie rekursiv tun würden, um sich durch eine BST zu bewegen. Bewegen Sie den ganzen Weg nach links, dann zurück und dann nach rechts. Ich versuche, einen Knoten hinzuzufügen, aber die Syntax verwirrte mich, da ich erhalte, dass addTreeNode einen doppelten Zeiger erwartet, aber wenn ich einen doppelten Zeiger in den hinzufüge rekursiver Aufruf es sagt dann "Knoten" ist nicht Teil einer Struktur oder Union. Ich bin nur ein wenig verwirrt, wie man diese Strukturen verwaltet.

#include <stdio.h> 
#include <stdlib.h> 
#define ADD_LENGTH 30 

typedef struct treeType{ 
    int listingId, price, propertySize; 
    int numOfBeds, yearBuilt; 
    double numOfBaths; 
    char agent[20]; 
    char address[ADD_LENGTH]; 
    struct treeType *left; 
    struct treeType *right; 

}bNode; 

typedef struct treeFrame{ 
    bNode *node; 

}bTree; 

void init(bTree **tree); 
void addTreeNode(bTree **tree, bNode *temp); 



int main(void) 
{ 
    bTree *tree; 
    int numOfProperties; 
    int i; 

    init(&tree); 
    FILE *fp; 
    fp = fopen("library.txt","r"); 
    if(fp == NULL){ 
     printf("fopen failed\n"); 
    } 
    fscanf(fp, "%d", &numOfProperties); 
    printf("%d\n", numOfProperties); 
    bNode temp; 
    // for(i = 0; i < numOfProperties; i++){ 
    fscanf(fp,"%d %s %d %d %d %lf %d %[^\n]s", &temp.listingId, temp.agent,&temp.price,&temp.propertySize,&temp.numOfBeds, 
      &temp.numOfBaths,&temp.yearBuilt,temp.address); 
    addTreeNode(&tree, &temp); 
    //} 


    fclose(fp); 

    return 0; 
} 

void init(bTree **tree){ 
    *tree = malloc(sizeof(bTree)); 
    (*tree)->node= NULL; 


} 

void addTreeNode(bTree **tree,bNode *temp){ 
    if((*tree)->node == NULL){ 
     (*tree)->node = temp; 
     (*tree)->node->left = NULL; 
     (*tree)->node->right = NULL; 
    } 
    else if(temp->listingId < (*tree)->node->listingId){ 
     addTreeNode((*tree)->node->left,temp); 
    } 
    /* printf("%d %s %d %d %d %.1lf %d %s\n", (*tree)->node->listingId, (*tree)->node->agent, (*tree)->node->propertySize,(*tree)->node->price, (*tree)->node->numOfBeds, 
      (*tree)->node->numOfBaths, (*tree)->node->yearBuilt, (*tree)->node->address);*/ 
} 

Answer 1

Bitte lesen https://en.wikipedia.org/wiki/Binary_search_tree

besonders die Insert Abschnitt

Wie dann zurück Spur all die linke Art und Weise bewegt dann bewegen den ganzen Weg rechts

Nö, binäre Suchbäume sind bereits sortiert.

In Pseudo-Code, tun Sie gerade:

node search(value,node) 

    if node_value == search_value then return node 
    else if current_node_vale < search_value return search(left) 
    else return search(right) 

---

void addTreeNode(bTree **tree,bNode *temp);

Baum Operationen Knoten ändern, und dieser Knoten kann der Wurzelknoten, so dass Sie keine root_node als verwenden können Darstellung des Baumes. Stattdessen wird ein Zeiger auf einen Wurzelknoten verwendet.

typedef struct treeFrame{ 
    bNode *node; 
}bTree; 

Also, wenn Ihre Funktionen erstellen müssen oder ändern Sie Ihren Baum, Ihren Pass sie einen Zeiger auf diesen Baum, müssen sie mit einem Zeiger auf den Baum arbeiten, denn wenn der Wurzelknoten ändert, muss die Änderung den Anruferbereich erreichen. So alle Baum Funktionen sollten die Signatur haben:

do_something(bTree * tree_ptr) 

Aber einige Leute, (wie ich) nicht mag diese Art von Abstraktion, so dass anstelle einer Baumstruktur zu definieren, oder eine typedef, sie arbeiten lieber direkt mit root_nodes.

In diesem Fall sollten die Signaturen von der Art sein:

do_something(bNode ** root_node) 

Denken Sie daran, dass ein Baum ein Zeiger auf eine root_node ist, so dass Sie nur ein weiteres indirection Hinzufügen der root_node in der Lage sein zu ändern, in Falls die Operation es erfordert.

---

Schließlich Ihre Prototypen:

void init(bTree **tree); 
void addTreeNode(bTree **tree, bNode *temp); 

falsch sind, entweder ein Doppelzeiger benötigen, wenn Sie mit root_nodes arbeiten, oder Sie benötigen einen einzigen Zeiger, wenn Sie abstrakte der Baum.

Answer 2

Da Ihre Funktion Knoten hinzuzufügen, um die Signatur

void addTreeNode(bTree **tree,bNode *temp); 

Sie können es nicht rekursiv Knoten verwenden, um den linken oder rechten Unterbaum hinzuzufügen: bTree hält nur die Wurzel des Baumes, die Teilbäume sind Zeiger auf bNode. Definieren Sie eine neue Funktion in Bezug auf den Teilbaumtyp und verwenden Sie diese, um addTreeNode zu implementieren.

/* adds the new node to the tree - returns root of modified tree */ 
bNode* addTreeNodeHelper(bNode *root, bNode *temp); 

void addTreeNode(bTree **tree,bNode *temp) { 
    (*tree)->node = addTreeNodeHelper((*tree)->node, temp); 
} 

Der Code, den Sie jetzt haben, geht stattdessen in den Helfer.

void addTreeNodeHelper(bNode *root, bNode *temp){ 
    if (!root) { 
     temp->left = temp->right = NULL; 
     return temp; 
    } 
    else if (temp->listingId < root->listingId) { 
     root->left = addTreeNodeHelper(root->left, temp); 
     return root; 
    ... 
}