2023 Wangdao C language training camp (clue binary tree)

Clue binary tree

( It is absolutely impossible to solve a big problem , It is of no use in industry )
When the left child pointer or right child pointer of a node is empty , The clue binary tree is to prevent the left and right child pointers of the node from being empty

The header file

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

Structure

typedef char ElemType;
typedef struct ThreadNode {
    
	ElemType data;
	struct ThreadNode* lchild, * rchild;
	int ltag, rtag;

}ThreadNode,*ThreadTree;

Main function

// Build a clue tree by hand , in total 5 Nodes 
void BulidThreadTree(ThreadTree& T)
{
    
	ThreadTree arr[5];
	int i;
	for (i = 0; i < 5; i++)
	{
    
		arr[i] = (ThreadTree)malloc(sizeof(ThreadNode));
		//memset It's an initialization function , The function is to set all in a block of memory to the specified value .
		memset(arr[i], 0, sizeof(ThreadNode));
		arr[i]->data = 'A' + i;

	}
	arr[0]->lchild = arr[1];
	arr[0]->rchild = arr[2];
	arr[1]->lchild = arr[3];
	arr[2]->lchild = arr[4];
	T = arr[0];
}
void InThread(ThreadTree& p, ThreadTree& pre)
{
    
	if (p != NULL)
	{
    
		//
		InThread(p->lchild, pre);
		if (p->lchild == NULL)// On the left for NULL
		{
    
			p->lchild = pre;
			p->ltag = 1;
		}
		if (pre != NULL && pre->rchild == NULL)
		{
    
			//pre The right child of the node is NULL, Let it point to the successor node 
			pre->rchild = p;
			pre->rtag = 1;
		}
		pre = p;
		InThread(p->rchild, pre);
	}
}
void CreateInThread(ThreadTree T)
{
    
	ThreadTree pre = NULL;// Use auxiliary pointer 
	if (T != NULL)
	{
    

		InThread(T, pre);
		pre->rchild = NULL;
		pre->rtag = 1;
	}
}

// The first node under middle order traversal 
ThreadNode* Firstnode(ThreadNode* p)
{
    
	while (p->ltag == 0)
		p = p->lchild;
	return p;
}

The main function

int main()
{
    
	ThreadTree T;
	ThreadTree p;
	BulidThreadTree(T);
	CreateInThread(T);// Construct a clue binary tree 
	p = Firstnode(T);
	printf(" The value of the leftmost lower node is ：%c\n", p->data);
	system("pause");
}