编辑代码

/***********************************************************/
/****************   算法6.10  建立中序线索二叉树 （137页）**********
	先序输入法创建二叉树，中序遍历方式建立中序线索二叉树
	            以结点P为根的子树中序线索化
************************************************************/

#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));
//指针p指向当前访问的结点，附设指针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);	//递归创建右子树
	}
}

//*******   算法6.10  建立中序线索二叉树 （137页）*********
void InThreading(BiThrTree p) {
	if (p) {
		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->rtag = 1;
			pre->rchild = p;      //pre的右线索为p
		} else {
			pre->rtag = 0;
		}

		pre = p;               	 //保持pre指向p的前驱
		InThreading(p->rchild);	 //右子树递归线索化
	}
}//InThreading

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

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

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