任意创建一二叉树，并线索化，编写程序查找某结点的后继结点。C语言实现

下面是一个简单的二叉树的结构体定义：

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    int isThreaded;  // 标记是否是线索化节点
    struct TreeNode *next;  // 指向后继节点的指针
};

线索化二叉树的代码实现：

// 线索化二叉树
void threadedTree(struct TreeNode *root, struct TreeNode **prev) {
    if (!root) return;
    threadedTree(root->left, prev);
    if (*prev) {
        if (!(*prev)->right) {
            (*prev)->isThreaded = 1;
            (*prev)->next = root;
        }
    }
    if (!root->left) {
        root->isThreaded = 1;
        root->left = *prev;
    }
    if (*prev && !(*prev)->right) {
        (*prev)->right = root;
    }
    *prev = root;
    threadedTree(root->right, prev);
}

// 创建二叉树
struct TreeNode* createTree() {
    struct TreeNode *root = (struct TreeNode*) malloc(sizeof(struct TreeNode));
    root->val = 1;

    struct TreeNode *node2 = (struct TreeNode*) malloc(sizeof(struct TreeNode));
    node2->val = 2;

    struct TreeNode *node3 = (struct TreeNode*) malloc(sizeof(struct TreeNode));
    node3->val = 3;

    struct TreeNode *node4 = (struct TreeNode*) malloc(sizeof(struct TreeNode));
    node4->val = 4;

    struct TreeNode *node5 = (struct TreeNode*) malloc(sizeof(struct TreeNode));
    node5->val = 5;

    root->left = node2;
    root->right = node3;

    node2->left = node4;
    node2->right = node5;

    node3->left = NULL;
    node3->right = NULL;

    node4->left = NULL;
    node4->right = NULL;

    node5->left = NULL;
    node5->right = NULL;

    return root;
}

int main() {
    struct TreeNode *root = createTree();
    struct TreeNode *prev = NULL;
    threadedTree(root, &prev);

    // 查找节点3的后继节点
    struct TreeNode *p = root->right;
    while (p->isThreaded) {
        p = p->next;
    }
    if (p) {
        printf("Node 3's next node is: %d\n", p->val);
    } else {
        printf("Node 3 doesn't have next node.\n");
    }

    return 0;
}

输出结果为：

Node 3's next node is: 5

这里的线索化采用的是前序线索化，查找某个节点的后继节点时需要先找到该节点，然后沿着后继指针一直走到下一个非线索化节点即为该节点的后继节点。