二叉树递归遍历（C语言实现）

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

//二叉树节点
struct BinaryNode
{
	char ch;	//显示字母

	struct BinaryNode* lChild;	//左孩子

	struct BinaryNode* rChild;	//右孩子
};

//递归函数：先序遍历
void recursion(struct BinaryNode* root)
{
	if (root == NULL)
	{
		return;
	}

	//先根
	printf("%c ", root->ch);
	//再左
	recursion(root->lChild);
	//再右
	recursion(root->rChild);
}

//递归函数：中序遍历
void recursion01(struct BinaryNode* root)
{
	if (root == NULL)
	{
		return;
	}

	//中序遍历的结果为：
	recursion(root->lChild);
	printf("%c ", root->ch);
	recursion(root->rChild);
}

//递归函数：后序遍历
void recursion02(struct BinaryNode* root)
{
	if (root == NULL)
	{
		return;
	}

	//后序遍历的结果为：
	recursion(root->lChild);
	recursion(root->rChild);
	printf("%c ", root->ch);
}

//统计叶子数量
void calculateLeafNum(struct BinaryNode* root, int * p)
{
	if (root == NULL)
	{
		return;
	}

	//统计叶子
	if (root->lChild == NULL && root->rChild == NULL)
	{
		(*p)++;
	}

	calculateLeafNum(root->lChild, p);
	calculateLeafNum(root->rChild, p);
}

//统计树高度
int getTreeHeight(struct BinaryNode * root)
{
	if (root == NULL)
	{
		return 0;
	}

	//获取左子树高度
	int lHeight = getTreeHeight(root->lChild);

	//获取右子树高度
	int rHeight = getTreeHeight(root->rChild);

	//取最大的值 +1 就是树的高度
	int height = lHeight > rHeight ? lHeight + 1 : rHeight + 1;

	return height;
}

//拷贝二叉树
struct BinaryNode* copyTree(struct BinaryNode * root)
{
	if (root == NULL)
	{
		return NULL;
	}

	//先拷贝左子树
	struct BinaryNode* lChild = copyTree(root->lChild);

	//再拷贝右子树
	struct BinaryNode* rChild = copyTree(root->rChild);

	//创建新节点
	struct BinaryNode* newNode = (BinaryNode*)malloc(sizeof(struct BinaryNode));

	//将拷贝的左右子树  挂载到新节点上
	newNode->lChild = lChild;
	newNode->rChild = rChild;
	newNode->ch = root->ch;

	//返回结果
	return newNode;
}

void freeTree(struct BinaryNode* root)
{
	if (root == NULL)
	{
		return;
	}

	//先释放左子树
	freeTree(root->lChild);

	//在释放右子树
	freeTree(root->rChild);

	//在释放根节点
	printf("%c被释放了\n", root->ch);
	free(root);
}


void test01()
{
	struct BinaryNode nodeA = { 'A',NULL,NULL };
	struct BinaryNode nodeB = { 'B',NULL,NULL };
	struct BinaryNode nodeC = { 'C',NULL,NULL };
	struct BinaryNode nodeD = { 'D',NULL,NULL };
	struct BinaryNode nodeE = { 'E',NULL,NULL };
	struct BinaryNode nodeF = { 'F',NULL,NULL };
	struct BinaryNode nodeG = { 'G',NULL,NULL };
	struct BinaryNode nodeH = { 'H',NULL,NULL };

	//建立节点之间的关系
	nodeA.lChild = &nodeB;
	nodeA.rChild = &nodeF;

	nodeB.rChild = &nodeC;

	nodeC.lChild = &nodeD;
	nodeC.rChild = &nodeE;

	nodeF.rChild = &nodeG;

	nodeG.lChild = &nodeH;

	//通过递归函数实现遍历

	printf("二叉树的先序遍历结果为：\n");
	recursion(&nodeA);
	printf("\n");

	printf("二叉树的中序遍历结果为：\n");
	recursion01(&nodeA);
	printf("\n");

	printf("二叉树的后序遍历结果为：\n");
	recursion02(&nodeA);
	printf("\n");

	//统计二叉树叶子结点数量
	int num = 0;
	calculateLeafNum(&nodeA, &num);
	printf("树的叶子数量为：%d\n", num);

	//统计树高度
	int height = getTreeHeight(&nodeA);
	printf("树的高度为：%d\n", height);

	//拷贝二叉树
	struct BinaryNode* newTree = copyTree(&nodeA);
	printf("拷贝二叉树结果:");
	recursion(newTree);
	printf("\n");

	//释放二叉树：
	freeTree(newTree);

}

int main()
{
	test01();

	system("pause");
	return 0;
}