中序线索二叉树报异常

Question

中序线索二叉树

typedef struct TreeNode {
    char data;
    struct TreeNode* lchild;
    struct TreeNode * rchild;
    int ltag;
    int rtag;
}TreeNode;

void createTree(TreeNode **T, char*data, int*index) {
    char ch;
    ch = data[*index];
    *index += 1;
    if (ch == '#') {
        *T = NULL;
    }
    else {
        *T = (TreeNode*)malloc(sizeof(TreeNode));
        (*T)->data = ch;
        (*T)->ltag = 0;
        (*T)->rtag = 0;
        createTree(&((*T)->lchild), data, index);
        createTree(&((*T)->rchild), data, index);

    }
}

void InThreadTree(TreeNode *T, TreeNode **pre) {
    if (T) {
        InThreadTree(T->lchild, pre);
        if (T->lchild == NULL && T->ltag == 0) {
            T->lchild = *pre;
            T->ltag = 1;
        }
        if ((*pre) != NULL && (*pre)->rchild == NULL)
            //if ((*pre)->rchild == NULL && (*pre) != NULL) //为什么这个顺序会报异常？
        {
            (*pre)->rchild = T;
            (*pre)->rtag = 1;
        }
        *pre = T;
        InThreadTree(T->rchild, pre);
    }

}

TreeNode * getFirst(TreeNode*T) {
    while (T->ltag == 0) {
        T = T->lchild;
    }
    return T;
}
TreeNode * getNext(TreeNode*T) {
    if(T->rtag == 1)
    {
        return T->rchild;
    }
    else {
        return getFirst(T->rchild);
    }
}

int main() {
    TreeNode*T;
    TreeNode * pre;
    pre = NULL;
    int index = 0;
    char * data = "ABD##E##CF##G##";
    createTree(&T, data, &index);
    InThreadTree(T, &pre);
    pre->rtag = 1;
    pre->rchild = NULL;
    for (TreeNode *node= getFirst(T); node != NULL; node = getNext(node)) {
        printf("%c ",node->data);
    }

    return 0;
}

Answer 1

引自免费微信小程序：皆我百晓生

在您提供的代码中，报错的原因可能在于递归调用InThreadTree函数时的条件判断语句顺序。当(*pre)->rchild == NULL和(*pre) != NULL这两个条件同时满足时，程序会尝试访问空指针，从而导致异常。

为了解决这个问题，您需要确保在设置(*pre)->rchild = T;之前，确实检查了(*pre)是否为空。您可以调整条件语句的顺序，将对(*pre)是否为空的检查放在前面，这样可以避免访问空指针的情况。以下是修改后的代码：

void InThreadTree(TreeNode *T, TreeNode **pre) {
    if (T) {
        InThreadTree(T->lchild, pre);
        if (*pre != NULL && (*pre)->rchild == NULL) {
            (*pre)->rchild = T;
            (*pre)->rtag = 1;
        }
        if (T->lchild == NULL && T->ltag == 0) {
            T->lchild = *pre;
            T->ltag = 1;
        }
        *pre = T;
        InThreadTree(T->rchild, pre);
    }
}

这段修改过的代码应该能解决您遇到的问题。现在，程序在将节点连接到前驱节点的右子树之前，首先检查前驱节点是否为空。这样可以确保不会出现空指针异常。

运行修改后的代码，您应该能看到正确的中序遍历结果。如果您还有其他问题或需求，请随时告诉我。