线索二叉树

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

typedef char ElempType;

//线索存储标志位
//Link(0) :表示左右孩子的指针
//Thread(1):表示只想前驱节点的线索
typedef enum {Link,Thread} PointerTag;


//定义节点
typedef struct BiThrNode {
	char data;
	struct BiThrNode *lchild,*rchild;
	PointerTag ltag;
	PointerTag rtag;
} BiThrNode,*BiThrTree;


//全局变量，始终指向刚刚访问过的节点
BiThrTree pre;

//创建一颗二叉树，约定用户按照前序遍历输入数据
CreateBiThrTree(BiThrTree *T) {
	char c;

	printf("请输入节点的值\n");
	scanf("%c",&c);
	if(c==' ') {
		*T=NULL;
	} else {
		*T=(BiThrNode *)malloc(sizeof(BiThrNode));
		(*T)->data=c;
		(*T)->ltag=Link;
		(*T)->rtag=Link;

		//递归创建子节点
		CreateBiThrTree(&((*T)->lchild));
		CreateBiThrTree(&((*T)->rchild));

	}
}

//中序遍历线索化
InThread(BiThrTree T) {
	if(T) {
		InThread(T->lchild);
		if(!T->lchild) { //如果该节点没有左孩子设置ltag为Threa,并把lchild指向刚刚访问的节点。
			T->ltag=Thread;
			T->lchild=pre;
		}
		if(!pre->rchild) {
			pre->rtag=Thread;
			pre->rchild=T;
		}
		pre=T;//按照前序遍历，左孩子递归完 ，该 父节点了，它会是 右节点左递归后的前驱节点
		InThread(T->rchild);//递归右孩子线索华
	}
}


InOderThreading(BiThrTree *p, BiThrTree T)
{
	*p =(BiThrTree)malloc(sizeof(BiThrNode));
	(*p)->ltag=Link;
	(*p)->rtag=Thread;
	(*p)->lchild=*p;
	if(!T)
	{
		(*p)->lchild=*p;
	}
	else
	{
		(*p)->lchild=T;
		pre=*p;
		InThread(T);
		pre->rchild=*p;
		pre->rtag=Thread;
		(*p)->rchild=pre;
	}
}
void visit(char c)
{
	printf("%c",c);
}
//中序遍历二叉树，非递归
void InOderTraverse(BiThrTree T)
{
	BiThrTree p;
	p=p->lchild;
	while(p!=T)
	{
		while(p->ltag==Link)
		{
			p=p->lchild;
		}
		visit(p->data);
		while(p->rtag==Thread&&p->rchild!=T)
		{
			p=p->rchild;
			visit(p->data);
		}
		p=p->rchild; 
	}
 } 

int main() {
	BiThrTree P,T =NULL;

	CreateBiThrTree(&T);
	
	InOderThreading(&P,T);
    printf("中序遍历的结果为\n");
    InOderTraverse(P);
    
	return 0;
}