数据结构——线索树

核心思路就是要先将空指针转为线索 也就是多出来的n+1个指针，然后再将这些指针连成一个链表，遍历就可以达到O(n）的速度打出

以下代码为中序遍历 前序和后续随缘更新

#include <iostream>
#include <stdlib.h>
using namespace std;
typedef struct Node
{
    char data;
    struct Node *l, *r;
    int Ltag, Rtag;
} *TR, TN;
TR createNode(char data)
{
    TR pnew = (TR)malloc(sizeof(TN));
    pnew->data = data;
    pnew->l = pnew->r = NULL;
    pnew->Ltag = pnew->Rtag = 0;
    return pnew;
}
TR pre = NULL;
void createTr(TR *root)
{
    char ch;
    cin >> ch;
    if (ch == '#')
    {
        *root = NULL;
    }
    else
    {
        *root = createNode(ch);
        createTr(&(*root)->l);
        createTr(&(*root)->r);
    }
}
void Pre(TR root)
{
    cout << root->data << " ";
    if (root->l != NULL)
        Pre(root->l);
    if (root->r != NULL)
        Pre(root->r);
}
void Thread_mid(TR *root)
{
    if (*root == NULL)
        return;
    Thread_mid(&(*root)->l);
    if ((*root)->l == NULL)
    {
        (*root)->Ltag = 1;
        (*root)->l = pre;
    }
    if (pre != NULL && pre->r == NULL)
    {
        pre->Rtag = 1;
        pre->r = *root;
    }
    pre = *root;
    Thread_mid(&(*root)->r);
}
TR findnext(TR root)
{
    if (root->Rtag == 1)
        return root->r;
    else
    {
        root = root->r;
        while (root->Ltag == 0)
            root = root->l;
        return root;
    }
}
void midorder(TR root)
{
    TR p = root;
    while (p->l != NULL)
        p = p->l;
    cout << p->data << " ";
    while (p->r != NULL)
    {
        p = findnext(p);
        cout << p->data << " ";
    }
}
int main()
{
    TR root;
    createTr(&root);
    // Pre(root);
    Thread_mid(&root);
    midorder(root);
}