编辑代码

/***********************************************************
              在线索二叉树中查找结点的前驱和后继（137页）
/****************   算法6.11 和 算法6.12 （137页、138页）**********
		 算法6.11【中序线索二叉树中查找结点后继】
		 算法6.12【遍历中序线索二叉树】
	先序输入法创建二叉树，中序遍历方式建立中序线索二叉树
************************************************************/

#include <stdlib.h>
#include <stdio.h>

//二叉树的二叉线索类型存储表示
typedef struct BiThrNode {
	char data;						//结点数据域
	struct BiThrNode *lchild, *rchild;	//左右孩子指针
	int ltag, rtag;
} BiThrNode, *BiThrTree;

//全局变量pre
BiThrNode *pre = (BiThrNode *)malloc(sizeof(BiThrNode));
//附设指针pre始终指向刚刚访问过的结点，即结点p的前驱。
//pre是全局变量，初始化时其右孩子指针为空，便于在树的最左点开始建线索

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


void InThreading(BiThrTree p) {
	if (p != NULL) {
		InThreading(p->lchild);   //左子树递归线索化
		if (!p->lchild) {
			//p的左孩子为空
			p->ltag = 1;        //给p加上左线索
			p->lchild = pre;	//p的左孩子指针指向pre（前驱），p的左线索为pre
		} else
			p->ltag = 0;
		if (!pre->rchild) {
			//pre的右孩子为空
			pre->rtag = 1;     	 //给pre加上右线索
			pre->rchild = p;     //pre的右孩子指针指向p（后继），pre的右线索为p
		} else
			pre->rtag = 0;
		pre = p;               	 //保持pre指向p的前驱
		InThreading(p->rchild);	 //右子树递归线索化
	}
}

//算法6.11  中序线索二叉树中查找结点后继（137页）
BiThrNode *InOrderNext(BiThrNode *p) {
	BiThrNode *q;
	q = p->rchild;
	if (p->rtag != 1) {
		while (q->ltag == 0) {
			q = q->lchild; //查找q的最左下结点
		}
	}
	return q;
}


// 算法6.12  遍历中序线索二叉树（138页）
void InThredTraverse(BiThrTree p) {
	//中序遍历二叉线索树T的非递归算法，对每个数据元素直接输出
	if (p != NULL) {
		while (p->ltag == 0) {	//查找中序遍历序列的开始结点
			p = p->lchild;
		}
		do {
			printf("%2c", p->data);
			p = InOrderNext(p);
		} while (p != NULL) ;


	}
}//InThredTraverse

int main() {
	pre->rtag = 1;
	pre->rchild = NULL;
	BiThrTree tree;
	printf("建立树，按先序遍历序列输入结点\n");
	printf("空结点为@，结束按回车\n");
	CreateBiTree(tree);
	printf("建立中序线索二叉树\n");
	InThreading(tree);
	printf("线索化完毕！\n");
	printf("遍历中序线索二叉树，结果为：\n");
	InThredTraverse(tree);
	return 0;
}

//测试样例1 (教材第131页图6.10中的二叉树，先序遍历输入结点)
// 输入结点  ABD@@E@G@@C@FH@@@
// 输出  DBEGACHF

//测试样例2 (教材第134页图6.11，先序遍历输入结点))
// 输入结点  ABH@@FD@@@E@CK@@G@@
// 输出  HBDFAEKCG