链式二叉树算法精讲：前中后序、层序与完全二叉树判断

//前序遍历 - 根左右
void PreOrder(BTNode* root);
//中序遍历 - 左根右
void InOrder(BTNode* root);
//后序遍历 - 左右根
void PostOrder(BTNode* root);

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>

//定义二叉树节点结构
typedef char BTDataType;
typedef struct BinaryTreeNode {
	BTDataType data;
	struct BinaryTreeNode* left; //指向当前节点左孩子
	struct BinaryTreeNode* right;//指向当前节点右孩子
}BTNode;

//前序遍历 - 根左右
void PreOrder(BTNode* root);
//中序遍历 - 左根右
void InOrder(BTNode* root);
//后序遍历 - 左右根
void PostOrder(BTNode* root);
//二叉树节点个数
int BinaryTreeSize(BTNode* root);
//void BinaryTreeSize(BTNode* root, int* psize);

//二叉树叶子结点个数
int BinaryTreeLeafSize(BTNode* root);
//二叉树第k层结点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
//二叉树的深度/高度
int BinaryTreeDepth(BTNode* root);
//二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
//二叉树销毁
void BinaryTreeDestory(BTNode** root);
//层序遍历
void LevelOrder(BTNode* root);
//判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root);

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
//嵌套包含
//#include"Tree.h"

//typedef int QDataType;
//int更改为二叉树节点结构
//前置声明
typedef struct BinaryTreeNode* QDataType;
//还可以使用下面
//typedef struct BTNode* QDataType;

//定义节点结构
typedef struct QueueNode {
	QDataType data;
	struct QueueNode* next;
}QueueNode;

//定义队列的结构
typedef struct Queue {
	QueueNode* phead; //队头
	QueueNode* ptail; //队尾
	//int size;         //队列中有效数据个数
}Queue; 


//初始化
void QueueInit(Queue* pq);
//销毁
void QueueDesTroy(Queue* pq);

//入队列
void QueuePush(Queue* pq, QDataType x);
//出队列
void QueuePop(Queue* pq);
//取队头数据
QDataType QueueFront(Queue* pq);
//取队尾数据
QDataType QueueBack(Queue* pq);

bool QueueEmpty(Queue* pq);
//队列有效元素个数
int QueueSize(Queue* pq);

#include"Queue.h"

//初始化
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->phead = pq->ptail = NULL;
}

//入队列
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	//创建值为x的节点
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newnode->data = x;
	newnode->next = NULL;
	//队列为空
	if (pq->phead == NULL)
	{
		pq->phead = pq->ptail = newnode;
	}
	else {
		pq->ptail->next = newnode;
		pq->ptail = pq->ptail->next;
	}	
}
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->phead == NULL;
}
//出队列
void QueuePop(Queue* pq)
{
	assert(!QueueEmpty(pq));

	//队列中只有一个节点
	if (pq->phead == pq->ptail)
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	else {
		QueueNode* next = pq->phead->next;
		free(pq->phead);
		pq->phead = next;
	}
}

//取队头数据
QDataType QueueFront(Queue* pq)
{
	assert(!QueueEmpty(pq));
	return pq->phead->data;
}
//取队尾数据
QDataType QueueBack(Queue* pq)
{
	assert(!QueueEmpty(pq));
	return pq->ptail->data;
}
//队列有效元素个数
int QueueSize(Queue* pq)
{
	assert(pq);
	QueueNode* pcur = pq->phead;
	int size = 0;
	while (pcur)
	{
		++size;
		pcur = pcur->next;
	}
	return size;

	//return pq->size;
}
//销毁
void QueueDesTroy(Queue* pq)
{
	assert(pq);

	QueueNode* pcur = pq->phead;
	while (pcur)
	{
		QueueNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	pq->phead = pq->ptail = NULL;
}

#include"Tree.h"
#include"Queue.h"

//前序遍历 - 根左右
void PreOrder(BTNode* root)
{
	//遍历到空节点直接结束
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	//打印根节点
	printf("%c ", root->data);
	//遍历左右孩子，左右孩子还是二叉树，重复操作根左右
	PreOrder(root->left);
	PreOrder(root->right);
}

//中序遍历 - 左根右
void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	//左根右
	InOrder(root->left);
	printf("%c ", root->data);
	InOrder(root->right);
}

//后序遍历 - 左右根
void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%c ", root->data);
}

//错误：创建全局变量，多次调用方法会出现累加的情况
//int size = 0;
////二叉树节点个数
//int BinaryTreeSize(BTNode* root)
//{
//	if (root == NULL)
//	{
//		return 0;
//	}
//	size++;
//	BinaryTreeSize(root->left);
//	BinaryTreeSize(root->right);
//	return size;
//}

//方法二：需要改造函数定义
//void BinaryTreeSize(BTNode* root,int* psize)
//{
//	if (root == NULL)
//	{
//		return;
//	}
//	(*psize)++;
//	BinaryTreeSize(root->left, psize);
//	BinaryTreeSize(root->right, psize);
//}

//节点总数 = 1 + 左子树节点个数 + 右子树节点个数
int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}

//二叉树叶子结点个数
int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	//判断是否为叶子节点
	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}
	//走到这里节点不为空，也不为叶子节点，继续向下递归
	//求左子树叶子节点个数+右子树叶子节点个数
	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

//二叉树第K层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
	if (root == NULL)
	{
		return 0;
	}
	//节点不为空，且K=1
	if (k == 1)
	{
		return 1;
	}
	//节点不为空，且不是第K层，继续递归左右子树，每向下递归一次K-1
	return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}

//二叉树的深度/高度
int BinaryTreeDepth(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int leftDep = BinaryTreeDepth(root->left);
	int rightDep = BinaryTreeDepth(root->right);
	//根节点+manx(左子树高度，右子树高度)
	return 1 + (leftDep > rightDep ? leftDep : rightDep);
}

//二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->data == x)
	{
		return root;
	}
	//节点不为空，且节点的值不为x
	BTNode* leftFind = BinaryTreeFind(root->left, x);
	//找到了
	if (leftFind)
	{
		return leftFind;
	}
	BTNode* rightFind = BinaryTreeFind(root->right, x);
	if (rightFind)
	{
		return rightFind;
	}
	return NULL;
}

//二叉树销毁
void BinaryTreeDestory(BTNode** root)
{
	if (*root == NULL)
	{
		return;
	}
	BinaryTreeDestory(&((*root)->left));
	BinaryTreeDestory(&((*root)->right));
	free(*root);
	*root = NULL;
}

//层序遍历 --- 借助数据结构：队列
void LevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	//在队列中存根结点
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		//取队头，打印队头
		BTNode* top = QueueFront(&q);
		printf("%c ", top->data);
		//出队
		QueuePop(&q);
		if (top->left)
		{
			QueuePush(&q, top->left);
		}
		if (top->right)
		{
			QueuePush(&q, top->right);
		}
	}
	QueueDesTroy(&q);
}

//判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	//头结点入队列
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		//取队头，出队头
		BTNode* top = QueueFront(&q);
		QueuePop(&q);
		//top取到空，直接跳出循环
		if (top == NULL)
		{
			break;
		}
		//top不为空，将队头节点的左右孩子入队列
		QueuePush(&q, top->left);
		QueuePush(&q, top->right);
	}
	//循环判断剩下的结点是否存在非空结点
	while (!QueueEmpty(&q))
	{
		BTNode* top = QueueFront(&q);
		QueuePop(&q);
		if (top != NULL)
		{
			//剩下结点存在非空结点，不是完全二叉树
			QueueDesTroy(&q);
			return false;
		}
	}
	//队列为空，也没有取到不为空的结点
	QueueDesTroy(&q);
	return true;
}

#include"Tree.h"

//创建节点 - 节点内存储char类型的值
BTNode* buyNode(char x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newnode->data = x;
	newnode->left = newnode->right = NULL;
	return newnode;
}

//创建二叉树
BTNode* createTree()
{
	BTNode* nodeA = buyNode('A');
	BTNode* nodeB = buyNode('B');
	BTNode* nodeC = buyNode('C');
	BTNode* nodeD = buyNode('D');
	BTNode* nodeE = buyNode('E');
	BTNode* nodeF = buyNode('F');

	nodeA->left = nodeB;
	nodeA->right = nodeC;
	nodeB->left = nodeD;
	nodeC->left = nodeE;
	nodeC->right = nodeF;
	//nodeB->right = nodeE;
	//nodeC->left = nodeF;
	return nodeA;
}

void test01()
{
	BTNode* root = createTree();
	//传根节点
	//PreOrder(root);
	//InOrder(root);
	//PostOrder(root);
	//printf("size:%d\n", BinaryTreeSize(root));
	//printf("size:%d\n", BinaryTreeSize(root));
	//int Treesize = 0;
	//BinaryTreeSize(root, &Treesize);
	//printf("size:%d\n", Treesize);
	//Treesize = 0;
	//BinaryTreeSize(root, &Treesize);
	//printf("size:%d\n", Treesize);
	//printf("size:%d\n", BinaryTreeSize(root));
	//printf("size:%d\n", BinaryTreeSize(root));
	//printf("size:%d\n", BinaryTreeSize(root));
	//printf("leaf size:%d\n", BinaryTreeLeafSize(root));
	//printf("K level Size:%d\n", BinaryTreeLevelKSize(root, 3));
	//printf("K level Size:%d\n", BinaryTreeLevelKSize(root, 2));
	//printf("K level Size:%d\n", BinaryTreeLevelKSize(root, 1));
	//printf("Tree Depth:%d\n", BinaryTreeDepth(root));
	//BTNode* find = BinaryTreeFind(root, 'F');
	//if (find)
	//{
	//	printf("找到了\n");
	//}
	//else {
	//	printf("未找到\n");
	//}
	//printf("层序遍历的结果：");
	//LevelOrder(root);
	bool isComplete = BinaryTreeComplete(root);
	if (isComplete)
	{
		printf("是完全二叉树\n");
	}
	else {
		printf("不是完全二叉树\n");
	}
	BinaryTreeDestory(&root);
}

int main()
{
	test01();
	return 0;
}