线索二叉树

传统的二叉树存储仅能体现一种父子关系，不能直接得到结点在遍历中的前驱和后继。
故引入线索二叉树，目的是为了加快查找结点前驱和后继的速度。
同时，原本普通的二叉树存储有$n+1$个指针域浪费，线索二叉树利用了这部分空间，减少了资源浪费。

结构：
规定：
若无左子树，令lchild指向其前驱结点
若无右子树，令rchild指向其后继结点
增加两个标志域，指向左孩子的前驱、右孩子的后继

typedef struct ThreadNode {
	int data; // 数据元素
	struct ThreadNode *lchild, *rchild; //左右孩子指针 
	int ltag, rtag; //左右线索标志 
}ThreadNode, *ThreadTree; 

线索二叉树操作

中序遍历线索化

//中序线索化
void InThread(ThreadTree &p, ThreadTree &pre) {
	if (p != NULL) {
		// 首先对左子树做中序线索化
		InThread(p->lchild, pre);
		// 再对当前节点做中序线索化，处理的是当前节点的前继关系
		//当当前节点的左子节点为null时，就将左指针域赋值为pre
		//并标记左tag，表明左指针域指向的是前继节点
		if(p->lchild == NULL) {
			p->lchild = pre;
			p->ltag = 1;
		}
		// 处理上一个节点的后继关系 
		// preNode的右指针域指向p（此处的p为后继节点） 
		if (pre && pre->rchild==NULL) {
			pre->child = p;
			pre->rtag = 1;
		}
		//对当前节点处理完之后，pre被赋值为p
		pre = p;
		 // 最后对右子树做中序线索化
		InThread(p->rchild, pre);
	}
}

线索二叉树中序遍历

// 寻找左子树的遍历起始节点（最左下结点） 
ThreadTree Firstnode(ThreadNode *p) {
	while(T->ltag == 0)
		T = T->lchild;
	return T; 
}
// 返回中序线索二叉树中结点p在中序序列下的后继 
ThreadTree NextNode(ThreadNode *p) {
	if (p->rtag == 0)//右链不是线索，寻找右子树中最左下结点 
		return Firstnode(p->rchild);
	else
		return p->rchild;
}

void inorder(ThreadNode *T) {
	for(ThreadNode *p=Firstnode(T); p != NULL; p=nextNode(p)) {
		cout << p->data << " ";
	}
}

先序遍历线索化

void PreThread(ThreadTree &p, ThreadTree &pre) {
	if (p != NULL) {
		if (p->lchild == NULL) {
			p->lchild = pre;
			p->ltag = 1; 
		}
		if (pre && pre->rchild == NULL) {
			pre->rchild = p;
			pre->rtag = 1;
		}
		pre = p;
		if (p->ltag == 0)//左结点不是线索，继续往左子树线索化 
			PreThread(p->lchild, pre);
		if (p->rtag == 0)//右结点不是线索，继续往右子树线索化
			preThread(p->rchild, pre);
	}
}

先序二叉树先序遍历

ThreadTree NextNode(ThreadNode *p) {
	if (p->ltag == 0)
		return p->lchild;
	else
		return p->rchild;
}

void preOrder(ThreadTree T) {
	for (ThreadNode *p=T; p!=NULL; p=nextNode(p)) {
		cout << p->data << endl;
	}
}

Q.E.D.