线索二叉树（作业二）

下面展示一些 内联代码片。

// A code block
var foo = 'bar';

// An highlighted block
#include <stdio.h>
#include <stdlib.h>

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
typedef char TElemType;

typedef enum { Link, Thread } PointerTag;

typedef struct BiThrNode {
    TElemType data;
    struct BiThrNode* lchild, * rchild;
    PointerTag LTag;
    PointerTag RTag;
}BiThrNode, * BiThrTree;
void    visit(BiThrTree T) {

	printf("%c", T->data);


}
//线索二叉树初始化
Status CreateBiThrNode(BiThrTree* B) {
    char ch;
    scanf_s("%c", &ch);
    if (ch == '#') *B = NULL;
    else {
        if (!((*B) = (BiThrNode*)malloc(sizeof(BiThrNode)))) exit(OVERFLOW);
        (*B)->data = ch;
        (*B)->LTag = Link;
        (*B)->RTag = Link;
        CreateBiThrNode(&(*B)->lchild);
        CreateBiThrNode(&(*B)->rchild);
    }
    return OK;
}

//线索二叉树线索化
void InThreading(BiThrTree B, BiThrTree* pre) {
    if (!B) return;

    InThreading(B->lchild, pre);

    if (!B->lchild) {
        B->LTag = Thread;//节点左指针指向前驱结点
        B->lchild = *pre;
    }

    if (!(*pre)->rchild) {
        (*pre)->RTag = Thread;//右指针指向后驱节点；
        (*pre)->rchild = B;
    }

    *pre = B;
    InThreading(B->rchild, pre);
}

//为线索二叉树添加头结点，使之可以双向操作
Status InOrderThreading(BiThrTree* Thrt, BiThrTree T) {
    if (!(*Thrt = (BiThrTree)malloc(sizeof(BiThrNode)))) exit(OVERFLOW);
    (*Thrt)->LTag = Link;//左指针指向左孩子
    (*Thrt)->RTag = Thread;右指针指向后驱节点；
    (*Thrt)->rchild = (*Thrt);
    if (!T) {
        (*Thrt)->lchild = (*Thrt);
        return OK;       //若根结点不存在,则该二叉树为空,让该头结点指向自身.
    }
    BiThrTree pre;
    //令头结点的左指针指向根结点
    pre = (*Thrt);
    (*Thrt)->lchild = T;
    //开始递归输入线索化
    InThreading(T, &pre);
    //此时结束了最后一个结点的线索化了,下面的代码把头结点的后继指向了最后一个结点.
    //并把最后一个结点的后继也指向头结点,此时树成为了一个类似双向链表的循环.
    pre->rchild = *Thrt;
    pre->RTag = Thread;//右指针指向后驱节点；
    (*Thrt)->rchild = pre;
    return OK;
}

//非递归遍历线索二叉树
Status InOrderTraverse(BiThrTree T) {
    BiThrTree p = T->lchild;

    while (p != T) {
        while (p->LTag == Link)p = p->lchild;//走向左孩子尽头；
        visit(p);//
        while (p->RTag == Thread && p->rchild != T) {//访问该节点的后续节点；

            p = p->rchild;
            visit(p);
        }
        p = p->rchild;

    }

    return OK;

}

int main() {
    BiThrTree B, T;
    CreateBiThrNode(&B);
    InOrderThreading(&T, B);
    printf("结果为：");
    InOrderTraverse(T);
 
}

//测试数据:abc##de#g##f###