(the complete code is at the end of the text and the user manual is attached)

Implemented operations

        1. Tree initialization

        2. Traversal binary tree

Traversing binary tree in sequence (non recursive using stack)

Middle order traversal binary tree (recursion)

Post order traversal trigeminal tree (trigeminal tree)

        3. Calculate the number of nodes

        4. Calculate the number of leaves

        5. Judge whether the binary tree is a small root tree

        6. Decompose the binary tree into roots, left and right

        7. Replace left subtree

        8. Replace right subtree

        9. Find the k-th accessed binary tree

        10. Judge whether there is a node with element x in the binary tree

        11. Judge whether the binary tree is a regular binary tree

        12. The left and right subtrees of each node in the exchange tree

        13. Find the depth of the subtree with x as the root node

        14. Find the number of branch nodes in the tree

        15. Judge whether two binary trees are similar

        16. Destroy binary tree

        17. Separate left subtree

        18. Separating right subtree

pedagogical operation

        

1. Tree initialization:

Before running all programs, you need to complete the initialization of the tree. Enter a string in the order of first traversal, and enter "#" to represent an empty tree. The function converts the string into the corresponding sequence and traverses the tree to get the content. If the input is wrong, it will return the prompt that the error occurs in the first data in the string. If the establishment is completed, the same string is used to complete the establishment of trigeminal tree at the same time.

Test case: 153 ##2###64### (must be entered in order and the empty tree is' # ')

        2. Traversal binary tree

After selecting this option, the user enters the traversal function. If the tree does not exist, the output prompt tree is not established. In the traversal function, the user performs traversal in different orders by selecting the corresponding options. The options provided are pre order traversal, medium order traversal, and post order traversal. Among them, the first order traversal adopts the non recursive method using stack, the middle order traversal adopts the recursive method, and the subsequent traversal adopts the trigeminal tree method.

        3. Calculate the number of nodes

After the user selects this function, the number of nodes in the tree will be returned. If the tree does not exist, the output prompt tree is not established.

        4. Computed leaf subtree

After the user selects this function, the number of leaves of the tree is returned. If the tree does not exist, the output prompt tree is not established.

        5. Judge whether the binary tree has no small root binary tree

After the user selects this function, the output determines whether the current tree is a small root binary tree. The definition of small root binary tree is that the data value in any node is less than the data value in its left and right subtrees. If the tree does not exist, the output prompt tree is not established.

        6. Decompose the binary tree into three trees: root, left and right

After the user selects the function, the tree is decomposed into three sub trees: root tree, left sub tree and right sub tree, and the three sub trees are output in the order of precedence. If the tree does not exist, the output prompt tree is not established.

        7. Replace left subtree

After the user selects the function, first enter the string in the order of precedence to establish a new replacement tree. If the establishment fails, a prompt will be returned. After the creation is completed, the function replaces the left subtree of the current tree with the input new tree. The replacement is complete. If the tree does not exist, the output prompt tree is not established.

        8. Replace right subtree

After the user selects the function, first enter the string in the order of precedence to establish a new replacement tree. If the establishment fails, a prompt will be returned. After the creation is completed, the function replaces the right subtree of the current tree with the input new tree. The replacement is complete. If the tree does not exist, the output prompt tree is not established.

        9. Find the k-th accessed node of the binary tree

After the user selects the function, enter K, indicating that he wants to view the k-th accessed node. The function returns the k-th accessed node. If K exceeds the node range of the tree, it returns "#" indicating null. If the tree does not exist, the output prompt tree is not established.

        10. Judge whether there is a node with element x in the binary tree

After the user selects the function, enter x to indicate the node value to be searched. The function returns a prompt whether the node exists. If the tree does not exist, the output prompt tree is not established.

       

        11. The left and right subtrees of each node in the exchange tree

After the user selects the function, the left and right subtrees of each node in the function exchange book are exchanged, and the exchanged trees are output in order.

        12. Judge whether the binary tree is a regular binary tree

After the user selects the function, the function returns to judge whether the tree is a regular binary tree. Regular binary tree is defined as: the number of nodes with degree 1 is 0. If the tree does not exist, the output prompt tree is not established.

       

        13. Find the depth of the subtree with x as the root node

After the user selects this function, enter the value x of the desired search depth, and the function returns the depth of the subtree with X as the root node. If the target node is not found, a prompt is returned that the value with X as the node does not exist. If the tree does not exist, the output prompt tree is not established.

        14. Find the number of branch nodes in the tree

After the user selects this function, the function returns the number of branch nodes in the tree. If the tree does not exist, the output prompt tree is not established.

        15. Judge whether the two trees are similar

After the user selects the function, enter the tree (string) that you want to compare with the current tree, and the function generates the corresponding binary tree. If the generation fails, a failure prompt is returned. Then compare the similarity of the two trees. Similar definitions have the same structure and different values. If the tree does not exist, the output prompt tree is not established.

       

        16. Destroy binary tree

After the user selects this function, the current tree will be destroyed. If the tree does not exist, the output prompt tree is not established.

        17. Separate left subtree

After the user selects the function, the function separates the left subtree of the original tree from the original tree, and outputs the separated original tree and the separated left subtree. If the tree does not exist, the output prompt tree is not established.

        18. Separating right subtree

After the user selects the function, the function separates the right subtree of the original tree from the original tree, and outputs the separated original tree and the separated right subtree. If the tree does not exist, the output prompt tree is not established.

Macro definition

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -1
typedef int Status;		    //Used as the return type of the function, indicating the result status of the function 
typedef char TElemType;		//It is assumed that the element type of binary tree node is character

Binary tree chain structure

typedef struct BiTNode 
{
	TElemType data;
	BiTNode* lchild, * rchild;
} BiTNode, * BiTree;

Trident tree chain structure

typedef struct TriTNode 
{
	int mark;
	TElemType data;
	TriTNode* parent, * lchild, * rchild;
}TriTNode, * TriTree;

Auxiliary stack

typedef struct BSNode
{
	BiTree data;
	struct BSNode* next;
}BSNode, *BStack;

Initialization stack

void InitStack(BStack& s)
{
	s = NULL;
}

Push

Status Push_BS(BStack& s, BiTree e)
{
	BSNode* p;
	p = (BSNode*)malloc(sizeof(BSNode));
	if (p == NULL)return OVERFLOW;
	p->data = e;
	p->next = s;
	s = p;
	return OK;
}

Out of stack

Status Pop_Bs(BStack& s, BiTree& e)
{
	BSNode* p;
	if (s == NULL)return ERROR;
	p = s;
	e = s->data;
	s = s->next;
	free(p);
	return OK;
}

Stack empty judgment

Status StackEmpty_BS(BStack s)
{
	if (s == NULL)return TRUE;
	else return FALSE;
}

Auxiliary function 1: access the value of the node

Status visit(TElemType e)
{
	if (e)
	{
		printf("%c", e);
		return OK;
	}
	else return ERROR;
}

Auxiliary function 2: it is used to find the value of the k-th accessed node in the pre sequence pass time of binary tree T

TElemType visitsPreOrderK(BiTree T, Status& i, Status k)
{
	TElemType p = '#';
	if (T == NULL)return '#';
	if (i == k)return T->data;
	i++;
	if (T->lchild)
		p = visitsPreOrderK(T->lchild, i, k);
	if (T->rchild && p == '#')
		p = visitsPreOrderK(T->rchild, i, k);
	return p;
}

Auxiliary function 3: the depth of the subtree whose root is the node whose auxiliary evaluation is x

Status depth(BiTree T)
{
	int depl, depr;
	if (T == NULL)return 0;
	else
	{
		depl = depth(T->lchild);
		depr = depth(T->rchild);
		return 1 + (depl > depr ? depl : depr);
	}
}

Create Trident tree

TriTree CreateTriTree(TElemType* tree, Status& i)
{
	TriTree T;
	TElemType node = tree[i++];
	if (node=='#')
	{
		T = NULL; //T is an empty tree
	}
	else 
	{
		T = (TriTree)malloc(sizeof(TriTNode));
		if (T == NULL)
			return NULL;
		T->data = node;
		T->mark = 0;
		T->parent = NULL;
		T->lchild = CreateTriTree(tree, i); //Build left subtree
		if (T->lchild != NULL)
		{
			T->lchild->parent = T;
		}   //If the left subtree exists, assign its parent value
		T->rchild = CreateTriTree(tree, i); //Constructing right subtree
		if (T->rchild != NULL)
		{
			T->rchild->parent = T;      //If the right subtree exists, assign its parent value
		}
	}
	return T;
}

Tree initialization

//Create binary tree and initialize
Status InitBiTree(BiTree& T) 
{
	T = NULL;
	return OK;
}

Create binary tree

BiTree MakeBiTree(TElemType e, BiTree L, BiTree R)
{
	BiTree T;
	T = (BiTNode*)malloc(sizeof(BiTNode));
	if (T==NULL) 
	{
		return NULL;
}
T->data = e;
	T->lchild = L;
	T->rchild = R;
	return T;
}

Construction of binary tree by preorder

BiTree CreateBiTree(TElemType* T, Status& i, Status&tag)
{
	BiTree temp;
	TElemType ch;
	int len;
	len = strlen(T);
	ch = T[i++];
	if (i>len)
	{
		tag = 0;
		printf("The first%d Data entry error or does not exist, please re-enter\n",i);
		temp = NULL;
		return ERROR;
	}
	else if ('#' == ch)InitBiTree(temp);// Create an empty tree
	else
	{
		temp = MakeBiTree(ch, NULL, NULL);
		temp->lchild = CreateBiTree(T, i,tag);
		temp->rchild = CreateBiTree(T, i,tag);
	}
	return temp;
}

Traversal binary tree

Traversing binary tree in sequence (non recursive using stack)

Status PreOrderTraverse(BiTree T, Status(*visit)(TElemType e))
{
	BStack s;
	InitStack(s);
	BiTree p = T;
	while (p != NULL || !StackEmpty_BS(s))
	{
		if (p != NULL)
		{
			visit(p->data);
			Push_BS(s, p);
			p = p->lchild;
		}
		else
		{
			Pop_Bs(s, p);
			p = p->rchild;
		}
	}
	return OK;
}

Middle order traversal binary tree (recursion)

void InOrderTraverse(BiTree T)
{
	if (T)
	{
		InOrderTraverse(T->lchild);       //Preorder traversal of left subtree
		printf("%c", T->data);              //Access root node
		InOrderTraverse(T->rchild);       //Preorder traversal right subtree
	}
}

Postorder traversal trigeminal tree

void PostOrder(TriTree bt, Status(*visit)(TElemType e))
{
	TriTree p = bt;
	// visit(p->data);
	while (p) {
		while (p->mark == 0) {  //First traverse the left child
			p->mark = 1;
			if (p->lchild)
				p = p->lchild;
		}
		while (p->mark == 1) {  //Then traverse the right child
			p->mark = 2;
			if (p->rchild)
				p = p->rchild;
		}
		if (p->mark == 2) {
			visit(p->data);
			p = p->parent;
		}
	}
}

Destroy binary tree

void DestroyBiTree(BiTree& T)
{
	if (T == NULL)return;
	else
	{
		DestroyBiTree(T->lchild);
		DestroyBiTree(T->rchild);
		free(T);
		T = NULL;
	}
}

If the binary tree is empty, return true; otherwise, return FALSE

Status BiTreeEmpty(BiTree T)
{
	if (T == NULL)
	{
		return TRUE;
	}
	else
	{
		return FALSE;
	}
}

A binary tree is divided into three parts: root, left subtree and right subtree

Status BreakBiTree(BiTree& T)
{
	BiTree L, R;
	if (T == NULL)return ERROR;
	else
	{
		L = T->lchild;
		R = T->rchild;
		T->lchild = NULL;
		T->rchild = NULL;
		printf("The root node is (priority):");
		PreOrderTraverse(T,visit);
		printf("\n");
		printf("The left subtree is (first order):");
		PreOrderTraverse(L, visit);
		printf("\n");
		printf("The right subtree is (first order):");
		PreOrderTraverse(R, visit);
		printf("\n");
		return OK;
	}
}

Separate left subtree

Status Breakleft(BiTree& T)
{
	BiTree l;
	if (T == NULL)return ERROR;
	l = T->lchild;
	T->lchild=NULL;
	printf("The separated left subtree is(Preorder): ");
	PreOrderTraverse(l, visit);
	printf("\n");
	printf("The original tree after separation is(Preorder):");
	PreOrderTraverse(T, visit);
	return OK;
}

Separating right subtree

Status Breakright(BiTree& T)
{
	BiTree r;
	if (T == NULL)return ERROR;
	r = T->rchild;
	T->rchild = NULL;
	printf("The separated right subtree is(Preorder): ");
	PreOrderTraverse(r, visit);
	printf("\n");
	printf("The original tree after separation is(Preorder):");
	PreOrderTraverse(T, visit);
	return OK;
}

Replace the left subtree. If t is not empty, replace the left subtree of T with LT, and return the original left subtree of T with Lt

Status ReplaceLeft(BiTree& T, BiTree& LT)
{
	BiTree temp;
	if (T == NULL)return ERROR;
	temp = T->lchild;
	T->lchild = LT;
	LT = temp;
	return OK;
}

Replace the right subtree. If t is not empty, replace the right subtree of T with RT, and return the original right subtree of T with RT

Status ReplaceRight(BiTree& T, BiTree& RT)
{
	BiTree temp;
	if (T == NULL)return ERROR;
	temp = T->rchild;
	T->rchild = RT;
	RT = temp;
	return OK;
}

Recursive algorithm to find the value of the k-th visited node of the binary tree T

TElemType PreOrderK(BiTree T, Status k)
{
	int x = 1;
	return visitsPreOrderK(T, x, k);
}

Find the number of leaves of a binary tree

Status Leaves(BiTree T)
{
	if (T == NULL)return 0;
	else
	{
		if (T->lchild == NULL && T->rchild == NULL)return 1;
		else
			return Leaves(T->lchild) + Leaves(T->rchild);
	}
}

Knot count

Status Node(BiTree T,int& num)
{
	if (T)
	{
		num++;
		Node(T->lchild, num);
		Node(T->rchild, num);
	}
	else return ERROR;
	return OK;
}

Judge whether it is a small root binary tree, and return true

Status SmallBiTree(BiTree T)
{  
	int l, r;
	int cur;
	if (T == NULL)return TRUE;
	if (T->lchild != NULL && T->rchild != NULL)
	{

		if (T->data <= T->lchild->data && T->data <= T->rchild->data)
		{
			l = SmallBiTree(T->lchild);
			r = SmallBiTree(T->rchild);
			cur = l & r;
		}
		else cur = 0;
		return cur;
	}
	if (T->lchild == NULL && T->rchild != NULL)
	{
		if (T->data <= T->rchild->data)
		{
			r = SmallBiTree(T->rchild);
			cur = r;
		}
		else
			cur = 0;
		return cur;
	}
	if (T->rchild == NULL && T->lchild != NULL)
	{
		if (T->data <= T->lchild->data)
		{
			l = SmallBiTree(T->lchild);
			cur = l;
		}
		else
			cur = 0;
		return cur;
	}
	if (T->lchild == NULL && T->rchild == NULL)
	{
		return TRUE;
	}
}

Judge whether there is a node with element x in the binary tree. If yes, return ok

Status SearchX(BiTree T, TElemType x)
{ 
	if (T == NULL)return ERROR;
	else
	{
		if (T->data == x)return OK;
		else
		{
			return SearchX(T->lchild, x) | SearchX(T->rchild, x);
		}
	}
}

Judge whether the binary tree is a regular binary tree (the number of nodes with degree 1 is 0)

Status RegularBiTree(BiTree T)
{ 
	if (T == NULL)return TRUE;
	else
	{
		if (T->lchild == NULL && T->rchild == NULL)
		{
			return TRUE;
		}
		else if (T->lchild != NULL && T->rchild != NULL)
		{
			int l, r;
			l = RegularBiTree(T->lchild);
			r = RegularBiTree(T->rchild);
			return l & r;
		}
		else
			return ERROR;
	}
}

Exchange left and right subtrees of all nodes

void ExchangeSubTree(BiTree& T)
{
	if (T == NULL)return;
	BiTree l, r;
	l = T->lchild;
	r = T->rchild;
	T->lchild = r;
	T->rchild = l;
	ExchangeSubTree(T->rchild);
	ExchangeSubTree(T->lchild);
}

Find the depth of the subtree of the node with x as the root

Status Depthx(BiTree T, TElemType x)
{
	int depth(BiTree T);
	int d;
	if (T == NULL)return ERROR;
	if (T->data != x)
	{
		int l, r;
		l = Depthx(T->lchild, x);
		r = Depthx(T->rchild, x);
		d = l > r ? l : r;
		return d;
	}
	else
	{
		return depth(T);
	}

}

Find the number of branch nodes in the tree

Status BranchNodes(BiTree T)
{
	if (T == NULL)return 0;
	else
	{
		if (T->lchild != NULL || T->rchild != NULL)
		{
			return 1 + BranchNodes(T->lchild) + BranchNodes(T->rchild);
		}
		if (T->rchild == NULL && T->lchild == NULL)
		{
			return 0;
		}
	}
}

Judge whether two binary trees are similar

Status Similar(BiTree T1, BiTree T2)
{  
	if (T1 == NULL && T2 == NULL)return TRUE;
	else if (T1 == NULL && T2 != NULL)return FALSE;
	else if (T1 != NULL && T2 == NULL)return FALSE;
	else
	{
		if (Similar(T1->lchild, T2->lchild) == TRUE && Similar(T1->rchild, T2->rchild) == TRUE)return TRUE;
		else return FALSE;
	}
}

Complete code

mian.c

#include"head.h"

int main(void)
{
	BiTree T = NULL;
	TriTree triTree = NULL;
	TriTree triTree_temp = NULL;
	int tag;
	int i, count;
	int num;
	char sel;
	char tree[50];  //Storage binary tree
	int flag = 1;
	while (flag)
	{
		system("cls");
		printf(" -------------------------------------------------\n");
		printf("|        0. Tree initialization                           |\n");
		printf("|        1. Traversal binary tree                           |\n");
		printf("|        2. Calculate the number of nodes                         |\n");
		printf("|        3. Calculate the number of leaves                           |\n");
		printf("|        4. Judge whether the binary tree is a small root tree               |\n");
		printf("|        5. Decompose the binary tree into roots, left and right             |\n");
		printf("|        6. Replace left subtree                           |\n");
		printf("|        7. Replace right subtree                           |\n");
		printf("|        8. Find the second binary tree k Accessed nodes            |\n");
		printf("|        9. Determine whether there are elements in the binary tree x Node of    |\n");
		printf("|        10.Judge whether the binary tree is a regular binary tree           |\n");
		printf("|        11.The left and right subtrees of each node in the exchange tree           |\n");
		printf("|        12.Beg for x Is the depth of the subtree of the root node            |\n");
		printf("|        13.Finding the number of branch nodes in a binary tree                 |\n");
		printf("|        14.Judge whether two binary trees are similar               |\n");
		printf("|        15.Destroy binary tree                           |\n");
		printf("|        16.Separate left subtree                           |\n");
		printf("|        17.Separating right subtree                           |\n");
		printf("|        18.sign out                                 |\n");
		printf(" -------------------------------------------------\n");
		printf("\n Please at 0-16 If multiple selections are entered at one time, the first selection will be executed\n");
		printf("Please enter the sequence number of the operation command you want to execute:");
		scanf("%d", &num);
		getchar();
		switch (num)
		{
		//Create tree
		case 0:
			tag = 1;
			i = 0;
			printf("Please enter the binary tree in the preorder traversal format('#’Indicates empty tree): ");
			scanf("%s", tree);
			T = CreateBiTree(tree, i,tag);
			if (tag == 0)
			{
				printf("Tree input error, creation failed\n");
				break;
			}
			i = 0;
			triTree = CreateTriTree(tree, i);//Used when traversing the post order trigeminal linked list
			printf("Tree created successfully\n");
			printf("Tree creation is complete");
			flag = 1;
			break;

		//Traversal tree
		case 1:
			if (T == NULL)
			{
				printf("The tree has not been created");
			}
			else
			{
				printf("a.Preorder traversal    b.Medium order traversal  c.Postorder traversal:");
				scanf("%c", &sel);
				getchar();
				switch (sel)
				{
				case 'a'://Preorder traversal 
					PreOrderTraverse(T, visit);
					break;
				case 'b'://Medium order traversal
					InOrderTraverse(T);
					break;
				case 'c'://Postorder traversal
					i = 0;
					triTree_temp = CreateTriTree(tree, i);//After each post order traversal, the mark is modified, so it needs to be redefined
					PostOrder(triTree_temp, visit);//Postorder traversal
					break;
				default:
					printf("\n Please enter the correct serial number");
					break;
				}
			}
			break;

		//Calculate node number
		case 2:
			count = 0;
			Node(T, count);
			printf("\n The nodes of the tree are:%d individual", count);
			break;

		//Calculate the number of leaves
		case 3:
			count = 0;
			count = Leaves(T);
			printf("\n The leaves of the tree are:%d individual",count);
			break;

		//Judge whether binary trees are small root binary trees
		case 4:
			if (T == NULL)printf("The tree has not been established");
			else
			{
				if (SmallBiTree(T) == TRUE)printf("\n The current binary tree is a small root binary tree\n");
				else printf("\n The current binary tree is not a small root binary tree\n");
			}
			break;
		//The binary tree is divided into three parts: left, right and root
		case 5:
			if (T == NULL)printf("The tree has not been established");
			else
			{
				BreakBiTree(T);
			}
			break;

		//Replace left subtree
		case 6:
			if (T == NULL)printf("The tree has not been established");
			else
			{
				BiTree l;
				char lchar[50];
				int temp = 0;
				tag = 1;
				printf("\n Please enter the left subtree you want to replace:");
				scanf("%s", lchar);
				l = CreateBiTree(lchar, temp,tag);
				if (tag == 0)
				{
					printf("\n Tree input error, creation failed\n");
					break;
				}
				ReplaceLeft(T, l);
				printf("The replaced tree is:");
				PreOrderTraverse(T, visit);
			}
			break;

		//Replace right subtree
		case 7:
			if (T == NULL)printf("The tree has not been established");
			else
			{
				BiTree r;
				char rchar[50];
				int temp = 0;
				tag = 1;
				printf("\n Please enter the left subtree you want to replace:");
				scanf("%s", rchar);
				r = CreateBiTree(rchar, temp,tag);
				if (tag == 0)
				{
					printf("\n Tree input error, creation failed\n");
					break;
				}
				ReplaceRight(T, r);
				printf("The replaced tree is:");
				PreOrderTraverse(T, visit);
			}
			break;

		//The k-th accessed node
		case 8:
			if (T == NULL)printf("The tree has not been established");
			else
			{
				int k;
				char temp;
				printf("\n Which node do you want to view");
				scanf("%d", &k);
				getchar();
				temp=PreOrderK(T, k);
				printf("\n The first%d The accessed nodes are:%c", k,temp);
			}
			break;
		
		//Judge whether there is a node with element x in the binary tree
		case 9:
			if (T == NULL)printf("The tree has not been established");
			else
			{
				char temp;
				int result;
				printf("\n The node data you want to check is:");
				scanf("%c", &temp);
				result=SearchX(T, temp);
				if (result == 1)printf("\n The node does not exist\n");
				else printf("\n The node does not exist\n");
			}
			break;

		//Judge whether the binary tree is a regular binary tree
		case 10:
			if (T == NULL)printf("The tree has not been established");
			else
			{
				int temp;
				temp=RegularBiTree(T);
				if (temp == 1)printf("\n The tree is a regular binary tree\n");
				else printf("\n The tree is not a regular binary tree\n");
			}
			break;

		//The left and right subtrees of each node in the exchange tree
		case 11:
			if (T == NULL)printf("The tree has not been established");
			else 
			{
				ExchangeSubTree(T);
				printf("\n Exchange complete\n");
			}
			break;

		//Find the depth of the subtree with x as the root node
		case 12:
			if (T == NULL)printf("The tree has not been established");
			else
			{
				char temp;
				int dep;
				printf("\n What do you want to ask for the depth of the subtree rooted in:");
				scanf("%c", &temp);
				dep= Depthx(T, temp);
				if (dep == 0)
				{
					printf("with%c The value node does not exist, please re-enter\n",temp);
				}
				else
				{
					printf("\n with%c The depth of the subtree that is the root node is%d", temp, dep);
				}
				
			}
			break;

		//Find the number of branch nodes in the tree 
		case 13:
			if (T == NULL)printf("The tree has not been established");
			else
			{
				int temp;
				temp = BranchNodes(T);
				printf("\n The number of branch nodes in the tree is:%d", temp);
			}
			break;

		//Judge whether the two trees are similar
		case 14:
			if (T == NULL)printf("The tree has not been established");
			else
			{
				BiTree T2;
				char t2[50];
				int temp = 0;
				tag = 1;
				printf("\n Please enter the new tree you want to compare:");
				scanf("%s", t2);
				T2 = CreateBiTree(t2, temp, tag);
				if (tag == 0)
				{
					printf("\n Tree input error, creation failed\n");
					break;
				}
				if (Similar(T, T2) == TRUE)printf("\n The two trees are similar");
				else printf("\n The two trees are not alike");
			}
			break;

		//Destroy binary tree
		case 15:
			if (T == NULL)printf("The tree has not been established");
			else
			{
				DestroyBiTree(T);
				printf("Tree destroyed");
			}
			break;

		//Separate left subtree
		case 16:
			if (T == NULL)printf("The tree has not been established");
			else
			{
				Breakleft(T);
			}
			break;

		//
		case 17:
			if (T == NULL)printf("The tree has not been established");
			else
			{
				Breakright(T);
			}
			break;
		case 18:
			flag = 0;
			printf("Program end");
			break;
		default:
			printf("\n Please enter the correct serial number");
			break;
		}
		printf("\n");
		getchar();
		system("pause");
	}
	return 0;
}

BinaryTree.h

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -1
typedef int Status;		    //Used as the return type of the function, indicating the result status of the function 
typedef char TElemType;		//It is assumed that the element type of binary tree node is character


//Binary tree chain
typedef struct BiTNode 
{
	TElemType data;
	BiTNode* lchild, * rchild;
} BiTNode, * BiTree;

//Trigeminal linked list
typedef struct TriTNode 
{
	int mark;
	TElemType data;
	TriTNode* parent, * lchild, * rchild;
}TriTNode, * TriTree;


//Auxiliary stack
typedef struct BSNode
{
	BiTree data;
	struct BSNode* next;
}BSNode, *BStack;
//Initialization stack
void InitStack(BStack& s)
{
	s = NULL;
}
//Element stack
Status Push_BS(BStack& s, BiTree e)
{
	BSNode* p;
	p = (BSNode*)malloc(sizeof(BSNode));
	if (p == NULL)return OVERFLOW;
	p->data = e;
	p->next = s;
	s = p;
	return OK;
}
//Out of stack
Status Pop_Bs(BStack& s, BiTree& e)
{
	BSNode* p;
	if (s == NULL)return ERROR;
	p = s;
	e = s->data;
	s = s->next;
	free(p);
	return OK;
}
//Judge stack empty
Status StackEmpty_BS(BStack s)
{
	if (s == NULL)return TRUE;
	else return FALSE;
}



//Special 1: value of access node
Status visit(TElemType e)
{
	if (e)
	{
		printf("%c", e);
		return OK;
	}
	else return ERROR;
}
//Special 2 is used to find the value of the k-th accessed node in the pre sequence pass time of binary tree T
TElemType visitsPreOrderK(BiTree T, Status& i, Status k)
{
	TElemType p = '#';
	if (T == NULL)return '#';
	if (i == k)return T->data;
	i++;
	if (T->lchild)
		p = visitsPreOrderK(T->lchild, i, k);
	if (T->rchild && p == '#')
		p = visitsPreOrderK(T->rchild, i, k);
	return p;
}
//Special 3, the depth of the subtree whose auxiliary evaluation is the root of the node x
Status depth(BiTree T)
{
	int depl, depr;
	if (T == NULL)return 0;
	else
	{
		depl = depth(T->lchild);
		depr = depth(T->rchild);
		return 1 + (depl > depr ? depl : depr);
	}
}

//Create Trident tree
TriTree CreateTriTree(TElemType* tree, Status& i)
{
	TriTree T;
	TElemType node = tree[i++];
	if (node=='#')
	{
		T = NULL; //T is an empty tree
	}
	else 
	{
		T = (TriTree)malloc(sizeof(TriTNode));
		if (T == NULL)
			return NULL;
		T->data = node;
		T->mark = 0;
		T->parent = NULL;
		T->lchild = CreateTriTree(tree, i); //Build left subtree
		if (T->lchild != NULL)
		{
			T->lchild->parent = T;
		}   //If the left subtree exists, assign its parent value
		T->rchild = CreateTriTree(tree, i); //Constructing right subtree
		if (T->rchild != NULL)
		{
			T->rchild->parent = T;      //If the right subtree exists, assign its parent value
		}
	}
	return T;
}

//Create binary tree and initialize
Status InitBiTree(BiTree& T) 
{
	T = NULL;
	return OK;
}

//Create a binary tree T, where the values of the root node are e, L and R are the left subtree and the right subtree respectively
BiTree MakeBiTree(TElemType e, BiTree L, BiTree R)
{
	BiTree T;
	T = (BiTNode*)malloc(sizeof(BiTNode));
	if (T==NULL) 
	{
		return NULL;
	}
	T->data = e;
	T->lchild = L;
	T->rchild = R;
	return T;
}

//Construction of binary tree by preorder
BiTree CreateBiTree(TElemType* T, Status& i, Status&tag)
{
	BiTree temp;
	TElemType ch;
	int len;
	len = strlen(T);
	ch = T[i++];
	if (i>len)
	{
		tag = 0;
		printf("The first%d Data entry error or does not exist, please re-enter\n",i);
		temp = NULL;
		return ERROR;
	}
	else if ('#' == ch)InitBiTree(temp);// Create an empty tree
	else
	{
		temp = MakeBiTree(ch, NULL, NULL);
		temp->lchild = CreateBiTree(T, i,tag);
		temp->rchild = CreateBiTree(T, i,tag);
	}
	return temp;
}

//Traversing binary tree in sequence (non recursive using stack)
Status PreOrderTraverse(BiTree T, Status(*visit)(TElemType e))
{
	BStack s;
	InitStack(s);
	BiTree p = T;
	while (p != NULL || !StackEmpty_BS(s))
	{
		if (p != NULL)
		{
			visit(p->data);
			Push_BS(s, p);
			p = p->lchild;
		}
		else
		{
			Pop_Bs(s, p);
			p = p->rchild;
		}
	}
	return OK;
}

//Middle order traversal binary tree (recursion)
void InOrderTraverse(BiTree T)
{
	if (T)
	{
		InOrderTraverse(T->lchild);       //Preorder traversal of left subtree
		printf("%c", T->data);              //Access root node
		InOrderTraverse(T->rchild);       //Preorder traversal right subtree
	}
}

//Post order traversal trigeminal tree (trigeminal tree)
void PostOrder(TriTree bt, Status(*visit)(TElemType e))
{
	TriTree p = bt;
	// visit(p->data);
	while (p) {
		while (p->mark == 0) {  //First traverse the left child
			p->mark = 1;
			if (p->lchild)
				p = p->lchild;
		}
		while (p->mark == 1) {  //Then traverse the right child
			p->mark = 2;
			if (p->rchild)
				p = p->rchild;
		}
		if (p->mark == 2) {
			visit(p->data);
			p = p->parent;
		}
	}
}

//Destroy binary tree
void DestroyBiTree(BiTree& T)
{
	if (T == NULL)return;
	else
	{
		DestroyBiTree(T->lchild);
		DestroyBiTree(T->rchild);
		free(T);
		T = NULL;
	}
}


//If the binary tree is empty, return true; otherwise, return FALSE
Status BiTreeEmpty(BiTree T)
{
	if (T == NULL)
	{
		return TRUE;
	}
	else
	{
		return FALSE;
	}
}

//A binary tree is divided into three parts: root, left subtree and right subtree
Status BreakBiTree(BiTree& T)
{
	BiTree L, R;
	if (T == NULL)return ERROR;
	else
	{
		L = T->lchild;
		R = T->rchild;
		T->lchild = NULL;
		T->rchild = NULL;
		printf("The root node is (priority):");
		PreOrderTraverse(T,visit);
		printf("\n");
		printf("The left subtree is (first order):");
		PreOrderTraverse(L, visit);
		printf("\n");
		printf("The right subtree is (first order):");
		PreOrderTraverse(R, visit);
		printf("\n");
		return OK;
	}
}

//Separate left subtree
Status Breakleft(BiTree& T)
{
	BiTree l;
	if (T == NULL)return ERROR;
	l = T->lchild;
	T->lchild=NULL;
	printf("The separated left subtree is(Preorder): ");
	PreOrderTraverse(l, visit);
	printf("\n");
	printf("The original tree after separation is(Preorder):");
	PreOrderTraverse(T, visit);
	return OK;
}

//Separating right subtree
Status Breakright(BiTree& T)
{
	BiTree r;
	if (T == NULL)return ERROR;
	r = T->rchild;
	T->rchild = NULL;
	printf("The separated right subtree is(Preorder): ");
	PreOrderTraverse(r, visit);
	printf("\n");
	printf("The original tree after separation is(Preorder):");
	PreOrderTraverse(T, visit);
	return OK;
}

//Replace the left subtree. If t is not empty, replace the left subtree of T with LT, and return the original left subtree of T with Lt
Status ReplaceLeft(BiTree& T, BiTree& LT)
{
	BiTree temp;
	if (T == NULL)return ERROR;
	temp = T->lchild;
	T->lchild = LT;
	LT = temp;
	return OK;
}

//Replace the right subtree. If t is not empty, replace the right subtree of T with RT, and return the original right subtree of T with RT
Status ReplaceRight(BiTree& T, BiTree& RT)
{
	BiTree temp;
	if (T == NULL)return ERROR;
	temp = T->rchild;
	T->rchild = RT;
	RT = temp;
	return OK;
}


//Recursive algorithm to find the value of the k-th visited node of the binary tree T
TElemType PreOrderK(BiTree T, Status k)
{
	int x = 1;
	return visitsPreOrderK(T, x, k);
}

//Find the number of leaves of a binary tree
Status Leaves(BiTree T)
{
	if (T == NULL)return 0;
	else
	{
		if (T->lchild == NULL && T->rchild == NULL)return 1;
		else
			return Leaves(T->lchild) + Leaves(T->rchild);
	}
}

//Knot count
Status Node(BiTree T,int& num)
{
	if (T)
	{
		num++;
		Node(T->lchild, num);
		Node(T->rchild, num);
	}
	else return ERROR;
	return OK;
}


//Judge whether it is a small root binary tree, and return true
Status SmallBiTree(BiTree T)
{  
	int l, r;
	int cur;
	if (T == NULL)return TRUE;
	if (T->lchild != NULL && T->rchild != NULL)
	{

		if (T->data <= T->lchild->data && T->data <= T->rchild->data)
		{
			l = SmallBiTree(T->lchild);
			r = SmallBiTree(T->rchild);
			cur = l & r;
		}
		else cur = 0;
		return cur;
	}
	if (T->lchild == NULL && T->rchild != NULL)
	{
		if (T->data <= T->rchild->data)
		{
			r = SmallBiTree(T->rchild);
			cur = r;
		}
		else
			cur = 0;
		return cur;
	}
	if (T->rchild == NULL && T->lchild != NULL)
	{
		if (T->data <= T->lchild->data)
		{
			l = SmallBiTree(T->lchild);
			cur = l;
		}
		else
			cur = 0;
		return cur;
	}
	if (T->lchild == NULL && T->rchild == NULL)
	{
		return TRUE;
	}
}

//Judge whether there is a node with element x in the binary tree. If yes, return ok
Status SearchX(BiTree T, TElemType x)
{ 
	if (T == NULL)return ERROR;
	else
	{
		if (T->data == x)return OK;
		else
		{
			return SearchX(T->lchild, x) | SearchX(T->rchild, x);
		}
	}
}

//Judge whether the binary tree is a regular binary tree (the number of nodes with degree 1 is 0)
Status RegularBiTree(BiTree T)
{ 
	if (T == NULL)return TRUE;
	else
	{
		if (T->lchild == NULL && T->rchild == NULL)
		{
			return TRUE;
		}
		else if (T->lchild != NULL && T->rchild != NULL)
		{
			int l, r;
			l = RegularBiTree(T->lchild);
			r = RegularBiTree(T->rchild);
			return l & r;
		}
		else
			return ERROR;
	}
}

//Exchange left and right subtrees of all nodes
void ExchangeSubTree(BiTree& T)
{
	if (T == NULL)return;
	BiTree l, r;
	l = T->lchild;
	r = T->rchild;
	T->lchild = r;
	T->rchild = l;
	ExchangeSubTree(T->rchild);
	ExchangeSubTree(T->lchild);
}

//Find the depth of the subtree of the node with x as the root
Status Depthx(BiTree T, TElemType x)
{
	int depth(BiTree T);
	int d;
	if (T == NULL)return ERROR;
	if (T->data != x)
	{
		int l, r;
		l = Depthx(T->lchild, x);
		r = Depthx(T->rchild, x);
		d = l > r ? l : r;
		return d;
	}
	else
	{
		return depth(T);
	}

}

//Find the number of branch nodes in the tree
Status BranchNodes(BiTree T)
{
	if (T == NULL)return 0;
	else
	{
		if (T->lchild != NULL || T->rchild != NULL)
		{
			return 1 + BranchNodes(T->lchild) + BranchNodes(T->rchild);
		}
		if (T->rchild == NULL && T->lchild == NULL)
		{
			return 0;
		}
	}
}

//Judge whether two binary trees are similar
Status Similar(BiTree T1, BiTree T2)
{  
	if (T1 == NULL && T2 == NULL)return TRUE;
	else if (T1 == NULL && T2 != NULL)return FALSE;
	else if (T1 != NULL && T2 == NULL)return FALSE;
	else
	{
		if (Similar(T1->lchild, T2->lchild) == TRUE && Similar(T1->rchild, T2->rchild) == TRUE)return TRUE;
		else return FALSE;
	}
}

head.h

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


//Create binary tree
Status InitBiTree(BiTree& T); 

//Create a binary tree T, where the values of the root node are e, L and R are the left subtree and the right subtree respectively
BiTree MakeBiTree(TElemType e, BiTree L, BiTree R);

//Destroy binary tree
void DestroyBiTree(BiTree& T);

//If the binary tree is empty, return true; otherwise, return FALSE
Status BiTreeEmpty(BiTree T);

//A binary tree is divided into three parts: root, left subtree and right subtree
Status BreakBiTree(BiTree& T);

//Separate left subtree
Status Breakleft(BiTree& T);

//Separating right subtree
Status Breakright(BiTree& T);

//Replace the left subtree. If t is not empty, replace the left subtree of T with LT, and return the original left subtree of T with Lt
Status ReplaceLeft(BiTree& T, BiTree& LT);

//Replace the right subtree. If t is not empty, replace the right subtree of T with RT, and return the original right subtree of T with RT
Status ReplaceRight(BiTree& T, BiTree& RT);

//Construction of binary tree by preorder
BiTree CreateBiTree(TElemType* T, Status& i, Status& tag);//defBT is the input array

//Recursive algorithm to find the value of the k-th visited node of the binary tree T
TElemType PreOrderK(BiTree T, Status k);

//Find the number of leaves of a binary tree
Status Leaves(BiTree T);

//Find the node number of binary tree
Status Node(BiTree T, Status& num);

//Judge whether it is a small root binary tree, and return true
Status SmallBiTree(BiTree T);

//Judge whether there is a node with element x in the binary tree. If yes, return ok
Status SearchX(BiTree T, TElemType x);

//Judge whether the binary tree is a regular binary tree (the number of nodes with degree 1 is 0)
Status RegularBiTree(BiTree T);

//Exchange left and right subtrees of all nodes
void ExchangeSubTree(BiTree& T);

//Find the number of branch nodes in the tree
Status BranchNodes(BiTree T);

//Judge whether two binary trees are similar
Status Similar(BiTree T1, BiTree T2);


//Traversing binary tree in sequence (non recursive using stack)
Status PreOrderTraverse(BiTree T);

//Middle order traversal binary tree (recursion)
void InOrderTraverse(TriTree T, Status(*visit)(TElemType e));

//Postorder traversal trigeminal tree
void PostOrder(TriTree bt, Status(*visit)(TElemType e));

//Create Trident tree
TriTree CreateTriTree(TElemType* tree, Status& i);

//Special 1: value of access node
Status visit(TElemType e);
//Special 2 is used to find the value of the k-th accessed node in the pre sequence pass time of binary tree T
TElemType visitsPreOrderK(BiTree T, Status& i, Status k);
//Special 3, the depth of the subtree whose auxiliary evaluation is the root of the node x
Status depth(BiTree T);

Instruction manual:

1. In "tree initialization" (option '0'), enter 153##2###64###

2. Enter '1' to traverse the binary tree

Enter 'a' for preorder traversal

Enter 'b' for middle order traversal

Enter 'c' to traverse the sequence number

3. Enter '2' to calculate nodes

4. Enter '3' to calculate the number of leaves

5. Enter '4' to judge whether the binary tree is a small root tree

6. Enter '5' to decompose the binary tree into roots, left and right

7. Enter '6' to replace the left subtree

After entering the option, enter it in sequence: ab##c## (after 7, it needs to be reinitialized

8. Enter '7' to replace the right subtree

After entering the option, enter it in sequence: a#bc#### (after 8, it needs to be reinitialized)

9. Enter '8' to find the k-th accessed node of the binary tree

After entering the option (running twice in total), enter 2 and 5

10. Enter '9' to judge whether there is a node with element x in the binary tree

After entering the option (two runs in total), enter 4 and 7

11. Enter '10' to judge whether the binary tree is a regular binary tree

12. Enter the left and right subtrees of each node in the '11' exchange tree (after 11, it needs to be reinitialized)

13. Enter '12' to find the depth of the subtree with node x as the root node

After entering the option (two runs in total), enter 1 and 6

14. Enter '13' to find the number of branch nodes in the binary tree

15. Enter '14' to judge whether the two trees are similar

After entering the option, enter: abd##c##fe###

After entering the option, enter 153##2##6#4##

16. Enter '15' to destroy the binary tree (it needs to be reinitialized after 15)

17. Enter '16'

18. Enter '17' to separate the left subtree (it needs to be reinitialized after 18)

19. Enter '18' to separate the right subtree (it needs to be reinitialized after 19)