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

using namespace std;

/*
		1、為什么要線索化二叉樹？
		對(duì)于經(jīng)常需要遍歷或查找結(jié)點(diǎn) 在遍歷所得線性序列中的 前驅(qū)和后繼信息，
		線索化二叉樹查找效率高，不需要設(shè)棧。
		
		2、如何查找前驅(qū)和后繼信息？ 
		當(dāng)二叉樹以二叉鏈表作為存儲(chǔ)結(jié)構(gòu)時(shí)，只能找到結(jié)點(diǎn)的左、右孩子信息，
		而不能直接得到結(jié)點(diǎn)在一序列中的前驅(qū)和后繼信息，前序和后繼信息只有在遍歷的動(dòng)態(tài)過(guò)程中才能得到。 
*/ 



typedef struct treenode{
	char data;
	struct treenode *lchild, *rchild;
	// ltag = 0：lchild指針指向結(jié)點(diǎn)的左孩子 ?ltag = 1：lchild指針指向結(jié)點(diǎn)的前驅(qū) 
	// rtag = 0：rchild指針指向結(jié)點(diǎn)的右孩子 ?rtag = 1：rchild指針指向結(jié)點(diǎn)的后繼 
	int ltag, rtag;
}treenode, *tree; 

void buildtree(tree &t);
void InOrderThreading(tree &thrt, tree t);
void InThreading(tree p);
void InOrderTraverse(tree thrt); 
void InOrderTraverseReverse(tree thrt);

// 先序序列建立二叉樹 
void buildtree(tree &t){
	char ch;
	ch = getchar();
	
	if(ch == '#'){
		t = NULL;
	}
	else{
		t = (treenode *)malloc(sizeof(treenode));
		t->data = ch;
		t->lchild = NULL;
		t->rchild = NULL;
		t->ltag = 0;
		t->rtag = 0;
		
		buildtree(t->lchild);
		buildtree(t->rchild);
	}
}

// 前驅(qū)結(jié)點(diǎn)指針 （全局變量） 
treenode* pre; 

// 中序線索化 
void InOrderThreading(tree &thrt, tree t){
	// 建頭結(jié)點(diǎn) (為頭節(jié)點(diǎn)指針分配存儲(chǔ)空間)
	thrt = (treenode*) malloc(sizeof(treenode));
	thrt->ltag = 0;
	thrt->rtag = 1;
	// 右指針 回指 
	thrt->rchild = thrt;
	if(t == NULL){
		// 二叉樹t 為空，頭節(jié)點(diǎn)的左指針 回指 
		thrt->lchild = thrt;
	} 
	else{
		thrt->lchild = t;
		pre = thrt;
		// 中序遍歷 進(jìn)行 中序線索化 
		InThreading(t);
		// 最后一個(gè)結(jié)點(diǎn) 線索化
		pre->rchild = thrt;
		pre->rtag = 1;
		thrt->rchild = pre; 
	}
}

// 中序遍歷 進(jìn)行中序線索化
void InThreading(tree p){
	// 結(jié)點(diǎn) 非空 
	if(p){
		// 向左延申 找中序遍歷的第一個(gè)結(jié)點(diǎn) 
		InThreading(p->lchild); // 左子樹線索化 
		
		if(p->lchild == NULL){ // 當(dāng)前結(jié)點(diǎn) 左孩子 為空 
			p->ltag = 1;
			// 將 左孩子指針 指向 中序遍歷時(shí)的 前驅(qū)結(jié)點(diǎn) 
			p->lchild = pre;
		} 
		
		if(pre->rchild == NULL){ // 前驅(qū)結(jié)點(diǎn) 右孩子 為空 
			pre->rtag = 1;
			// 將 前驅(qū)結(jié)點(diǎn)的右孩子指針 指向 當(dāng)前結(jié)點(diǎn) 
			pre->rchild = p; ?
		}
		// 更新前驅(qū)結(jié)點(diǎn) 
		pre = p;
		
		InThreading(p->rchild); // 右子樹線索化 
	}
} 


// p->rtag = 1：右指針是線索,其后繼為 右孩子 
// p->rtag = 0：該結(jié)點(diǎn)有右孩子，則其后繼為 右子樹最左下結(jié)點(diǎn)
// 中序線索二叉樹的遍歷
void InOrderTraverse(tree thrt){
	// p 指向原二叉樹的根結(jié)點(diǎn) 
	treenode* p = thrt->lchild;
	while(p != thrt){
		// 第一次 while 循環(huán)：找到 中序遍歷的第一個(gè)結(jié)點(diǎn) 
		// 后面每一次 while 循環(huán)：找到 右子樹最左下結(jié)點(diǎn) 
		while(p->ltag == 0){
			p = p->lchild;
		}
		// 訪問第一個(gè)結(jié)點(diǎn) 
		printf("%c	", p->data);
		// 右標(biāo)志為 1，可直接得到 后繼結(jié)點(diǎn) 
		while(p->rtag == 1 && p->rchild != thrt){
			p = p->rchild;
			printf("%c	", p->data);
		}
		// while循環(huán)結(jié)束，p->rtag = 0;
		// 右標(biāo)志為 0，則 后繼為 右子樹最左下角結(jié)點(diǎn) 
		// 右標(biāo)志為 0，將 p指針 指向 p的右孩子 ?
		p = p->rchild;
	} 
} 

// p->ltag = 1：左指針是線索,其前序?yàn)?左孩子 
// p->ltag = 0：該結(jié)點(diǎn)有左孩子，則其前驅(qū)為 左子樹最右下結(jié)點(diǎn)
// 逆序遍歷中序線索二叉樹 
void InOrderTraverseReverse(tree thrt){
	treenode* p = thrt->lchild;
	while(p != thrt){
		// 第一次 while 循環(huán)：查找中序遍歷的最后一個(gè)結(jié)點(diǎn) 
		// 后面每一次 while 循環(huán)：找到左子樹最右下結(jié)點(diǎn) 
		while(p->rtag == 0){
			p = p->rchild;
		}
		// 訪問最后一個(gè)結(jié)點(diǎn) 
		printf("%c	", p->data);
		while(p->ltag == 1 && p->lchild != thrt){
			p = p->lchild;
			printf("%c	", p->data);
		}
		p = p->lchild;
	}
	printf("\n");
}

int main(){
	
	tree t;
	tree thrt;
	// 先序序列：FECA#B##D###HG##I##
	buildtree(t);
	// 中序線索化 
	InOrderThreading(thrt, t);
	
	// 中序線索二叉樹的遍歷：A B C D E F G H I ?
	InOrderTraverse(thrt); 
	printf("\n"); 
	// 逆序遍歷中序線索二叉樹：I H G F E D C B A 
	InOrderTraverseReverse(thrt);
	/*
				F
			E		H
		 C ? ? ? ?G ? ?I
	 ?A ? ?D
	 ? ?B
	*/
	return 0;
}