编辑代码

#include <stdio.h>
#include "windows.h"

//线索化二叉树是一种对二叉树的空指针域进行利用的方法，目的是为了加快查找二叉树中某节点的前驱和后继的速度¹²。
// 线索化二叉树可以按照不同的遍历顺序进行线索化，如先序，中序，后序等³。
// 线索化二叉树的节点结构中除了数据域和左右孩子指针外，还有两个标识域，
// 用来区分左右指针是指向孩子节点还是指向前驱或后继节点⁴。
typedef char E;

struct TreeNode {
    E element;
    struct TreeNode *left;
    struct TreeNode *right;
    int leftTag, rightTag;   //标志位 如果值为1则表示该节点进行了线索化
};

typedef struct TreeNode *Node;

// 创建节点
Node createNode(E element) {
    Node node = malloc(sizeof(struct TreeNode));
    if (node == NULL) return NULL;
    node->left = node->right = NULL;
    node->leftTag = node->rightTag = 0;
    node->element = element;
    return node;
}

Node pre = NULL; // 临时存储上一个节点

//前序线索化方法
void inOrder(Node root) {
    if (root == NULL) return;
    if (root->leftTag == 0)
        inOrder(root->left);
    // 判断规则 左子树空指针连接上一个节点 右子树空指针连接下一个节点
    if (root->left == NULL) {
        root->left = pre;
        root->leftTag = 1;
    }
    if (pre && pre->right == NULL) {
        pre->right = root;
        pre->rightTag = 1;
    }
    pre = root;
    if (root->rightTag == 0)
        inOrder(root->right);
}

// 中序遍历
void f(Node TwoTree) {
    while (TwoTree) {
        // 走到最左边
        while (TwoTree && TwoTree->leftTag == 0)
            TwoTree = TwoTree->left;
        // 打印
        printf("%c", TwoTree->element);

        // 打印中间
        while (TwoTree && TwoTree->rightTag == 1) {
            TwoTree = TwoTree->right;
            printf("%c", TwoTree->element);
        }
        // 走到右边
        TwoTree = TwoTree->right;
    }
}

int main() {
    Node a = createNode('A');
    Node b = createNode('B');
    Node c = createNode('C');
    Node d = createNode('D');
    Node e = createNode('E');

    a->left = b;
    b->left = d;
    a->right = c;
    b->right = e;

    inOrder(a);
    f(a);
}