编辑代码

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

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

struct TreeNode {
    E element;
    struct TreeNode *left;
    struct TreeNode *right;
    struct TreeNode *parent;
    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 postOrder(Node root) {
    if (root == NULL) return;
    if (root->leftTag == 0) {
        if (root->left != NULL)root->left->parent = root;
        postOrder(root->left);
    }
    if (root->rightTag == 0) {
        if (root->right != NULL)root->right->parent = root;
        postOrder(root->right);
    }
    // 判断规则 左子树空指针连接上一个节点 右子树空指针连接下一个节点
    if (root->left == NULL) {
        root->left = pre;
        root->leftTag = 1;
    }
    if (pre && pre->right == NULL) {
        pre->right = root;
        pre->rightTag = 1;
    }
    pre = root;
}

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

    // 两种情况
    while (TwoTree) {
        // 有线索化结点则往右
        if (TwoTree && TwoTree->rightTag == 1){
            TwoTree = TwoTree->right;
            printf("%c", TwoTree->element);
        } else {        // 无线索化结点则指向兄弟节点
            if (TwoTree->parent->right)
            TwoTree = TwoTree->parent->right;
            else        //无兄弟节点则指向父节点
                TwoTree = TwoTree->parent;
            printf("%c", TwoTree->element);
        }
    }
}

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;

    postOrder(a);
    f(a);
}