1

二分探索木の挿入部分で行き詰まっています。ネストされた構造体と混同されます。このプログラムの基本的な考え方は、(明らかに) 値によって格納される名前と double 値を保持できる bst を作成することです。

例：保管したい

ジェーン 3.14

ジョン 3.233

ルーク 6.4

マイク 1.4

したがって、bstは次のようになります

                 3.14
                 /   \
              1.4    3.233
                       \
                        6.4

ただし、コードの insertHelper 再帰部分に問題があります。ハッシュ テーブルはコードのボーナス部分であり、後で実装してみます。ご協力ありがとうございました！

typedef struct name_val // holds name and value
{
    char *name;
    double value;
}NAME_VAL;

typedef struct node //binary search tree
{
    NAME_VAL *nV;
    struct node *left;
    struct node *right;
}NODE;

struct tmap_struct  //handle for bst and hashtable
{
    int nL; //nodes on left
    int nR; //nodes on right
    NODE *root;
    NODE **table;
};


int tmap_insert(TMAP_PTR hashTree, char * name, double val)
{
    if(hashTree->root == NULL)
    {
        NODE *bst = (NODE *)malloc(sizeof(NODE));
        NAME_VAL *root = (NAME_VAL *)malloc(sizeof(NAME_VAL));
        bst->nV = root;
        bst->nV->value = val;
        strcpy(bst->nV->name, name);
        hashTree->root = bst;
        hashTree->nL = 0;
        hashTree->nR = 0;
    }

    else 
        insertHelper(hashTree->root, val, name);

}

void insertHelper(TMAP_PTR hashTree, int val, char * name)
{
    if(val < hashTree->root->nV->value)
    {
        if(hashTree->root->left == NULL)
        {
            hashTree->root->left = (NODE *)malloc(sizeof(NODE));
            hashTree->root->left->nV = (NAME_VAL *) malloc(sizeof(NAME_VAL));
            strcpy(hashTree->root->left->nV->name, name);
            hashTree->root->nV->value = val;
            (hashTree->nL)++;
        }

        else
            insertHelper(hashTree->root->left, val, name);
    }

    else
    {
        if(hashTree->root->right == NULL)
        {
            hashTree->root->right = (NODE *)malloc(sizeof(NODE));
            hashTree->root->right->nV = (NAME_VAL *)malloc(sizeof(NAME_VAL));
            strcpy(hashTree->root->left->nV->name,name);
            hashTree->root->nV->value = val;
            (hashTree->nR)++;
        }

        else
            insertHelper(hashTree->root->right, val, name);
    }
}
4

2 に答える 2

1

私のものを適応させる必要があります（不要なテンプレートとクラス以外はほぼ標準のCです）が、同様のアルゴリズムです：（私は自分の目的のためにソースを調べていないと思います。）

template<typename T>
class BST {
    protected:
        typedef struct node_t {
            struct node_t * dir[2];
            T data; 
        } node;

        node * root;

        void insert_node(node * active_node, T data){ //call with node *root;
            int next = data < active_node->data ? 0 : 1;
            if(active_node->dir[next] == NULL){
                active_node->dir[next] = new node;
                active_node->dir[next]->dir[0] = NULL;
                active_node->dir[next]->dir[1] = NULL;
                active_node->data = data;
            } else
                insert_node(active_node->dir[next], data);
        }

    public:
        BST() : root(new node){root->dir[0] = NULL; root->dir[1] = NULL; root->data = 0;}
       ~BST(){}
}
于 2013-04-30T04:00:56.013 に答える
1

これがコンパイルされるとは思えません。それはあなたが抱えている問題ですか？

私が見る限りinsertHelper、最初のパラメーターに間違った型を宣言しています。NODE*値ではなく、値を取る必要がありTMAP_PTRます。これは、常にツリー外のノードで呼び出すためです。

したがって、関数の最初の部分は次のようになります。

void insertHelper(NODE *node, int val, char * name)
{
    if(val < node->nV->value)
    {
        if(node->left == NULL)
        {
            node->left = (NODE *)malloc(sizeof(NODE));
            node->left->nV = (NAME_VAL *) malloc(sizeof(NAME_VAL));
            strcpy(node->left->nV->name, name);
            node->left->nV->value = val;
        }

        else
            insertHelper(node->left, val, name);
    }

    //.....

次の行を削除したことに注意してください。

(hashTree->nR)++;

ノードレベルで追跡しない限り、この情報を追跡することはほとんど意味がありません。

ただし、必要に応じてinsertHelper、正または負の値を再帰的に返して、挿入した側を示すことができます。しかし、それは意味がありません。右にあるのは何？ツリーの左半分にあったノードの右側に挿入した可能性があります。

この情報を各ノードに保存すると、 から戻ったときに上記のノードを再帰的に更新できますinsertHelper。多分それはあなたがやろうとしていたことです。バランス ツリーの実装も同様のことを行います。AVL ツリーはノードにツリーの最大深度を格納し、それを使用してリバランスのためにブランチ ローテーションを行います。

于 2013-04-30T03:03:40.363 に答える