Bir düğüm eklemek için ikili arama ağacında yinelemeli olarak hareket etmeye çalışmak

Question

Bir BST'yi hareket ettirmek için bunu yinelemeli olarak yapacağınızı anlıyorum. Tüm yolu sola, sonra geri yoluna devam et, sonra yolun sağa doğru hareket et. Bir düğüm eklemeye çalışıyorum ama sözdizimi, addTreeNode'un bir çift işaretçi beklediğimde kafamı karıştırıyor, ama bende bir çift işaretçi eklediğimde özyinelemeli sonra "düğüm" bir yapı veya birliğin parçası olmadığını söyler. Bu yapıları nasıl yöneteceğim konusunda biraz kafam karıştı. düğüm eklemek için işlev imzası yana

#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

Lütfen

https://en.wikipedia.org/wiki/Binary_search_tree okumak özellikle takın bölüm

sol tüm yol hareketli gibi

sonra tekrar iz sonra taşımaktır sağ

Hayır, ikili arama ağaçları zaten sıralanmıştır. pseudocode

, sadece yapın:

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);

Ağaç işlemleri düğümleri değiştirmek ve bir gibi bir root_node kullanamaz böylece düğüm, kök düğüm olabilir ağacın temsili. Bunun yerine, kök düğüme bir işaretçi kullanılır. senin fonksiyonları, kartınızı bunları şu ağaca bir işaretçi oluşturmak veya ağaç değiştirmek gerekiyorsa

typedef struct treeFrame{ 
    bNode *node; 
}bTree; 

Yani, onlar kök düğüm değişirse, değişim gerektiğinden, ağaca bir işaretçi ile çalışması gereken arayan kapsamına ulaşmak. soyutlama bu tür sevmiyorum

do_something(bTree * tree_ptr) 

Ama (benim gibi) bazı insanlar, bunun yerine bir ağaç yapısı ya da bir typedef tanımlama, bunlar doğrudan çalışmayı tercih: Yani bütün ağaç fonksiyonları imzası bulunmalıdır root_nodes.

Bu durumda

, imzalar tipte olmalıdır: Eğer sadece başka indirection içinde root_node değiştirmeye muktedir ekliyoruz böylece

do_something(bNode ** root_node) 

, bir ağaç, bir root_node bir işaretçi olduğunu unutmayın Durumda işlem gerektirir.Nihayet

---

sizin prototipler:

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

Eğer root_nodes ile çalışmak eğer ya bir çift işaretçi gerek yanlış mı yoksa soyut eğer tek işaretçi ağaç gerekir.

Answer 2

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

sol veya sağ alt ağaç düğüm eklemek için yinelemeli bunu kullanamazsınız: bTree ağacın sadece kökünü tutan, subtrees bNode için işaretçilerdir. Alt ağaç türü açısından yeni bir işlev tanımlayın ve addTreeNode'u uygulamak için kullanın.

/* 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); 
} 

Şimdi sahip olduğunuz kod, bunun yerine yardımcıya gider.

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; 
    ... 
}