データ構造:手がかり二叉樹はどうやって前駆と後継を見つけて、どうやって出力を遍歴しますか?

前のブログでは手がかり二叉樹の構造と簡単な再帰的出力方法を紹介しています.
https://blog.csdn.net/hpu2022/article/details/107234190
本文を読むなら、まず前の文章を大体理解してください.
スレッド二叉ツリー定義

typedef struct ThreadNode{
    ElemType data;
    //     ->   、    ->     
    struct ThreadNode *lchild, *rchild; 
    // tag 0    ，tag 1     
	int ltag, rtag;
} ThreadNode, *ThreadTree;

前の記事は出力方法を遍歴しています.この方法は当時自分が思っていた低データ量で大丈夫です.データが多い時が正しいかどうかは確認できませんでした.

//                         
//                 tag == 0？              
void InOrder(ThreadTree T)
{

	if(NULL != T){
		if(0 == T->ltag)
			InOrder(T->lchild); //         
		PrintNode(T);			//       
		if(0 == T->rtag) 
			InOrder(T->rchild); //         
	} 
}

//        
void PrintNode(ThreadNode *node)
{
	if(NULL == node->lchild){
		printf("  ：NULL  ");
	}
	else{
		printf("  ：%d  ", node->lchild->data);
	}
	printf("  ：%d  ", node->data);
	if(NULL == node->rchild){
		printf("  ：NULL
");	
	}
	else{
		printf("  ：%d
", node->rchild->data);
	}
}

以下の方法は、より科学的な方法であり、王道408シリーズのコースで提供される方法である.コメントをよく見る
後継をさがす

//    p      ，            
ThreadNode* FirstNode(ThreadNode *p) 
{
	while(0 == p->ltag){ //           
		p = p->lchild;
	}
	return p;
}

//             p      
ThreadNode *NextNode(ThreadNode *p) 
{
	if(0 == p->rtag){
		//              
		return FirstNode(p->rchild);
	}
	else{
		return p->rchild; // rtag == 1          
	}
}

//               （     ） 
void InOrder(ThreadNode *T) 
{
	for(ThreadNode *p = FirstNode(T); p != NULL; p = NextNode(p)){
		PrintNode(p);
	}
}

前駆者を探して結点する

//    p      ，            
ThreadNode* LastNode(ThreadNode *p)
{
	//          （       ） 
	while(0 == p->rtag){
		p = p->rchild;
	}
	return p; 
}

//            p    
ThreadNode* PreNode(ThreadNode *p)
{ 
	if(p->ltag == 0){
		//             
		return LastNode(p->lchild);
	}
	else{
		return p->lchild;
	}
}

//              
void RevInOrder(ThreadNode *T)
{
	for(ThreadNode *p = LastNode(T); p != NULL; p = PreNode(p)){
		PrintNode(p);
	}
}

コード:

#include 
#include 

#define ElemType int

typedef struct ThreadNode{
    ElemType data;
    //     ->   、    ->     
    struct ThreadNode *lchild, *rchild; 
    // tag 0    ，tag 1     
	int ltag, rtag;
} ThreadNode, *ThreadTree;

ThreadNode *preNode = NULL; //     ，              

//            
void visit(ThreadNode *nowNode)
{
	if(NULL == nowNode->lchild){ //          ，         
		nowNode->lchild = preNode;
		nowNode->ltag = 1;
	}
	 
	if(NULL != preNode && NULL == preNode->rchild){ //             
		preNode->rchild = nowNode;
		preNode->rtag = 1;
	}
	preNode = nowNode; //   ，          
}

//          
void InitThreadTree(ThreadTree &T)
{
	T == NULL;
}

//      
void InThread(ThreadTree T)
{
	if(NULL != T){
		InThread(T->lchild); //         
		visit(T);			//       
		InThread(T->rchild); //         
	}
}

//                
ThreadNode* CreateNode(int data)
{
	struct ThreadNode *node = (ThreadNode *)malloc(sizeof(ThreadNode));
	node->ltag = 0;
	node->rtag = 0;
	node->lchild = NULL;
	node->rchild = NULL;	
	node->data = data; 
	return node;
}

//      
void CreateBiTree(ThreadTree &T) 
{
	//              
	T = CreateNode(1);
	T->lchild = CreateNode(2);
	T->rchild = CreateNode(3);
	T->lchild->lchild = CreateNode(4);
	T->rchild->lchild = CreateNode(5);
}


//          
void CreateInThread(ThreadTree T)
{
	preNode = NULL;
	if(NULL != T){
		InThread(T); //                     
		if(NULL == preNode->rchild){ //               
			preNode->rtag = 1;
		}
	}
}

//        
void PrintNode(ThreadNode *node)
{
	if(NULL == node->lchild){
		printf("  ：NULL  ");
	}
	else{
		printf("  ：%d  ", node->lchild->data);
	}
	printf("  ：%d  ", node->data);
	if(NULL == node->rchild){
		printf("  ：NULL
");	
	}
	else{
		printf("  ：%d
", node->rchild->data);
	}
}

//    p      ，            
ThreadNode* FirstNode(ThreadNode *p) 
{
	while(0 == p->ltag){ //           
		p = p->lchild;
	}
	return p;
}

//             p      
ThreadNode *NextNode(ThreadNode *p) 
{
	if(0 == p->rtag){
		//              
		return FirstNode(p->rchild);
	}
	else{
		return p->rchild; // rtag == 1          
	}
}

//               （     ） 
void InOrder(ThreadNode *T) 
{
	for(ThreadNode *p = FirstNode(T); p != NULL; p = NextNode(p)){
		PrintNode(p);
	}
}

//    p      ，            
ThreadNode* LastNode(ThreadNode *p)
{
	//          （       ） 
	while(0 == p->rtag){
		p = p->rchild;
	}
	return p; 
}

//            p    
ThreadNode* PreNode(ThreadNode *p)
{ 
	if(p->ltag == 0){
		//             
		return LastNode(p->lchild);
	}
	else{
		return p->lchild;
	}
}

//              
void RevInOrder(ThreadNode *T)
{
	for(ThreadNode *p = LastNode(T); p != NULL; p = PreNode(p)){
		PrintNode(p);
	}
}

int main()
{
	ThreadTree T;
	InitThreadTree(T); 
	CreateBiTree(T); //       
	CreateInThread(T); //         
	InOrder(T);	//        
	printf("
");
	RevInOrder(T); 
	
    return 0;
}