// Day08Data.cpp : 线索二叉树

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


// 定义线索二叉树结构体
typedef struct Tree
{
	int data, Ltag, Rtag;			// 数据域及左右标记
	struct Tree *Lchild, *Rchild;	// 左右孩子指针
}Tree,*Trees;

Trees pre = NULL;	

// 初始化二叉树,只设置根节点 
void InitBiTree(Trees *boot)
{
	*boot = (Trees)malloc(sizeof(Tree));
	(*boot)->Lchild = (*boot)->Rchild = NULL;
	(*boot)->Ltag = (*boot)->Rtag = 0;
}

// 创建二叉树
void CreateBiTree(Trees &boot)
{
	int number;
	scanf_s("%d", &number);
	if (number == 0)
	{
		boot = NULL;
	}
	else
	{
		boot = (Trees)malloc(sizeof(Tree));
		boot->data = number;
		boot->Lchild = boot->Rchild = NULL;
		boot->Ltag = boot->Rtag = 0;
		CreateBiTree(boot->Lchild);
		CreateBiTree(boot->Rchild);
	}
}


// 添加线索
void InserLineTree(Trees &boot)
{
	if (boot != NULL)
	{
		InserLineTree(boot->Lchild);
		if (boot->Lchild == NULL)
		{
			boot->Ltag = 1;
			boot->Lchild = pre;		// 设置前驱
		}
		if (pre != NULL && pre->Rchild == NULL)
		{
			pre->Rchild = boot;
			pre->Rtag = 1;
		}
		pre = boot;	// 当前访问节点是下一个访问节点的前驱
		InserLineTree(boot->Rchild);	// 线索右子树
	}
}


// 创建头节点
Trees InorderThread(Trees &rt)
{
	Trees throot;
	if (!(throot = (Trees)malloc(sizeof(Tree))))
	{
		printf("创建头结点失败.\n\n");
		exit(1);
	}

	throot->Ltag = 0;			// 指向左子树
	throot->Rtag = 1;			// 指向前驱
	throot->Rchild = throot;	// 指向自己

	if (!throot)
	{
		throot->Lchild = throot;  // 如果二叉树为空，指针指向头节点
	}
	else
	{
		throot->Lchild = rt;		// 指向二叉树的根
		pre = throot;				// 指向头结点
		InserLineTree(rt);			// 添加线索
		pre->Rchild = throot;
		pre->Rtag = 1;
		throot->Rchild = pre;
	}
	return throot;
}

// 使用中序遍历查找节点前驱
void InPre(Trees boot)
{
	Trees q = NULL;
	if (boot->Ltag == 1)
	{
		pre = boot->Lchild;
	}
	else
	{
		for (q = boot->Lchild; q->Rtag == 0; q = q->Rchild)
		{
			pre = q;
		}
	}
	if (pre)
	{
		printf("中序遍历找到的前驱为：%d\n", pre->data);
	}
	else
	{
		printf("中序遍历没有找到前驱!\n");
	}
}


// 使用中序遍历查找节点后继
void InNext(Trees boot)
{
	Trees q = NULL;
	if (boot->Rtag == 1)
	{
		pre = boot->Rchild;
	}
	else
	{
		for (q = boot->Rchild; q->Ltag == 0; q = q->Lchild)
		{
			pre = q;
		}
	}
	if (pre)
	{
		printf("中序遍历找到的后继为：%d\n", pre->data);
	}
	else
	{
		printf("中序遍历没有找到后继!\n");
	}
}

// 查找线索二叉树上的第一个节点
Trees InFirst(Trees boot)
{
	Trees p = boot;
	if (!p)
	{
		return 0;
	}
	while (p->Ltag == 0)
	{
		p = p->Lchild;

	}
	return p;
}


// 中序遍历线索二叉树
void TinOrder(Trees &throot)
{
	Trees p;
	p = throot->Lchild;
	while (p != throot)
	{
		while (p->Ltag == 0)
		{
			p = p->Lchild;
		}
		printf("%d ", p->data);
		while (p->Rtag == 1 && p->Rchild != throot)
		{
			p = p->Rchild;
			printf("%d ", p->data);
		}
		p = p->Rchild;
	}
	printf("\n");
}



int main()
{
	Trees boot = NULL;
	printf("创建线索二叉树，当用户输入0结束操作!\n");
	CreateBiTree(boot);

	Trees throot;		// 头节点
	throot = InorderThread(boot);
	TinOrder(throot);	// 中序遍历
	InPre(boot);		// 中序查找前驱
	InNext(boot);		// 中序查找后继
	Trees bt = InFirst(boot);
	printf("中序遍历线索二叉树的第一个节点为：%d", bt->data);

	return 0;
}