基数树实现中的无限循环问题

Question

我的基数树实现有问题。这个想法是我创建第一个节点，然后输入一些二进制数。二进制数决定是创建左节点 (0) 还是右节点 (1)。到达二进制数的末尾后，我将节点设置为 "active"。

然后我在树中搜索找到一个活动节点，并通过检查我必须朝哪个方向到达活动节点再次输出原始二进制数。

完整代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef int bool;
enum { false, true };

typedef struct radixNode {
    bool active;
    struct radixNode * pnt;
    struct radixNode * l;
    struct radixNode * r;
} node;

void insert(node *root, char * B) {

    printf("String: %s\n", B);
    printf("1st: %c", B[0]);
    printf("\n\n", B);

    // digit is zero so we go left
    if (B[0] == '0') {

        printf("till here if");

        // left child doesn't exist, create it
        if (root->l == NULL) {

            root->l = malloc(sizeof(node));

            /* if the next index in the string does NOT contain a 1 or 0,
            the current index is the last index and the node is activated */
            if (B[1] == 1 || B[1] == 0)
                root->l->active = false;
            else
                root->l->active = true;

            root->l->pnt = root;
            root->l->l = NULL;
            root->l->r = NULL;
            insert(root->l,B++); // B++ removes the first digit of the string
        }

        // left child exists, traverse
        else {
            insert(root->l,B++);
        }
    }

    // digit is one, go right
    else if (B[0] == '1') {
        printf("first was 1\n");

        // right child doesn't exist, create it
        if (root->r == NULL) {

            printf("if triggered\n");

            root->r = malloc(sizeof(node));

            /* if the next index in the string does NOT contain a 1 or 0,
            the current index is the last index and the node is activated */
            if (B[1] == 1 || B[1] == 0)
                root->r->active = false;
            else
                root->r->active = true;

            root->r->pnt = root;
            root->r->l = NULL;
            root->r->r = NULL;
            insert(root->r,B++);
        }

        // left child exists, traverse
        else {
            printf("else triggered\n");
            insert(root->r,B++);
        }
    }
}

node * printTreeMin(node *root) {

    char C[10];

    /* goes left until it can't, appends 0 to string
    till it can't. if node is active, print the string */
    while (root->l != NULL) {

        C[strlen(C)] = '0';

        if (root->active == true)
            printf("%s\n",C);

        root = root->l;
    }

    return root;
}

// prints the next smallest binary number in the tree, returns the node it printed
node * printNextSmallest(node * root) {

    char C[10];

    // if right child exists, go there and find lowest node (after if same deal as printTreeMin() )
    if (root->r != NULL) {

        C[strlen(C)] = '1';
        if (root->active == true)
            printf("%s\n",C);

        root = root->r;

        while (root->l != NULL) {

            C[strlen(C)] = '0';
            if (root->active == true)
                printf("%s\n",C);

            root = root->l;
        }

        return root;
    }

    node * temp = root->pnt;

    while (temp != NULL && root == temp->r) {

        root = temp;
        temp = temp->pnt;
    }

    return temp;
}

void printRadixTree(node *root) {

    root = printTreeMin(root);

    while (printNextSmallest(root) != NULL)
        root = printNextSmallest(root);
}

void test() {

    node * tree = malloc(sizeof(node));
    tree->l = NULL;
    tree->r = NULL;

    // a)
    insert(tree,"101000");
    insert(tree,"10100");
    insert(tree,"10110");
    insert(tree,"101");
    insert(tree,"1111");

    // b)
    printRadixTree(tree);

}

int main() {
    test();
}

这是输出：

if triggered
String: 101000
1st: 1

first was 1
if triggered
String: 101000
1st: 1

first was 1
if triggered
String: 101000
1st: 1

（并且无限继续）

很明显，我在 insert() 函数的递归中遇到了问题，但考虑到我在进行递归时删除了二进制数字字符串的第一个字符，我不明白它如何可以无限地运行 .

Answer 1

无限递归的原因是您选择了自增运算符。您需要前缀，而不是后缀形式。

insert(..., B++)

增加指针（去除第一个字符）在调用插入之后。

调用应该是

insert (..., ++B)

你的 active 标志也有问题，这是你的罪魁祸首

if (B[1] == 1 || B[1] == 0)

我想你的意思是

if (B[1] == '1' || B[1] == '0')

第一种形式是检查 二进制 零或一，而不是 ASCII 字符。

这样做的结果是您的 active 标志对于大多数节点可能设置不正确。我希望这会在遍历树时引起问题。事实上，当您查看字符串中的最后一个 '0' 或 '1' 时，active 只会设置为 false（因为 B[1]是终止 '[=23=]').

此外，对于递归例程，将基本情况明确化而不是隐含化总是一个好主意。因此，insert 中的第一个代码块可能应该是

if (B[0] != '1' && B[0] != `0`)
    return;

然后你可以用简单的 else

替换 else if

if (B[0] == '0')
{
    // ... go left
}
else
{
    // ... go right
}

基数树实现中的无限循环问题

Issue with infinite loop in radix tree implementation

c

string

binary-tree

infinite-loop

radix-tree