1.头文件及类型定义

#include<stdio.h>
#include<stdlib.h>
#define ElemType char

2.线索二叉树结点类型定义

//线索二叉树结点类型定义
typedef struct ThreadNode {
	ElemType data;							//数据元素
	struct ThreadNode* lchild, * rchild;	//左、右孩子指针
	int ltag, rtag;							//左、右线索标志
	//tag=0,表示指针指向孩子;tag=1,表示指针是“线索”,ltag指向前驱，rtag指向后继
}ThreadNode, * ThreadTree;

3.函数声明

/*函数声明*/
void CreateThTree(ThreadTree& T);			//1.先序建立线索二叉树
void InitThread(ThreadTree& T);				//2.初始化tag
void visit1(ThreadNode* q);					//3-1.访问并建立线索
void PostThread(ThreadTree T);				//3-2.遍历
void CreatePostThread(ThreadTree T);		//3-3.后序线索化主过程
ThreadNode* PreNode(ThreadNode* p);			//4.找到p的前驱结点
void visit2(ThreadNode* p);					//5-1.打印结点
void RevPostOrder(ThreadNode* T);			//5-2.利用后序前驱实现逆向后序遍历

4.基本操作

4.1 先序建立线索二叉树

/*1.先序建立线索二叉树*/
void CreateThTree(ThreadTree& T) {
	char c;
	scanf("%c", &c);
	if (c == '#')
		T = NULL;
	else {
		T = (ThreadNode*)malloc(sizeof(ThreadNode));
		T->data = c;
		CreateThTree(T->lchild);
		CreateThTree(T->rchild);
	}
}

4.2 初始化tag

/*2.初始化tag*/
void InitThread(ThreadTree& T) {
	if (T != NULL) {
		T->ltag = 0;
		T->rtag = 0;	//初始化当前树中的tag指针为0，表示还未线索化
		InitThread(T->lchild);	//递归遍历左子树
		InitThread(T->rchild);	//递归遍历右子树
	}
}

4.3 后序线索化二叉树

4.3.1 访问并建立线索

ThreadNode* pre = NULL;		//pre指向当前访问结点的前驱
//3-1.访问并建立线索
void visit1(ThreadNode* q) {
	if (q->lchild == NULL) {	//左子树为空，建立前驱线索
		q->lchild = pre;
		q->ltag = 1;
	}
	if (pre != NULL && pre->rchild == NULL) {	
		pre->rchild = q;	//建立前驱结点的后继线索
		pre->rtag = 1;
	}
	pre = q;			//标记当前结点为刚刚访问过的结点
}

4.3.2 遍历

//3-2.遍历
void PostThread(ThreadTree T) {
	if (T != NULL) {
		PostThread(T->lchild);	//后序遍历左子树
		PostThread(T->rchild);	//后序遍历右子树
		visit1(T);				//访问根节点
	}
}

4.3.3 后序线索化主过程

//3-3.主过程
void CreatePostThread(ThreadTree T) {
	pre = NULL;			//pre初始化为NULL
	if (T != NULL) {	//非空二叉树才能线索化			
		PostThread(T);	//后序线索化二叉树
		if (pre->rchild == NULL)	
			pre->rtag = 1;			//处理遍历的最后一个结点
	}
}

4.4 寻找后序前驱

//4.寻找后序前驱
ThreadNode* PreNode(ThreadNode* p) {
	if (p->ltag == 0) {		//若ltag=0，说明所找结点有左孩子
		if (p->rtag == 0)		//若rtag=0
			return p->rchild;		//说明所找结点有右孩子，根据后序遍历的特点(左-右-根)，右孩子为前驱
		else                    //若rtag=1
			return	p->lchild;		//说明所找结点无右孩子，则前驱结点为其左孩子
	}
	else
		return p->lchild;	//若ltag=1，说明所找结点无左孩子，则返回前驱线索
}

4.5 逆向后序遍历

4.5.1 打印结点

//5-1.打印结点
void visit2(ThreadNode* p) {
	printf("%c\t", p->data);
}

4.5.2 利用后序前驱实现逆向后序遍历

//5-2.利用后序前驱实现逆向后序遍历：空间复杂度为O(1) 
void RevPostOrder(ThreadNode* T) {
	for (ThreadNode* p = T; p != NULL; p = PreNode(p))
		visit2(p);
}

4.6 main函数

int main() {
	ThreadTree T;

	/*1、创建二叉树*/
	printf("先序创建二叉树：");
	CreateThTree(T);

	/*2、初始化tag为0*/
	InitThread(T);

	/*3、后序线索化*/
	CreatePostThread(T);

	/*4、寻找后序前驱（用根结点测试）*/
	printf("根结点的后序前驱为：%c\n", PreNode(T)->data);

	/*6、逆向后序遍历二叉树*/
	printf("<————逆向后序遍历————>\n");
	RevPostOrder(T);

	return 0;
}

4.7 测试

4.7.1 二叉树结构

4.7.2 测试结果

5.小结

• 对于后序线索二叉树并不会出现“转圈"现象，原因是根结点是最后被访问的，不可能再回去访问其左右孩子指向的子树。
• 另外，同先序线索二叉树一样，后序线索二叉树也存在类似的问题：即只能找到后序前驱。具体分析同先序线索二叉树类似，已在上一篇文章小结中介绍，此处不再展开。

以上图为参考：

• 中序遍历（左根右）：DGBEAFC；
• 先序遍历（根左右）：ABDGECF；
• 后序遍历（左右根）：GDEBFCA；

讨论如何在线索二叉树查找结点的前驱与后继？

一、中序线索二叉树的遍历查找：DGBEAFC

① 查找p指针所指结点的前驱：

• 若 p->Ltag==1，则p的左链指向其前驱；
• 若 p->Ltag==0，说明有左子树，结点的前驱是遍历左子树时最后访问的一个结点（左子树中最右下结点）。

例如：左根右 --> ((左根右)根右) --> (((左根右)根右)根右)；
我们对根结点A进行中序遍历，可以发现，它的左子树是B为根节点，按中序遍历结果是先返回 D-G-B-E-A 满足(左子树最后访问的一个结点)。

② 查找p指针所指结点的后继：

• 若 p->Rtag==1，则p的左链指向其前驱；
• 若 p->Rtag==0，说明有右子树，结点的后继是遍历右子树时第一个访问的结点（右子树中最左下结点）。

例如：左根右 --> (左根(左根右))；
我们对根结点A进行中序遍历，可以发现，它的右子树是C为根节点，第一个访问是F结点，满足中序遍历结果。

二、先序线索二叉树的遍历查找：ABDGECF

① 查找p指针所指结点的前驱：

• 若 p->Ltag==1，则p的左链指向其前驱；
• 若 p->Ltag==0，说明有左子树，若 *p 结点为根结点，则找不到它的前驱，因为由于(根左右)，推不出它的前驱；若 *p 结点为左孩子 || (右孩子&兄弟节点)为NULL，则 *p 结点的前驱是它的父节点； 否则若 *p 结点为右孩子，它的前驱是兄弟节点。

② 查找p指针所指结点的后继：

• 若 p->Rtag==1，则p的左链指向其前驱；
• 若 p->Rtag==0，说明有右子树，由遍历规则知则先序后继为左孩子，若p没有左孩子，则先序后继为右孩子。

三、后序线索二叉树的遍历查找：GDEBFCA

① 查找p指针所指结点的前驱：

• 若 p->Ltag==1，则p的左链指向其前驱；
• 若 p->Ltag==0，若p有右孩子，则后序前驱为右孩子，若p没有右孩子，则后序前驱为左孩子。

② 查找p指针所指结点的后继：

• 若 p为根节点，则没有后继；若p为左孩子，它的后继结点是它的兄弟结点或者是p的父节点；若p为右孩子，它的后继是父节点。

四、算法：遍历中序线索二叉树

#include<iostream>
using namespace std;

//二叉树的二叉线索类型存储表示
typedef struct BiThrNode{
	char data;
	struct BiThrNode *lchild,*rchild;	//左右孩子指针
	int LTag,RTag;
}BiThrNode,*BiThrTree;

BiThrNode *pre=new BiThrNode;  // 全局变量pre

void CreateBiTree(BiThrTree &T){
	//按先序次序输入二叉树中结点的值（一个字符），创建二叉链表表示的二叉树T
	char ch;
	cin >> ch;
	if(ch=='#')  T=NULL;			//递归结束，建空树
	else{
		T=new BiThrNode;
		T->data=ch;//生成根结点
		CreateBiTree(T->lchild);	//递归创建左子树
		CreateBiTree(T->rchild);	//递归创建右子树
	}
}

// 结点P为根的子树中序线索化
void InThreading(BiThrTree p){
	//pre是全局变量，初始化时其右孩子指针为空，便于在树的最左点开始建线索
	if(p){
		InThreading(p->lchild);             			//左子树递归线索化
		if(!p->lchild){    //p的左孩子为空
			p->LTag=1;   	//给p加上左线索
			p->lchild=pre; 			//p的左孩子指针指向pre（前驱）
		}
		else
			p->LTag=0;
		if(!pre->rchild){		//pre的右孩子为空
			pre->RTag=1;    		//给pre加上右线索
			pre->rchild=p;      	//pre的右孩子指针指向p（后继）
		}
		else
			pre->RTag=0;
		pre=p;        			//保持pre指向p的前驱
		InThreading(p->rchild);	//右子树递归线索化
    }
}

// 带头结点的中序线索化
void InOrderThreading (BiThrTree &Thrt,BiThrTree T){
	//中序遍历二叉树T，并将其中序线索化，Thrt指向头结点
	Thrt=new BiThrNode;           //建头结点
	Thrt->LTag=0;  		   		 //头结点有左孩子，若树非空，则其左孩子为树根
	Thrt->RTag=1;				//头结点的右孩子指针为右线索
	Thrt->rchild=Thrt;            	//初始化时右指针指向自己
	if(!T)  Thrt->lchild=Thrt;      //若树为空，则左指针也指向自己
	else{
	  Thrt->lchild=T;  pre=Thrt;   //头结点的左孩子指向根，pre初值指向头结点
	  InThreading(T);             //调用算法，对以T为根的二叉树进行中序线索化
	  pre->rchild=Thrt;          //算法，结束后，pre为最右结点，pre的右线索指向头结点
	  pre->RTag=1;
	  Thrt->rchild=pre;        //头结点的右线索指向pre
	}
}

void InOrderTraverse_Thr(BiThrTree T){
    //T指向头结点，头结点的左链lchild指向根结点，可参见线索化算法5.8。
    //中序遍历二叉线索树T的非递归算法，对每个数据元素直接输出
	BiThrTree p;
	p=T->lchild;              //p指向根结点
    while(p!=T){			  //空树或遍历结束时，p==T
		while(p->LTag==0)	  //沿左孩子向下
			p=p->lchild;	 //访问其左子树为空的结点
		cout<<p->data;
		while(p->RTag==1&&p->rchild!=T){
			p=p->rchild;	//沿右线索访问后继结点
			cout<<p->data;
		}
		p=p->rchild;
    }
}

int main(){
	pre->RTag=1;
	pre->rchild=NULL;
	BiThrTree tree,Thrt;

	cout<<"请输入建立二叉链表的序列，例如(ABD#G##E##CF###):\n";
	CreateBiTree(tree);
	InOrderThreading(Thrt,tree);
	cout<<"中序遍历线索二叉树的结果为：\n";
	InOrderTraverse_Thr(Thrt);
	cout<<endl;
}

遍历二叉树时结点访问的先后顺序信息只有子啊遍历的动态过程中得到。若经常遍历或者要求取遍历时结点的前驱、后继信息则应修改二叉链表的结构以保存该遍历顺序链表，加上线索的二叉树称为线索二叉树。分先序、中序、后序线索二叉树。

这里介绍的是中序线索二叉树.

首先是辅助宏的定义：

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OVERFLOW -1
#define UNDERFLOW -2
#define NULL 0
#define TREE_SIZE 1
#define TREEINCREMENT 1
typedef int Status;
typedef char TElemType;
typedef enum {LINK,THREAD} PointerTag; //指针标记类型
/*LINK 0 代表指向孩子的指针
THREAD 1 代表为指向前驱后继的线索*/

线索链表的存储结构定义：

//线索链表的存储结构定义
typedef struct BiThrNode{
   TElemType data;
   struct BiThrNode *lchild,*rchild;//左右指针
   PointerTag LTag,RTag;//指针性质LINK或者THREAD
}BiThrNode,*BiThrTree;

输出e 输出二叉树 调用先序遍历函数 用函数传递给其参数visit即可.

Status PrintTElem(TElemType e){
   //输出e 输出二叉树 调用先序遍历函数 用函数传递给其参数visit即可
   printf("%c",e);
   return OK;
}

先序创造线索链表各节点 注意输入时空指针不要丢 输入空格是空树，停止 否则创造根节点 递归创造左子树, 递归创造右子树.

Status CreatBiTree(BiThrTree &T){
   /*先序创造线索链表各节点 注意输入时空指针不要丢
   输入空格是空树，停止 否则创造根节点 递归创造左子树
   递归创造右子树*/
   TElemType e;
   scanf("%c",&e);
   if(e==' ')
       T=NULL;
   else{
       T=(BiThrTree)malloc(sizeof(BiThrNode));
       if(!T)//存储分配失败
           exit(OVERFLOW);
       T->data=e;
       T->lchild=NULL;
       T->rchild=NULL;
       CreatBiTree(T->lchild);
       CreatBiTree(T->rchild);
   }
   return OK;
}

遍历以p为根的树并添加前驱和后继线索信息 pre指向遍历后第一个结点的前驱 函数返回时pre指向最后一个访问的结点 

递归求解 空时无操作 否则先递归的向左子树添加线索信息 后处理与p相关的线索信息 再递归的向右子树添加线索信息 注意处理左右子树时pre的取值..

void InTreading(BiThrTree p,BiThrTree &pre){
    /*遍历以p为根的树并添加前驱和后继线索信息 pre指向遍历后第一个结点的前驱
    函数返回时pre指向最后一个访问的结点
    递归求解 空时无操作 否则先递归的向左子树添加线索信息 后处理与p相关的线索信息
    再递归的向右子树添加线索信息 注意处理左右子树时pre的取值*/
   if(p){
       InTreading(p->lchild,pre);
       if(!p->lchild){
           p->LTag=THREAD;
	   p->lchild=pre;
       }
       else
           p->LTag=LINK;
       if(!pre->rchild) { 
	   pre->RTag=THREAD;
	   pre->rchild=p;
       }
       else
	   pre->RTag=LINK;
       pre=p; //修改pre
       InTreading(p->rchild,pre);
   }
}

T为原二叉树 T指向树的根结点 将T中序线索化为Thrt,开辟头结点并赋初值 遍历原二叉树 根据有无孩子修改标记并适时添加线索信息 最后结点单独处理.

Status InOrderTheading(BiThrTree &Thrt,BiThrTree T){
   //T为原二叉树 T指向树的根结点 将T中序线索化为Thrt
   //开辟头结点并赋初值 遍历原二叉树 根据有无孩子修改标记并适时添加线索信息 最后结点单独处理
   Thrt=(BiThrTree)malloc(sizeof(BiThrNode));
   if(!Thrt)
       exit(OVERFLOW);
   BiThrNode *pre;
   Thrt->lchild=Thrt;//假设T为空
   Thrt->LTag=LINK;
   Thrt->RTag=THREAD;
   Thrt->rchild=Thrt;
   if(T){
       Thrt->lchild=T;
       pre=Thrt;
       InTreading(T,pre);
       pre->RTag=THREAD;//处理最后一个结点
       pre->rchild=Thrt;
       Thrt->rchild=pre;
   }
   return OK;
}

中序遍历线性链表.  令p指向原树根 设法让p指向第一个应该访问的结点 只要左孩子不空就令他指向左孩子 即 第一个左标记不为LINK的结点 访问p 只要p->THREAD 就让p=p->rchild 并访问p 否则令p指向右子树的根  重复上面操作 直到p指向头结点 遍历完毕.

复杂度也为O(n)，但是没有递归，不需要栈。

Status InOrderTraverse_Thr(BiThrTree T,Status (*visit)(TElemType)){
    /*中序遍历线性链表
    令p指向原树根 设法让p指向第一个应该访问的结点 只要左孩子不空就令他指向左孩子 即
    第一个左标记不为LINK的结点 访问p 只要p->THREAD 就让p=p->rchild 并访问p 否则令p指向右子树的根
    重复上面操作 直到p指向头结点 遍历完毕*/
    BiThrNode *p=T->lchild;//p访问根结点
    while(p!=T){//未遍历结束
        while(p->LTag==LINK) //p指向第一个待访问的结点
	    p=p->lchild;
	if(!visit(p->data))
	    return ERROR;
	while(p->RTag==THREAD&&p->rchild!=T){
	//只要是线索就前进
	    p=p->rchild; 
            if(!visit(p->data))
		return ERROR;
	}
	p=p->rchild;//当前结点右子树非线索 p指向右子树根
    }
    return OK;
}//T(n)=O(n)