带你手撕链式二叉树—【C语言】

前言：

普通二叉树的增删查改没有意义？那我们为什么要先学习普通二叉树呢？

给出以下两点理由：

1.为后面学习更加复杂的二叉树打基础。（搜索二叉树、ALV树、红黑树、B树系列—多叉平衡搜索树）

2.有很多二叉树的OJ算法题目都是出在普通二叉树的基础上

让我们开始数据结构链式二叉树之旅吧！！！

1. 链式二叉树的遍历

1.1 前序、中序以及后序遍历概念

按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历

1. 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。访问顺序—— 根 —> 左子树—>右子树

2. 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。

访问顺序—— 左子树—>根 —>右子树

3. 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。

访问顺序—— 左子树—>右子树—>根

举例

1.2 前序、中序以及后序遍历代码实现

1.2.1创建二叉树节点

typedef int BTDataType;
typedef struct BinaryTreeNode
{
	struct BinaryTreeNode* left; //左子树
	struct BinaryTreeNode* right;//右子树
	BTDataType data;//数据
}BTNode;

1.2.2 手动搓出一颗二叉树

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int BTDataType;
typedef struct BinaryTreeNode
{
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
	BTDataType data;
}BTNode;

BTNode* BuyNode(BTDataType x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	assert(node);

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

	return node;
}

BTNode* CreatBinaryTree()  //搓树
{
	BTNode* node1 = BuyNode(1);
	BTNode* node2 = BuyNode(2);
	BTNode* node3 = BuyNode(3);
	BTNode* node4 = BuyNode(4);
	BTNode* node5 = BuyNode(5);
	BTNode* node6 = BuyNode(6);

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

	return node1;
}

void PreOrder(BTNode* root) //前序遍历
{
	if (root == NULL)
	{
		printf("# ");
		return;
	}

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

void InOrder(BTNode* root)//中序遍历
{
	if (root == NULL)
	{
		printf("# ");
		return;
	}

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

void PostOrder(BTNode* root)//后序遍历
{
	if (root == NULL) {
		printf("# ");
		return;
	}

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


int main()
{
	BTNode* root = CreatBinaryTree();

	PreOrder(root);//前序遍历
	printf("\n");

	InOrder(root);//中序遍历
	printf("\n");

	PostOrder(root);//后序遍历
	printf("\n");

	return 0;
}

1.2.3 代码结果

1.2.4 递归展开图

（学习二叉树的链式结构，一定要学会画递归展开图）

注意：访问到空树的时候，return的时候不是结束递归，是返回到函数被调用的地方

下面是前序遍历的左子树的递归展开图（右子树原理同理）》》》

2. 求二叉树节点的个数

2.1 全局count的方式（不推荐）

在写代码的过程中要尽量少使用全局变量，这里也是一样的，采用全局变量会有下面的问题：

我们在调用两次的情况下，count会加倍

代码实现

int count = 0;
void TreeSize1(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}

	++count;
	TreeSize1(root->left);
	TreeSize1(root->right);
}

2.2 采用分治的思路

将一颗二叉树分解为3个部分——根节点、左子树、右子树

代码实现：

int TreeSize2(BTNode* root)
{
	return root == NULL ? 0 :
		TreeSize2(root->left) + TreeSize2(root->right) + 1;
}

递归展开图

注意：这里的二叉树和上面的不一样（但是计算方式的大致一样的）

蓝色的数字是递归的次序

红色的数字1，表示返回节点的个数——最后是左子树返回3、右子树返回3、+1，一共是7个节点（可以看出，+1都是递归返回的时候加）

3. 求二叉树叶子节点的个数

思路分析

什么是叶子节点呢 ——> 左右孩子都是空的节点 像上面的二叉树节点个数就是3

怎么控制呢 ——> 1. 二叉树是空树的

2. 二叉树就一个根节点（也就是左右子树为空）

3. 到了第三点，那就直接递归到空，递归到空，就进入第二点，返回1

代码实现

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

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

	return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}

4. 求二叉树第k层的节点数量

思路分析

方法：转换成最小规模的子问题

思路：求第k层的节点，转换成左子树的第k-1层+右子树的第k-1层

每递归一次，k都会-1，当k=1时，就会返回1（也可以看出k不可能减到0）

注意点1：这里的k不能写成k--的形式，递归左子树的时候就k--的话，会改变k，到递归右子树的时候就会出问题

注意点2：重要的事情说三遍！！！ return是返回函数被调用的地方，不是结束整个递归

代码实现

int TreeKLevel(BTNode* root, int k)
{
	assert(k >= 1);
	if (root == NULL)
		return 0;

	if (k == 1)
		return 1;

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