线索树

编程技术  /  houtizong 发布于 3年前   69

#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;}//创建一棵树，当输入为空格的时候，其当前结点为NULLvoid 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;    }}