#include <stdio.h>
#include <stdlib.h>
#define TElemType int//宏定义，结点中数据域的类型
//枚举，Link为0，Thread为1
typedef enum PointerTag {
Link,
Thread
}PointerTag;
//结点结构构造
typedef struct BiThrNode {
TElemType data;//数据域
struct BiThrNode* Lchild, * Rchild;//左孩子，右孩子指针域
struct BiThrNode* parent;
PointerTag Ltag, Rtag;//标志域
}BiThrNode, * BiThrTree;
BiThrTree pre = NULL;
//创建二叉树，根结点的 parent 为 NULL
void CreateBiTree(BiThrTree* T, BiThrTree parent) {
int num;
scanf("%d", &num);
//如果输入的值为 0，表示无此结点
if (num == 0) {
*T = NULL;
}
else
{
//创建新结点
*T = (BiThrTree)malloc(sizeof(BiThrNode));
(*T)->data = num;
(*T)->Ltag = Link;
(*T)->Rtag = Link;
(*T)->parent = parent;
CreateBiTree(&((*T)->Lchild), *T);//创建该结点的左孩子
CreateBiTree(&((*T)->Rchild), *T);//创建该结点的右孩子
}
}
//后序遍历实现二叉树线索化
void PostThreading(BiThrTree p) {
//如果当前结点存在
if (p) {
if (p->Ltag == Link) {
PostThreading(p->Lchild);//递归当前结点的左子树，进行线索化
}
if (p->Rtag == Link) {
PostThreading(p->Rchild);//递归右子树进行线索化
}
//如果当前结点没有左孩子，左标志位设为1，左指针域指向上一结点 pre
if (!p->Lchild) {
p->Ltag = Thread;
p->Lchild = pre;
}
//如果 pre 没有右孩子，右标志位设为 1，右指针域指向当前结点。
if (pre && !pre->Rchild) {
pre->Rtag = Thread;
pre->Rchild = p;
}
pre = p;//pre指向当前结点
}
}
//在以 p 结点为根结点的二叉树中，找到后序序列的第一个结点
BiThrTree GET_First(BiThrTree p) {
if (!p) {
return NULL;
}
else
{
//从根结点开始，不断的找左孩子
while (p->Ltag == Link) {
p = p->Lchild;
}
// p 是那个没有左孩子的结点，如果它有右孩子，进入它的右子树，以同样的方式找到第一个结点
if (p->Rtag == Link) {
return GET_First(p->Rchild);
}
else
{ //如果 p 没有右孩子，那么它就是第一个结点
return p;
}
}
}
//找到 p 结点的下一个结点
BiThrTree GET_Next(BiThrTree p) {
if (!p) {
return NULL;
}
else
{
if (p->Rtag == Thread) {
return p->Rchild;
}
else
{
//如果当前结点是根结点
if (p->parent == NULL) {
return NULL;
}
//如果当前结点是左孩子
else if (p == p->parent->Lchild)
{
if (p->parent->Rtag == Link) {
return GET_First(p->parent->Rchild);
}
else
{
return p->parent;
}
}
//如果当前结点是右孩子
else
{
return p->parent;
}
}
}
}
//遍历后序线索二叉树
void PostOrderThraverse_Thr(BiThrTree p) {
p = GET_First(p);
while (p) {
printf("%d ", p->data);
p = GET_Next(p);
}
}
int main() {
BiThrTree t;
printf("输入前序二叉树:\n");
CreateBiTree(&t,NULL);
PostThreading(t);
printf("输出后序序列:\n");
PostOrderThraverse_Thr(t);
return 0;
}
/*
执行实例：
输入前序二叉树:
1 2 4 0 0 0 3 5 0 0 6 0 0
输出后序序列:
4 2 5 6 3 1
*/
