线索树

#include <iostream>
#include <stdlib.h>

using namespace std;

enum PointerTag {LINK , INDEX};
typedef char Elemtype;
typedef struct node {
    Elemtype data;
    struct node *lchild , *rchild;
    PointerTag lTag , rTag;
} *ThreadTree;

//声明所需要用到的函数
void createTree(ThreadTree *);
void displayBefore(ThreadTree);
void displayBetween(ThreadTree);
void inorderThrTree(ThreadTree * , ThreadTree);
void inorderThread(ThreadTree);
void displayThreadTree(ThreadTree);
//用于线索化的时候，记录前一个结点
ThreadTree  pre;

int main()
{
    ThreadTree tree;
    createTree(&tree);
    cout << "先序显示未线索化的树：" << endl;
    displayBefore(tree);
    cout << endl;
    cout << "中序显示未线索化的树：" << endl;
    displayBetween(tree);

    ThreadTree newTree;
    //线索化树
    inorderThrTree(&newTree , tree);

    cout << endl;
    cout << "显示线索化后的树：" << endl;
    displayThreadTree(newTree);
    return 0;
}

//创建一棵树，当输入为空格的时候，其当前结点为NULL
void createTree(ThreadTree *tCurrTree) {
    char cIn;
    cin.get(cIn);
    (*tCurrTree) = NULL;

    if(cIn == '\0') {
        return;
    }

    if(cIn != ' ') {
        (*tCurrTree) = (ThreadTree)malloc(sizeof(node));
        (*tCurrTree)->data = cIn;
        createTree(&(*tCurrTree)->lchild);
        createTree(&(*tCurrTree)->rchild);
    }
}

//先序遍历树显示，用于证明树创建的正确性
void displayBefore(ThreadTree tCurrTree) {
    if(tCurrTree != NULL) {
        cout << tCurrTree->data << " ";
        displayBefore(tCurrTree->lchild);
        displayBefore(tCurrTree->rchild);
    }
}

//中序遍历树显示，用于证明树创建的正确性
void displayBetween(ThreadTree tCurrTree) {
    if(tCurrTree != NULL) {
        displayBefore(tCurrTree->lchild);
        cout << tCurrTree->data << " ";
        displayBefore(tCurrTree->rchild);
    }
}

//用已有的树创建一个带头结点的线索树
void inorderThrTree(ThreadTree *root ,  ThreadTree tree) {

    //创建线索树头结点
    (*root) = (ThreadTree)malloc(sizeof(node));
    if(!(*root)) {
        exit(0);
    }

    //让头结点的左子树为线索，用于让线索化后最后一个结点的右子树指向它
    (*root)->rTag = LINK;
    (*root)->lTag = INDEX;
    (*root)->lchild = (*root);
    if(!tree) {
        (*root)->rchild = (*root);
    } else {
        (*root)->rchild = tree;
        pre = (*root);
        inorderThread(tree);
        pre->rchild = (*root);
        pre->rTag = INDEX;
        (*root)->lchild = pre;
    }

}

//对一个无头指针的树进行线索化
void inorderThread(ThreadTree tCurrTree) {
    if(tCurrTree != NULL) {
        //线索化当前结点的左子树
        inorderThread(tCurrTree->lchild);

        //线索化当前结点，由于其下一个结点不知道
        //所以它的右孩子指针留给它的下一个结点进行线索化
        if(tCurrTree->lchild == NULL) {
            tCurrTree->lTag = INDEX;
            tCurrTree->lchild = pre;
        }
        if(pre->rchild == NULL) {
            pre->rTag = INDEX;
            pre->rchild = tCurrTree;
        }
        pre = tCurrTree;

        //线索化当前结点的右子树
        inorderThread(tCurrTree->rchild);
    }
}

//显示线索化后的树，由于树是中序线索化，所以显示的结果与中序遍历的结果一样
void displayThreadTree(ThreadTree tree) {
    ThreadTree head = tree->rchild;
    while(head != tree) {

        //移动到第一个结点并打印值，即最左下的结点
        while(head->lTag == LINK) {
            head = head->lchild;
        }
        cout << head->data << "  ";

        //判断其右孩子指针是否是线索，如果是直接下移并输出
        //如果不是，移动到它的右子树，进行新一轮的遍历
        if(head->rTag == INDEX && head->rchild != tree) {
            head = head->rchild;
            cout << head->data << "  ";
        }
        head = head->rchild;
    }
}