请问这个线索二叉树哪里有问题呢

Question

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
typedef char BTType;

typedef struct BTree {
    BTType data;
    struct BTree* lchild, * rchild;
    int Ltag;
    int Rtag;
}BTNode;


void CreatBTree(BTNode** T) {

    char ch;
    scanf_s("%c", &ch, 1);
    if (ch == '#') {
        *T = NULL;
    }
    else {
        *T = (BTNode*)malloc(sizeof(BTNode));
        if (*T == NULL) {
            return;
        }
        else {
            (*T)->data = ch;
            (*T)->Ltag = 0;
            (*T)->Rtag = 0;
            CreatBTree(&(*T)->lchild);
            CreatBTree(&(*T)->rchild);
        }
    }
    return;
}
  

void inthreading(BTNode* T, BTNode** pre) {
    if (T){
        inthreading(T->lchild, pre);
    if (T->lchild == NULL) {
        T->Ltag = 1;
        T->lchild = *pre;

    }

    if ((*pre)->rchild == NULL && (*pre) != NULL) {
        (*pre)->Rtag = 1;
        (*pre)->rchild = T;
    }
    *pre = T;
    inthreading(T->rchild, pre);
}
}

int main() {
    BTNode* T;
    BTNode* pre = NULL;
    CreatBTree(&T);
    inthreading(T, &pre);
    pre->Rtag = 1;
    pre->rchild = NULL;
    return 0;
}

Answer 1

这段代码存在两个问题：

1. 函数 inthreading 中，对于线索化的前驱节点 pre 的判断不完整。当 T->lchild 为 NULL 时，需要将 T 的标志位设为线索，并将 T 的左（前）继节点指针指向 pre。

2. 在主函数 main 中，没有调用函数 inthreading 进行二叉树的中序线索化操作，这会导致后面对中序遍历结果的输出不准确。

以下是修改后的代码：

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

typedef char BTType;
typedef struct BTree {
    BTType data;
    struct BTree* lchild, * rchild;
    int Ltag;
    int Rtag;
}BTNode;

void CreatBTree(BTNode** T) {
    char ch;
    scanf_s("%c", &ch, 1);
    if (ch == '#') {
        *T = NULL;
    }
    else {
        *T = (BTNode*)malloc(sizeof(BTNode));
        if (*T == NULL) {
            return;
        }
        else {
            (*T)->data = ch;
            (*T)->Ltag = 0;
            (*T)->Rtag = 0;
            CreatBTree(&(*T)->lchild);
            CreatBTree(&(*T)->rchild);
        }
    }
    return;
}

void inthreading(BTNode* T, BTNode** pre) {
    if (T) {
        inthreading(T->lchild, pre);
        if (T->lchild == NULL) {
            T->Ltag = 1;
            T->lchild = *pre;
        }

        if (*pre != NULL && (*pre)->rchild == NULL) {
            (*pre)->Rtag = 1;
            (*pre)->rchild = T;
        }

        *pre = T;
        inthreading(T->rchild, pre);
    }
}

int main() {
    BTNode* T;
    CreatBTree(&T);

    // 初始化前驱节点，保存上一次遍历访问的节点
    BTNode* pre = NULL;

    // 进行中序线索化操作
    inthreading(T, &pre);

    // 输出结果
    printf("中序遍历结果：\n");
    BTNode* p = T;
    while (p) {
        while (p->Ltag == 0) {
            p = p->lchild;
        }
        printf("%c ", p->data);
        while (p->Rtag == 1 && p->rchild != NULL) {
            p = p->rchild;
            printf("%c ", p->data);
        }
        p = p->rchild;
    }

    return 0;
}