0

次のような main.c ファイルがあります。

it = bet_create_iterator(bstree);

while ((n = bst_iter_next(it))) {
    printf("value: %d", bst_getvalue(n));
}

上記から、その使用方法を理解していただければ幸いです。しかし、ここに私の問題があります。その機能、 

bst_iter_next(it)

ツリー内のノードへのポインターを返します。

BST を再帰的にトラバースするのは非常に簡単ですが、この方法で毎回ノードを返すのは難しいことがわかりました。

誰かが男を助けて、それを行う方法を私に説明できれば、それは大歓迎です.

乾杯、

アンディ。

4

2 に答える 2

0

ノードダブルポインターitであり、呼び出すたびbst_iter_next(it)に次のノードを指すようにします。ポスト オーダーでツリーをトラバースしていて、を呼び出しているとしましょうit = bet_create_iterator(bstree);。これitで、ルート ノードがポイントされました。次に を呼び出しますbst_iter_next(it);。それは次のようなことをします：

bst_iter_next(node **it) {
    if (*it has children) {
       *it = *it->left;
       return *it
    }
    else if (*it->parent == NULL)
        *it = NULL or whatever;
        return NULL;
    else {
       node *n = *it;
       while(1) {
          if(n->parent == NULL) {
             *it = NULL or whatever;
             return NULL;
          }
          if(n->parent->left == n && n->parent->right!= NULL) {
              *it = n->parent->right;
              return *it;
          }
          else
              n = n->parent;
       }
    }
}

とにかく、それは私の心の中ではうまくいくようですが、私の論理には欠陥があるかもしれません.

于 2013-10-20T23:08:49.130 に答える
0

これが私がやった1つの方法です：

struct node{
    int value;
    struct node *left, *right, *parent;
    int visited;
};

struct node* iter_next(struct node* node){
    struct node* rightResult = NULL;

    if(node==NULL)
        return NULL;

    while(node->left && !(node->left->visited))
        node = node->left;

    if(!(node->visited))
        return node;

    //move right
    rightResult = iter_next(node->right);

    if(rightResult)
        return rightResult;

    while(node && node->visited)
        node = node->parent;

    return node;
}

秘訣は、親リンクと各ノードの訪問済みフラグの両方を持つことです。また、 iter_next() は、ツリー構造の状態を (もちろん) 変更せずに呼び出す必要がありますが、「訪問済み」フラグの値は変更されません。

iter_next() を呼び出して、このツリーのたびに値を出力するテスター関数を次に示します。

                  27
               /      \
              20      62
             /  \    /  \
            15  25  40  71
             \  /
             16 21

int main(){

    //right root subtree
    struct node node40 = {40, NULL, NULL, NULL, 0};
    struct node node71 = {71, NULL, NULL, NULL, 0};
    struct node node62 = {62, &node40, &node71, NULL, 0};

    //left root subtree
    struct node node16 = {16, NULL, NULL, NULL, 0};
    struct node node21 = {21, NULL, NULL, NULL, 0};
    struct node node15 = {15, NULL, &node16, NULL, 0};
    struct node node25 = {25, &node21, NULL, NULL, 0};
    struct node node20 = {20, &node15, &node25, NULL, 0};

    //root
    struct node node27 = {27, &node20, &node62, NULL, 0};

    //set parents
    node16.parent = &node15;
    node21.parent = &node25;
    node15.parent = &node20;
    node25.parent = &node20;
    node20.parent = &node27;
    node40.parent = &node62;
    node71.parent = &node62;
    node62.parent = &node27;

    struct node *iter_node = &node27;

    while((iter_node = iter_next(iter_node)) != NULL){
        printf("%d ", iter_node->value);
        iter_node->visited = 1;
    }
    printf("\n");
    return 1;
}

ソートされた順序で値を出力します：

15 16 20 21 25 27 40 62 71
于 2016-02-13T06:49:16.357 に答える