Data Structure - Tree codebase

Traversal of trees

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct BiTNode
{
	int data;
	struct BiTNode*lchild, *rchild;
 };
typedef struct BiTNode BiTNode;
typedef struct BiTNode* BiTree;

void preOrder(BiTNode*root)
{
	if (root == NULL)
	{
		return;
	}
	printf("%d", root->data);
	preOrder(root->lchild);
	preOrder(root->rchild);

}
void inOrder(BiTNode *root)
{
	if (root == NULL)
	{
		return;
	}
	preOrder(root->lchild);
	printf("%d", root->data);
	preOrder(root->rchild);
}
void postOrder(BiTNode *root)
{
	if (root == NULL)
	{
		return;
	}
	preOrder(root->lchild);
	preOrder(root->rchild);
	printf("%d", root->data);
}
void main()
{
	BiTNode t1, t2, t3, t4, t5;
	memset(&t1, 0, sizeof(BiTNode));
	memset(&t2, 0, sizeof(BiTNode));
	memset(&t3, 0, sizeof(BiTNode));
	memset(&t4, 0, sizeof(BiTNode));
	memset(&t5, 0, sizeof(BiTNode));
	t1.data = 1;
	t2.data = 2;
	t3.data = 3;
	t4.data = 4;
	t5.data = 5;
	t1.lchild = &t2;
	t1.rchild = &t3;
	t2.lchild = &t4;
	t3.lchild = &t5;
	printf("preOrder\n");
	preOrder(&t1);
	printf("inOrder\n");
	inOrder(&t1);
	printf("postOrder\n");
	postOrder(&t1);
	printf("hello...\n");
	system("pause");
	return;
}           

Find the number of leaf nodes

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct BiTNode
{
	int data;
	struct BiTNode*lchild, *rchild;
 };
typedef struct BiTNode BiTNode;
typedef struct BiTNode* BiTree;

void preOrder(BiTNode*root)
{
	if (root == NULL)
	{
		return;
	}
	printf("%d", root->data);
	preOrder(root->lchild);
	preOrder(root->rchild);

}
void inOrder(BiTNode *root)
{
	if (root == NULL)
	{
		return;
	}
	preOrder(root->lchild);
	printf("%d", root->data);
	preOrder(root->rchild);
}
void postOrder(BiTNode *root)
{
	if (root == NULL)
	{
		return;
	}
	preOrder(root->lchild);
	preOrder(root->rchild);
	printf("%d", root->data);
}
int sum;
void  coutLeaf(BiTNode *T,int *sum)//递归里的指针做函数参数
{
	if (T != NULL)
	{
		if (T->lchild == NULL&&T->rchild == NULL)
		{
			(*sum)++;
		}


		if (T->lchild)
		{
			coutLeaf(T->lchild,sum);
		}
		if (T->rchild)
		{
			coutLeaf(T->rchild,sum);
		}
	}
}
void main()
{
	BiTNode t1, t2, t3, t4, t5;
	memset(&t1, 0, sizeof(BiTNode));
	memset(&t2, 0, sizeof(BiTNode));
	memset(&t3, 0, sizeof(BiTNode));
	memset(&t4, 0, sizeof(BiTNode));
	memset(&t5, 0, sizeof(BiTNode));
	t1.data = 1;
	t2.data = 2;
	t3.data = 3;
	t4.data = 4;
	t5.data = 5;
	t1.lchild = &t2;
	t1.rchild = &t3;
	t2.lchild = &t4;
	t3.lchild = &t5;
	{
		int mysum = 0;
		coutLeaf(&t1, &sum);
		printf("sum:%d\n", sum);
	}
	printf("hello...\n");
	system("pause");
	return;
}           

Find the height of the tree

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct BiTNode
{
	int data;
	struct BiTNode*lchild, *rchild;
 };
typedef struct BiTNode BiTNode;
typedef struct BiTNode* BiTree;


void inOrder(BiTNode *root)
{
	if (root == NULL)
	{
		return;
	}
	inOrder(root->lchild);
	printf("%d", root->data);
	inOrder(root->rchild);
}
int  Depth(BiTNode* T)
{
	int deptLeft = 0;
	int deptRight = 0;
	int deptval = 0;
	if (T == NULL)
	{
		deptval = 0;
		return  deptval;
	}
	deptLeft  = Depth(T->lchild);
	deptRight = Depth(T->rchild);
	deptval = 1 + (deptLeft > deptRight ? deptLeft : deptRight);
	return deptval;
}
void main()
{
	BiTNode t1, t2, t3, t4, t5;
	memset(&t1, 0, sizeof(BiTNode));
	memset(&t2, 0, sizeof(BiTNode));
	memset(&t3, 0, sizeof(BiTNode));
	memset(&t4, 0, sizeof(BiTNode));
	memset(&t5, 0, sizeof(BiTNode));
	t1.data = 1;
	t2.data = 2;
	t3.data = 3;
	t4.data = 4;
	t5.data = 5;
	t1.lchild = &t2;
	t1.rchild = &t3;
	t2.lchild = &t4;
	t3.lchild = &t5;

	printf("%d\n", Depth(&t1));
	printf("inOrder\n");
	inOrder(&t1);
	printf("hello...\n");
	system("pause");
	return;
}           

A copy of the tree

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct BiTNode
{
	int data;
	struct BiTNode*lchild, *rchild;
 };
typedef struct BiTNode BiTNode;
typedef struct BiTNode* BiTree;


void inOrder(BiTNode *root)
{
	if (root == NULL)
	{
		return;
	}
	inOrder(root->lchild);
	printf("%d", root->data);
	inOrder(root->rchild);
}
int  Depth(BiTNode* T)
{
	int deptLeft = 0;
	int deptRight = 0;
	int deptval = 0;
	if (T == NULL)
	{
		deptval = 0;
		return  deptval;
	}
	deptLeft  = Depth(T->lchild);
	deptRight = Depth(T->rchild);
	deptval = 1 + (deptLeft > deptRight ? deptLeft : deptRight);
	return deptval;
}
BiTNode *CopyTree(BiTNode* T)
{
	BiTNode *newNode = NULL;
	BiTNode *newLp = NULL;
	BiTNode *newRp = NULL;
	if (T == NULL)//递归结束标志
	{
		return NULL;
	}
	if (T->lchild != NULL)
	{
		newLp = CopyTree(T->lchild);
	}
	else
	{
		newLp = NULL;
	}
	if (T->rchild != NULL)
	{
		newRp = CopyTree(T->rchild);
	}
	else
	{
		newRp = NULL;
	}
	newNode = (BiTNode*)malloc(sizeof(BiTNode));
	if (newNode == NULL)
	{
		return  NULL;
	}
	newNode->lchild = newLp;
	newNode->rchild = newRp;

	newNode->data = T->data;
	return newNode;
}
void main()
{
	BiTNode t1, t2, t3, t4, t5;
	memset(&t1, 0, sizeof(BiTNode));
	memset(&t2, 0, sizeof(BiTNode));
	memset(&t3, 0, sizeof(BiTNode));
	memset(&t4, 0, sizeof(BiTNode));
	memset(&t5, 0, sizeof(BiTNode));
	t1.data = 1;
	t2.data = 2;
	t3.data = 3;
	t4.data = 4;
	t5.data = 5;
	t1.lchild = &t2;
	t1.rchild = &t3;
	t2.lchild = &t4;
	t3.lchild = &t5;

	printf("%d\n", Depth(&t1));
	{
		BiTNode *root = CopyTree(&t1);
		printf("inorder\n");
		inOrder(&t1);
		printf("hello...\n");
	}

	system("pause");
	return;
}           

#法创建树

BiTNode *CreateBiThrTree()
{
	BiTNode *node = NULL;
	BiTNode *pL = NULL;
	BiTNode *pR = NULL;
	char h;
	scanf("%c", &h);
	if (h == '#')
	{
		return NULL;
	}
	else
	{
		node = (BiTNode*)malloc(sizeof(BiTNode));
		memset(node, 0, sizeof(BiTNode));
		node->data = h;
		pL = CreateBiThrTree();
		if (pL != NULL)
		{
			node->lchild = pL;
		}
		else
		{
			node->rchild = NULL;
		}
		pR = CreateBiThrTree();
		if (pR != NULL)
		{
			node->rchild = pR;
		}
		else
		{
			node->rchild = NULL;
		}
	}
	return node;
}           

Binary tree clue

Status  InOrderThreading(BiThrTree *Thrt, BiThrTree T)
{
	*Thrt = (BiThrTree)malloc(sizeof(BiThrNode));
	if (!*Thrt)
		exit(OVERFLOW);
	(*Thrt)->LTag = Link;
	(*Thrt)->RTag = Thread;
	(*Thrt)->rchild = (*Thrt);
	if (!T)
		(*Thrt)->lchild = *Thrt;
	else
	{
		(*Thrt)->lchild = T;
		pre = (*Thrt);
		InThreading(T);
		pre->rchild = *Thrt;
		pre->RTag = Thread;
		(*Thrt)->rchild = pre;
	}
	return OK;

	
}
Status InOrderTraverse_Thr(BiThrTree T)
{
	BiThrTree p;
	p = T->lchild;
	while (p != T)
	{
		while(p->LTag==Link)
			p=p->lchild;
		if (!visit(p->data))
			return ERROP;
		while (p->RTag == Thread&&p->rchild != T)
		{
			p = p->rchild;
			visit(p->data);
		}
		p = p->rchild;
	}
	return OK;
}
Status InOrderTraverse_Thr(  BiThrTree T)
{
	BiThrTree p;
	p = T->lchild;
	while (p != T)
	{
		p = p->rchild;
	}
	return OK;
}