バイナリ検索ツリーを再帰的に移動してノードを追加しようとしています

Question

私はBSTを移動するには再帰的に行うことを理解しています。私はノードを追加しようとしていますが、addTreeNodeにはダブルポインタが必要ですが、シンタックスは混乱していますが、ダブルポインタを追加すると再帰呼び出しでは、「ノード」は構造体または共用体の一部ではないと言います。私はこれらの構造体をどのように管理するのかちょっと混乱しています。

#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

してくださいは、

https://en.wikipedia.org/wiki/Binary_search_treeを読んで、特に挿入セクション

左のすべての方法を動かすよう

その後、バックトラック、すべての道を移動し、右

いや、 2分探索木は既にソートされている。擬似コードで

、あなただけの操作を行います。

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

ツリーの操作は、ノードを変更し、そのノードがルートノードであってもよいし、あなたがようてroot_nodeを使用することはできません木の表現。代わりに、ルートノードへのポインタが使用されます。あなたの関数は、あなたのツリーを作成または変更する必要がある場合

typedef struct treeFrame{ 
    bNode *node; 
}bTree; 

だから、あなたはそのツリーへのポインタを渡すルートノードが変更された場合、変更はする必要があるため、彼らは、ツリーへのポインタを使用する必要があります呼び出し元のスコープに到達します。抽象化のようなものを好きではない

do_something(bTree * tree_ptr) 

しかし、（私のような）一部の人、その代わりに、ツリー構造、またはのtypedefを定義する、彼らは直接作業好む：だからすべてのツリーの機能は、署名を持っている必要がありますroot_nodes。その場合

、シグネチャは型でなければなりません：

do_something(bNode ** root_node) 

は木がroot_nodeにへのポインタであるので、あなただけでてroot_nodeを変更することができるように別の間接を追加していることを覚えておいてください操作が必要とする場合

---

最後にあなたのプロトタイプ：

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

あなたはroot_nodesで動作する、またはツリーあなたは抽象的な場合は、単一のポインタが必要な場合は、二重のポインタを必要とするいずれか、間違っています。

Answer 2

ノードを追加するあなたの機能を使用すると、左または右部分木にノードを追加するために再帰的にそれを使用することはできません署名

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

持っているので：bTreeは、ツリーのルートのみを保持し、サブツリーはbNodeへのポインタです。サブツリー型に関して新しい関数を定義し、addTreeNodeを実装するためにそれを使用します。

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

ここでコードは、代わりにヘルパーに入ります。

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