typedef int BTDataType;

typedef struct BinaryTreeNode
{
	struct BinaryTreeNode* left; // 指向左孩子
	struct BinaryTreeNode* right; // 指向右孩子
	BTDataType data;
}BTNode;

2.创建二叉树

????????实现一个较为简易版的创建二叉树函数，仅仅在函数内部进行创建节点，同时再实现一个专门创建节点的函数，用来创建多个节点，并以二叉树的方式链接起来。

BTNode* BuyBTNode(BTDataType x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	if (node == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}

	node->data = x;
	node->left = node->right = NULL;
	
	return node;
}

BTNode* CreateBTree()
{
	BTNode* node1 = BuyBTNode(1);
	BTNode* node2 = BuyBTNode(2);
	BTNode* node3 = BuyBTNode(3);
	BTNode* node4 = BuyBTNode(4);
	BTNode* node5 = BuyBTNode(5);
	BTNode* node6 = BuyBTNode(6);

	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	node4->left = node5;
	node4->right = node6;

	return node1;
}

3.二叉树前序遍历

????????前中后序遍历的核心就是递归，首先递归的终止条件是当前节点为空时，停止递归，如果不是，就先输出当前节点数据，然后向左向右进行递归。

void PrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	printf("%d ", root->data);
	PrevOrder(root->left);
	PrevOrder(root->right);
}

4.二叉树中序遍历

? ? ? ? 中序还是递归，只是因为是中序，所以要先向左递归，之后再打印当前节点，最后再向右递归。

void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	InOrder(root->left);
	printf("%d ", root->data);
	InOrder(root->right);
}

5.二叉树后序遍历

? ? ? ? 后序依旧是递归，只是因为是后序，所以要先向左递归，再向右递归，最后再打印当前节点数据。

void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->data);
}

6.二叉树层序遍历

? ? ? ? 层序遍历需要利用队列的先进先出的特性来实现。

? ? ? ? 首先要把之前实现的队列拿出来，在这里直接调用队列函数即可。队列初始化之后，先把根节点放入队列中，然后进入while循环，front拿到队列第一个节点，之后删掉，并打印出该节点数据，接着如果该节点有左孩子或者右孩子，就继续把孩子节点放入队列中。如果队列不为空，就继续进行循环，直到所有节点都遍历后，把队列销毁即可。

? ? ? ? 这样从根节点开始，再到根节点的下一层，接着再下一层，这样就实现了二叉树的层序遍历。

void LevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);

	if (root)
	{
		QueuePush(&q, root);
	}

	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);

		printf("%d ", front->data);

		if (front->left)
		{
			QueuePush(&q, front->left);
		}

		if (front->right)
		{
			QueuePush(&q, front->right);
		}
	}

	printf("\n");
	QueueEmpty(&q);
}

7.二叉树节点个数

两种方法：

方法1：遍历+计数

? ? ? ? ?通过递归进行继续，但是这时需要考虑该如何计数，这里我们可以比较容易想到全局变量和静态变量，但是这两种都不好，因此可以通过一个计数的指针变量作为函数的参数，这样每次递归时，也会跟着改变，借此来计数。

思想：遍历+计数
void BTreeSize(BTNode* root, int* pCount)
{
	if (root == NULL)
		return;

	++(*pCount);
	BTreeSize(root->left, pCount);
	BTreeSize(root->right, pCount);
}

方法2：分治

?????????这种方法比较好，在递归返回时，每次都+1，这样就相当于计数，最后返回的值就是节点的个数。

//思想：分治
int BTreeSize(BTNode* root)
{
	return root == NULL ? 0 : BTreeSize(root->left)+ BTreeSize(root->right) + 1;
}

8.二叉树叶子节点个数

? ? ? ? 叶子节点没有左孩子和右孩子，因此递归到叶子节点时，返回1，相当于计了1个数，最后返回的就是叶子节点的个数。

int BTreeLeafSize(BTNode* root)
{
	if (root == NULL)
		return 0;

	if (root->left == NULL && root->right == NULL)
		return 1;
	
	return BTreeLeafSize(root->left) + BTreeLeafSize(root->right);
}

9.二叉树第k层节点个数

? ? ? ? 要知道第k层节点个数，通过递归，每次往下走一层，就让k-1，这样当最后k=1时，就相当于第k层，因此每当第k层有一个节点就返回1，最后返回的就是第k层节点个数。

int BTreeKLevelSize(BTNode* root, int k)
{
	assert(k >= 1);

	if (root == NULL)
		return 0;

	if (k == 1)
		return 1;

	return BTreeKLevelSize(root->left, k - 1)
		+ BTreeKLevelSize(root->right, k - 1);
}

10.二叉树最大深度

? ? ? ? 递归往下走，leftDepth记录左边最大深度，rightDepth记录右边最大深度，如果左边更深，就让leftDepth+1，如果右边更深，就让rightDepth+1，这样一直递归下去，最后返回的就是二叉树的最大深度。

int BTreeDepth(BTNode* root)
{
	if (root == NULL)
		return 0;

	int leftDepth = BTreeDepth(root->left);
	int rightDepth = BTreeDepth(root->right);

	return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}

11.二叉树查找值为x的节点

? ? ? ? 查找函数，通过递归查找吗，如果找到了，先把这个节点返回前一个递归函数，然后继续往前返回，直到最后，返回回去。

BTNode* BTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return NULL;

	if (root->data == x)
		return root;

	BTNode* ret1 = BTreeFind(root->left, x);
	if (ret1)
		return ret1;

	BTNode* ret2 = BTreeFind(root->right, x);
	if (ret2)
		return ret2;

	return NULL;
}

12.判断二叉树是否为完全二叉树

? ? ? ? 类似于层序遍历，也是通过队列来完成。

? ? ? ? 前面和层序遍历差不多，但是要注意这个是不管当前节点的下一个是否为空，空节点也进队列。

? ? ? ? 如果是完全二叉树，那么在队列中的空节点后面一定都是空节点，如果有非空节点就说明不是完全二叉树。

bool BTreeComplete(BTNode* root)
{
	Queue* q;
	QueueInit(&q);

	if (root)
	{
		QueuePush(&q, root);
	}

	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);

		if (front == NULL)
		{
			break;
		}

		QueuePush(&q, root->left);
		QueuePush(&q, root->right);
	}

	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		//如果在空后出到非空，说明不是完全二叉树
		if (front)
		{
			return false;
		}
	}

	return true;
}

13.二叉树销毁

? ? ? ? 递归分别销毁左右孩子节点，最后销毁根节点。

void BTreeDestory(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}

	BTreeDestory(root->left);
	BTreeDestory(root->right);
	free(root);
}

二.代码

1.BinaryTree.h

#pragma once

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

#include "Queue.h"

typedef int BTDataType;

typedef struct BinaryTreeNode
{
	struct BinaryTreeNode* left; // 指向当前节点左孩子
	struct BinaryTreeNode* right; // 指向当前节点右孩子
	BTDataType data;
}BTNode;

//BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi);//构建二叉树（通过前序遍历的数组'#'代表NULL）

BTNode* CreateBTree();//创建二叉树

void PrevOrder(BTNode* root);//二叉树前序遍历

void InOrder(BTNode* root);//二叉树中序遍历

void PostOrder(BTNode* root);//二叉树后序遍历

void LevelOrder(BTNode* root);//二叉树层序遍历(使用队列，注意入队列的为节点(struct BinaryNode*))

int BTreeSize(BTNode* root);//二叉树节点个数

int BTreeLeafSize(BTNode* root);//二叉树叶子节点个数

int BTreeLevelKsize(BTNode* root, int k);//二叉树第k层节点个数

int BTreeDepth(BTNode* root);//二叉树最大深度

BTNode* BTreeFind(BTNode* root, BTDataType x);//二叉树查找值为x的节点

bool BTreeComplete(BTNode* root);//判断二叉树是否是完全二叉树(类似层序遍历)(利用NULL)

void BTreeDestory(BTNode* root);//二叉树销毁

2.BinaryTree.c

#include "BinaryTree.h"

//BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
//{
//	if (a[*pi] == '#' || *pi >= n)
//	{
//		(*pi)++;
//		return NULL;
//	}
//
//	BTNode* root = (BTNode*)malloc(sizeof(BTNode));
//	root->data = a[(*pi)++];
//
//	root->left = BinaryTreeCreate(a, n, pi);
//	root->right = BinaryTreeCreate(a, n, pi);
//
//	return root;
//}

BTNode* BuyBTNode(BTDataType x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	if (node == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}

	node->data = x;
	node->left = node->right = NULL;
	
	return node;
}

BTNode* CreateBTree()
{
	BTNode* node1 = BuyBTNode(1);
	BTNode* node2 = BuyBTNode(2);
	BTNode* node3 = BuyBTNode(3);
	BTNode* node4 = BuyBTNode(4);
	BTNode* node5 = BuyBTNode(5);
	BTNode* node6 = BuyBTNode(6);

	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	node4->left = node5;
	node4->right = node6;

	return node1;
}

void PrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	printf("%d ", root->data);
	PrevOrder(root->left);
	PrevOrder(root->right);
}

void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	InOrder(root->left);
	printf("%d ", root->data);
	InOrder(root->right);
}

void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->data);
}

void LevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);

	if (root)
	{
		QueuePush(&q, root);
	}

	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);

		printf("%d ", front->data);

		if (front->left)
		{
			QueuePush(&q, front->left);
		}

		if (front->right)
		{
			QueuePush(&q, front->right);
		}
	}

	printf("\n");
	QueueEmpty(&q);
}

//思想：遍历+计数
//void BTreeSize(BTNode* root, int* pCount)
//{
//	if (root == NULL)
//		return;
//
//	++(*pCount);
//	BTreeSize(root->left, pCount);
//	BTreeSize(root->right, pCount);
//}

//思想：分治
int BTreeSize(BTNode* root)
{
	return root == NULL ? 0 : BTreeSize(root->left)+ BTreeSize(root->right) + 1;
}

int BTreeLeafSize(BTNode* root)
{
	if (root == NULL)
		return 0;

	if (root->left == NULL && root->right == NULL)
		return 1;
	
	return BTreeLeafSize(root->left) + BTreeLeafSize(root->right);
}

int BTreeKLevelSize(BTNode* root, int k)
{
	assert(k >= 1);

	if (root == NULL)
		return 0;

	if (k == 1)
		return 1;

	return BTreeKLevelSize(root->left, k - 1)
		+ BTreeKLevelSize(root->right, k - 1);
}

int BTreeDepth(BTNode* root)
{
	if (root == NULL)
		return 0;

	int leftDepth = BTreeDepth(root->left);
	int rightDepth = BTreeDepth(root->right);

	return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}

BTNode* BTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return NULL;

	if (root->data == x)
		return root;

	BTNode* ret1 = BTreeFind(root->left, x);
	if (ret1)
		return ret1;

	BTNode* ret2 = BTreeFind(root->right, x);
	if (ret2)
		return ret2;

	return NULL;
}

void BTreeDestory(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}

	BTreeDestory(root->left);
	BTreeDestory(root->right);
	free(root);
}

bool BTreeComplete(BTNode* root)
{
	Queue* q;
	QueueInit(&q);

	if (root)
	{
		QueuePush(&q, root);
	}

	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);

		if (front == NULL)
		{
			break;
		}

		QueuePush(&q, root->left);
		QueuePush(&q, root->right);
	}

	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		//如果在空后出到非空，说明不是完全二叉树
		if (front)
		{
			return false;
		}
	}

	return true;
}

3.Test.c

#include "BinaryTree.h"

void BTreeTest1()
{
	BTNode* tree = CreateBTree();

	PrevOrder(tree);
	printf("\n");

	InOrder(tree);
	printf("\n");

	PostOrder(tree);
	printf("\n");
}

void BTreeTest2()
{
	BTNode* tree = CreateBTree();

	printf("size:%d\n", BTreeSize(tree));
	printf("size:%d\n", BTreeSize(tree));
	printf("size:%d\n", BTreeSize(tree));

	printf("Leaf size:%d\n", BTreeLeafSize(tree));

	printf("Depth size:%d\n", BTreeDepth(tree));
}

void BTreeTest3()
{
	BTNode* tree = CreateBTree();

	for (int i = 1; i <= 7; ++i)
	{
		printf("Find:%d %p\n", i, BTreeFind(tree, i));
	}

	BTNode* ret = BTreeFind(tree, 5);
	if (ret)
	{
		ret->data = 50;
	}
	PrevOrder(tree);
	printf("\n");

	BTreeDestory(tree);
	tree = NULL;
}

void BTreeTest4()
{
	BTNode* tree = CreateBTree();

	LevelOrder(tree);
}

int main()
{
	BTreeTest1();
	BTreeTest2();
	BTreeTest3();
	BTreeTest4();

	return 0;
}

4.Queue.h

#pragma once

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>

struct BinaryTreeNode;

typedef struct BinartTreeNode* QDataType;

typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;
}QNode;

typedef struct Queue
{
	QNode* head;
	QNode* tail;
}Queue;

void QueueInit(Queue* pq);//初始化队列

void QueueDestory(Queue* pq);//销毁队列

void QueuePush(Queue* pq, QDataType x);//入队列

void QueuePop(Queue* pq);//出队列

bool QueueEmpty(Queue* pq);//判断队列是否为空

size_t QueueSize(Queue* pq);//队列数据个数

QDataType QueueFront(Queue* pq);//队列头数据

QDataType QueueBack(Queue* pq);//队列尾数据

5.Queue.c

#include "Queue.h"

void QueueInit(Queue* pq)
{
	assert(pq);

	pq->head = NULL;
	pq->tail = NULL;
}

void QueueDestorty(Queue* pq)
{
	assert(pq);

	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	
	pq->head = NULL;
	pq->tail = NULL;
}

void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);

	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	assert(newnode);

	newnode->data = x;
	newnode->next = NULL;

	if (pq->tail == NULL)
	{
		assert(pq->head == NULL);
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
}

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->head && pq->tail);

	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
}

bool QueueEmpty(Queue* pq)
{
	assert(pq);

	return pq->head == NULL;
}

size_t QueueSize(Queue* pq)
{
	assert(pq);

	QNode* cur = pq->head;
	size_t size = 0;
	while (cur)
	{
		++size;
		cur = cur->next;
	}

	return size;
}

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->head);

	return pq->head->data;
}

QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->tail);

	return pq->tail->data;
}