Leecode 第100题 ：相同的树 C语言完整版

#include 
#include 

#define true		1
#define false		0

typedef int bool;

typedef struct Node {
	char data;
	struct Node* Lchild, * Rchild;
}BTnode, * BTree;


int CreatBTree(BTree* T)
{
	char ch;
	scanf_s("%c", &ch,1);
	if (ch == '#')
		*T = NULL;
	else
	{
		*T = (BTree)malloc(sizeof(BTnode));
		//printf("size of node is :%d", sizeof(BTnode));
		if (*T == NULL)
		{
			printf("内存申请失败n");
			return 0;
		}
		(*T)->data = ch;
		//printf("&(*T) address is:%xn", &(*T));
		//printf("&(*T) address is:%xn", &(*T)->Lchild);
		CreatBTree(&(*T)->Lchild);
		CreatBTree(&(*T)->Rchild);
	}
	return 1;
}

void DestoryBTree(BTree* T)
{
	if (*T)
	{
		if ((*T)->Lchild)
		{
			DestoryBTree(&(*T)->Lchild);
		}
		if ((*T)->Rchild)
		{
			DestoryBTree(&(*T)->Rchild);
		}
		free(*T);
		*T = NULL;
	}
}


void PreOrderTraverse(BTree T)
{
	if (T)
	{
		printf("%-5c", T->data);
		PreOrderTraverse(T->Lchild);
		PreOrderTraverse(T->Rchild);
	}
}


void InOrderTraverse(BTree T)
{
	if (T)
	{
		InOrderTraverse(T->Lchild);
		printf("%-5c", T->data);
		InOrderTraverse(T->Rchild);
	}
}


void PostOrderTraverse(BTree T)
{
	if (T)
	{
		PostOrderTraverse(T->Lchild);
		PostOrderTraverse(T->Rchild);
		printf("%-5c", T->data);
	}
}


void DeLeftChild(BTree* T)
{
	if (*T)
		DestoryBTree(&(*T)->Lchild);
}


void DeRightChild(BTree* T)
{
	if (*T)
		DestoryBTree(&(*T)->Rchild);
}


int MaxDepth(BTree T)
{
	if (T == 0)
		return 0;
	else {
		int maxLeft = MaxDepth(T->Lchild);
		int maxRight = MaxDepth(T->Rchild);
		if (maxLeft > maxRight)
			return 1 + maxLeft;
		else
			return 1 + maxRight;
	}
}


int NodeCount(BTree T)
{
	if (T == 0)
		return 0;
	else
	{
		return NodeCount(T->Lchild) + NodeCount(T->Rchild) + 1;
	}
}


int Out1_Count(BTree T)
{
	if (T == NULL)
		return 0;
	else
	{
		if ((T->Lchild == NULL && T->Rchild != NULL) || (T->Lchild != NULL && T->Rchild == NULL))
			return Out1_Count(T->Lchild) + Out1_Count(T->Rchild) + 1;
		else
			return Out1_Count(T->Lchild) + Out1_Count(T->Rchild);
	}
}


int Leaf_Count(BTree T)
{
	if (T == NULL)
		return 0;
	else if ((T->Lchild == NULL) && (T->Rchild == NULL))
		return 1;
	else
		return Leaf_Count(T->Lchild) + Leaf_Count(T->Rchild);
}


int ExchangeTree(BTree* T)
{
	BTree temp;
	if (*T == NULL)
		return 0;
	else
	{
		temp = (*T)->Lchild;
		(*T)->Lchild = (*T)->Rchild;
		(*T)->Rchild = temp;

		ExchangeTree(&(*T)->Lchild);		//交换左子树
		ExchangeTree(&(*T)->Rchild);		//交换右子树
	}
	return 1;
}

bool isSameTree(BTree p, BTree q) 
{
	if ((p == NULL) && (q == NULL)) {
		return true;
	}
	else if ((p == NULL) || (q == NULL)) {
		return false;
	}
	else if (p->data != q->data) {
		return false;
	}
	else {
		return (isSameTree(p->Lchild, q->Lchild) && isSameTree(p->Rchild, q->Rchild));
	}
}

int main() 
{
#if 0   //基本代码功能测试
	BTree T;
	int depth, count,out1_count,leaf_count;

	printf("输入待创建二叉树的先序序列：n");
	CreatBTree(&T);

	printf("n前序遍历算法的顺序.n");
	PreOrderTraverse(T);

	printf("n中序遍历算法的顺序.n");
	InOrderTraverse(T);

	printf("n后序遍历算法的顺序.n");
	PostOrderTraverse(T);

	depth = MaxDepth(T);
	printf("n二叉树的深度为：%d.n",depth);

	count = NodeCount(T);
	printf("n 二叉树的节点总数为：%dn", count);

	out1_count = Out1_Count(T);
	printf("n度为1的节点个数为：%dn", out1_count);

	leaf_count = Leaf_Count(T);
	printf("n二叉树的叶子节点个数为:%dn", leaf_count);

	ExchangeTree(&T);

	//printf("n删除根节点的左子树.n");
	DeLeftChild(&T);

	printf("n删除根节点的右子树.n");
	DeRightChild(&T);

	DestoryBTree(&T);

	while (1);

#endif

	BTree p, q;

	int result;

	printf("输入待创建二叉树的先序序列p:n");
	CreatBTree(&p);

	getchar(); //吸收缓存区中的空格或者换行符，在输入二叉树p的时候会有一个换行符产生，进入缓存区中。
	printf("输入待创建二叉树的先序序列q:n");
	CreatBTree(&q);

	result = isSameTree(p, q);
	if (result)
		printf("n两个二叉树相同!n");
	else
		printf("n两个二叉树不相同!n");

	while (1);
}

程序是#号作为结束符，输入的是char型数据，如果要输入数字，将结构体中的char data；改为int data;即可。（程序中包括二叉树的很多基本操作，可以用来学习，所有代码在VS2019上测试通过）。