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

这是我做到的一种方法：

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 回答