本章具体实现前序和后序线索化的代码，相关原理可参考一下章节：

C数据结构与算法-基础整理-树-06：线索二叉树（一）

0x01.前序顺序下的线索二叉树

二叉树的建立方式与上文完成相同，不同的只有线索化和遍历的过程

线索化：

//前序线索化过程
void PreThreading(BinTree BT)
{if (BT){if (!BT->Left)//左孩子不存在,线索化{BT->Ltag = 1;BT->Left = pre;//前驱}if (!pre->Right)//右孩子不存在，线索化{pre->Rtag = 1;pre->Right = BT;}pre = BT;//更新前指针if (BT->Ltag == 0)//左孩子存在，继续递归{PreThreading(BT->Left);}if (BT->Rtag == 0)//右孩子存在，继续递归{PreThreading(BT->Right);}}
}

带头结点线索化：

与中序的方式一模一样。

//带头结点的前序线索化
void PreOrderThreading(BinTree* Head, BinTree BT)
{*Head = (BinTree)malloc(sizeof(TreeNode));//给头结点分配空间(*Head)->Ltag = 0;//左孩子是根结点(*Head)->Rtag = 1;//右孩子是线索(*Head)->Right = (*Head);//右孩子先指向自身，防止原二叉树为空if (!BT)//二叉树为空{(*Head)->Left = (*Head);//左孩子也指向自身return;}pre = (*Head);//前指针指向头结点(*Head)->Left = BT;PreThreading(BT);//开始正常的前序线索化pre->Right = *Head;pre->Rtag = 1;(*Head)->Right = pre;
}

遍历：

注意传入的是头结点。

//带头结点的前序线索遍历
void PreOrderTravel1(BinTree BT)
{BinTree p = BT->Left;while (p != BT){printf("%c -> ", p->data);if (p->Ltag == 0)//左孩子存在访问左孩子{p = p->Left;}else//左孩子是前驱，开始访问右孩子{p = p->Right;}}
}

具体主函数测试代码见上篇

0x02.后序顺序下的线索二叉树

不同之处：

后序遍历时先把孩子都遍历完了再去遍历父结点，想要回来去找父结点，必须再结构中增加一个指向父结点的指针。

结构：

typedef struct TreeNode
{char data;struct TreeNode* Left;struct TreeNode* Right;struct TreeNode* Parent;int Ltag;//用于线索化的标志变量  左为1表示前驱 右为1表示后继int Rtag;
}TreeNode,*BinTree;//定义了这个结构体为 TreeNode ,这个二叉树指针为 BinTree

建立二叉树：

与普通不同的是构造完一个结点后，其parent结点需要指向上一个结点。

//后序线索化的创建二叉树方式
void CreateTree1(BinTree* BT,BinTree*p)//p为父结点信息
{char ch;scanf("%c", &ch);if (ch == '#'){*BT = NULL;}else{*BT = (BinTree)malloc(sizeof(TreeNode));if (!BT)exit(-1);(*BT)->data = ch;(*BT)->Ltag = 0;(*BT)->Rtag = 0;(*BT)->Parent = *p;CreateTree1(&(*BT)->Left,BT);CreateTree1(&(*BT)->Right,BT);}
}

线索化：

//后序线索化
void PostThreading(BinTree BT)
{if (BT){PostThreading(BT->Left);PostThreading(BT->Right);if (!BT->Left){BT->Ltag = 1;BT->Left = pre;}if (pre && !pre->Right){pre->Rtag = 1;pre->Right = BT;}pre = BT;}
}

遍历：

//后序线索化遍历
void PostOrderTraverse(BinTree BT)
{BinTree p = BT;pre = NULL;//重新初始化前指针while (p){while (p->Ltag == 0)//一直向左找最左端的孩子{p = p->Left;}while (p->Rtag == 1)//右孩子是后继的话，一直遍历下去{printf("%c -> ", p->data);pre = p;//记录当前结点的前驱p = p->Right;}if (p == BT)//访问到了根结点，遍历完成，退出{printf("%c -> ", p->data);break;}while (p && p->Right == pre)//此时右孩子真实存在，如果等于它的前驱，说明开始回溯访问父结点了{printf("%c -> ", p->data);pre = p;p = p->Parent;}if (p->Rtag == 0)//右孩子存在，一直访问下去，但不打印{p = p->Right;}}
}

0x03.感悟

1.线索化过程都查不多，不过顺序不同。

2.后序的特殊遍历方式导致在非递归的遍历时需要特殊处理

3.注意父指针的灵活运用。

本章结束。