[数据结构与算法]二叉树的线索化及其遍历（前序和中序）

#include<iostream>
using namespace std;
enum Tag { link, thread };
typedef struct Bitree
{
	char sign;
	int data;
	Bitree* left;
	Bitree* right;
	Tag ltag;
	Tag rtag;
}bi_node;
void cre_tree(bi_node* &node);//注意引用，比二级指针更方便
//————————————————————————————
void pre_display(bi_node*);//前序遍历
void in_display(bi_node*);//中序遍历
void post_display(bi_node*);//后序遍历
//————————————————————————————
void pre_cueing(bi_node*);//前序线索化
void in_cueing(bi_node*);//中序线索化
//————————————————————————————
void pre_traversal(bi_node* node);//前序遍历线索树
void in_traversal(bi_node* node);//中序遍历线索树
//————————————————————————————
//注意这里的pre要全局呀！！
//********************
bi_node* pre;
int main()
{
	cout << "输入序列以创建二叉树：（如AB#D##C##）\n";
	
	char signs = getc(stdin);
	ungetc(signs, stdin);
	bi_node* tree = NULL;
	cre_tree(tree);
	cout << "二叉树创建成功！";
	cout << "\n前序遍历：" << endl;
	pre_display(tree);
	cout << "\n中序遍历：" << endl;
	in_display(tree);
	cout << "\n后序遍历：" << endl;
	post_display(tree);
	pre = NULL;
	pre_cueing(tree);
	cout << "\n先序线索化完成！" << endl;
	cout << "先序遍历线索化树：" << endl;
	pre_traversal(tree);
	cout << "\n创建一棵新二叉树：" << endl;//必须重新创建一棵树用来中序线索化，前一棵树已经被前序线索化了，不能再被中序线索化
	getchar();//吸取上一次的回车
	char new_signs = getchar();
	ungetc(new_signs, stdin);//把读取的第一个字符重新放入缓冲区首位置
	bi_node* new_tree = NULL;
	cre_tree(new_tree);
	pre = NULL;//注意这里pre重新设置
	in_cueing(new_tree);
	cout << "中序线索化完成！" << endl;
	cout << "中序遍历线索化树：" << endl;
	in_traversal(new_tree);

}
void cre_tree(bi_node* &node)//创建二叉树;
{
	char ch = getc(stdin);
	if (ch == '#')
	{
		node = NULL;//'#'代表此处为NULL
		return;
	}
	else
	{
		node = new bi_node;    //如果不为'#'，则创捷新节点
		node->sign = ch;      
		node->ltag = node->rtag = link;//初始化节点，左右孩子都为link（因为此时没有加线索）
		cre_tree(node->left);  
		cre_tree(node->right);
	}
}

void pre_cueing(bi_node* node)//前序线索化思路不要与遍历前序线索化混淆
{                             //前序线索化的的节点经过顺序和建立二叉树的节点经过的顺序是相同的！！
	if (node == NULL)
		return;
	if (node->left == NULL)
	{
		node->ltag = thread;
		node->left = pre;
	}
	if (pre!=NULL && pre->right == NULL)//pre!=NULL是为了应付第一个节点，它的前驱节点是pre，而此时pre是NULL，不存在pre->right
	{
		pre->rtag = thread;           
		pre->right = node;
	}                                 
	//以上两个if内的操作：1.将本节点连上前驱  2.将前驱连上后继（即本节点）
	pre = node;//！！！
	if (node->ltag == link)//ltag为link才可进入！否则有可能再次进入前驱节点而陷入死循环！
		pre_cueing(node->left);
	if (node->rtag == link)//node->rtag一定是link，此if可删，不过为了统一，还是与上面对应
		pre_cueing(node->right);
	//若ltag和rtag都不是link，即左右孩子都不存在，则按照正常递归顺序进入到下一个节点（依次弹栈）
}
void in_cueing(bi_node* node)
{
	if (node == NULL)
		return;
	in_cueing(node->left);//递归到最左边的子树;
	if (node->left == NULL)
	{
		node->left = pre;
		node->ltag = thread;
	}
	if (pre != NULL && pre->right == NULL)
	{
		pre->rtag = thread;
		pre->right = node;
	}
	pre = node;

		in_cueing(node->right);
}

void pre_traversal(bi_node* node)//前序遍历线索二叉树
{
	while (node)
	{
		cout << node->sign;
		if (node->rtag == thread)//优先通过线索进入后继节点，不行再按递归顺序进行
			node = node->right;
		else if (node->left != NULL&&node->ltag!=thread)//务必不可忽略后半部分的条件！否则会在最后两个节点陷入死循环！可以把后半部分删掉试试；
			node = node->left;
		else
			node = node->right;  
	}
}
void in_traversal(bi_node* node)
{
	while (node)
	{
		while (node->left != NULL&&node->ltag==link)//node->left如非NULL，则既可能左孩子，也可能是左线索，如果是左孩子，则进入while
			node = node->left;     //一直向左下遍历，直到碰见第一个没有左孩子的节点（中序排第一）
		cout << node->sign;
		while (node->rtag == thread )//如果有有线索，直接跳到有线索指向的节点，并循环此步，直到没有右线索
		{
			node = node->right;
			cout << node->sign;
		}
		node = node->right;//否则，按照中序遍历的规律，找其右子树中最左下的结点，也就是继续循环遍历
	}
	//上面理解比较复杂，务必画图辅助理解！！！画一个特殊点的图，然后一步一步解决问题，就基本可行了；
}
void pre_display(bi_node* node)
{
	if (node == NULL)
		return;
	cout << node->sign;
	pre_display(node->left);
	pre_display(node->right);
}
void in_display(bi_node* node)
{
	if (node == NULL)
		return;
	in_display(node->left);
	cout << node->sign;
	in_display(node->right);
}
void post_display(bi_node* node)
{
	if (node == NULL)
		return;
	post_display(node->left);
	post_display(node->right);
	cout << node->sign;
}