二叉树链式结构的实现（递归的暴力美学！！）

前言

Hello,小伙伴们。你们的作者菌又回来了，前些时间我们刚学习完二叉树的顺序结构，今天我们就趁热打铁，继续我们二叉树链式结构的学习。我们上期有提到，二叉树的的底层结构可以选为数组和链表，顺序结构我们选用的数组，那我们就不难知道，二叉树的链式结构采用链表为底层结构。

1.实现链式二叉树

用链表来表示一颗二叉树，即用链表来表示元素之间的逻辑关系。通常的方法就是链表中的每一个节点有三个域组成，数据域和左右指针，左右指针分别用来给出该节点左右孩子所在的链接点的存储地址，数据结构的定义如下：

typedef int BTDataType; // ⼆叉链 typedef struct BinaryTreeNode { struct BinaryTreeNode* left; // 指向当前结点左孩⼦ struct BinaryTreeNode* right; // 指向当前结点右孩⼦ BTDataType val; // 当前结点值域 }BTNode;

不要忘记，我们在实现数据结构时，都要先创建三个文件来使测试代码变得更加的方便：

为了更好的演示效果，我们就在Test.c文件中手动的创建几个节点

BTNode* BuyBTNode(int val) { 	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode)); 	if (newnode == NULL) 	{ 		perror("malloc fail"); 		return NULL; 	}  	newnode->val = val; 	newnode->left = NULL; 	newnode->right = NULL; 	return newnode; }   BTNode* CreateTree() { 	BTNode* n1 = BuyBTNode(1); 	BTNode* n2 = BuyBTNode(2); 	BTNode* n3 = BuyBTNode(3); 	BTNode* n4 = BuyBTNode(4); 	BTNode* n5 = BuyBTNode(5); 	BTNode* n6 = BuyBTNode(6); 	BTNode* n7 = BuyBTNode(7); 	n1->left = n2; 	n1->right = n4; 	n2->left = n3; 	n4->left = n5; 	n4->right = n6; 	n5->left = n7; 	return n1;  }   int main() { 	BTNode* boot = CreateTree(); 	return 0; }

我们已经学习了链表，所以这里创建节点的操作我们就不再过多的赘述，因此，boot就是我们创建的这颗树的根节点。

接下来我们来回顾一下二叉树的概念，二叉树分为空树和非空树

 根节点的左子树和右子树分别有是有子树节点、子树节点的左子树和右子树组成，因此二叉树定义是递归式的，后续链式二叉树的操作中基本都是按照该概念实现的！！

1.1前中后序遍历

二叉树的操作离不开树的遍历，我们先来看看二叉树的遍历有哪些方式：

 1.1.1遍历的规则

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

前序遍历：访问根节点的操作，发生在遍历其左右子树之前。

访问顺序：根节点、左子树、右子树。

中序遍历：访问根节点的操作发生在遍历其左右节点子树之间（间）

访问顺序：左子树、根节点、右子树

后序遍历：访问根节点的操作发生在遍历其左右子树的遍历之后

访问顺序：左子树、右子树、根节点

1.1.2 代码的实现

1.1.2.1 前序遍历（PreOrder）

void PreOrder(BTNode* root) { if (root == NULL) { printf("N "); return; } p rintf("%d ", root->val); PreOrder(root->left); PreOrder(root->right); }

这里我们就涉及到了之前学习函数栈帧的知识，我们可以通过图来理解

函数递归栈帧图：

 

最终我们测试可得：

可知这符合我们前序遍历的规则，因此我们就成功实现了前序遍历。

实现了前序遍历，其他的两个遍历就简单了，几乎和前序遍历一样，中后序遍历也沿用了递归的思想 

后面大家能否根据上面前序遍历的代码实现中序遍历和后序遍历呢？

大家不妨一试。

1.1.2.2中序遍历（InOrder）

void InOrder(BTNode* root) { if (root == NULL) { printf("N "); return; }  InOrder(root->left); printf("%d ", root->val); InOrder(root->right); }

1.1.2.3后序遍历（PostOredr）

v oid PostOrder(BTNode* root) { if (root == NULL) { printf("N "); return; } I nOrder(root->left); InOrder(root->right); printf("%d ", root->val); }

 

有序他们之间的相似性，在代码上的差异也就只是不同行的代码顺序不一样，但是转化为后面的函数栈帧却又不小的差别。但在本质上，却还是大差不差！！

1.2节点个数以及高度等

1.2.1节点计数

// ⼆叉树结点个数 int BinaryTreeSize(BTNode* root);

我们来想一想，怎样才能达到我们的目的呢？

假设我们现在有这样的二叉树：
 

所以从上所述，我们就能够得出计数代码：

int BinaryNodeCount(BTNode* root) { 	if (root == NULL) 		return 0; 	return 1 + BinaryNodeCount(root->left) + BinaryNodeCount(root->right);  }

 代码测试：

这里我们创建的是这样的二叉树。

可知这样我们就实现了二叉树节点的计数！！

 1.2.2二叉树叶子结点个数

// ⼆叉树叶⼦结点个数 int BinaryTreeLeafSize(BTNode*root)

有了前面写求所有节点个数的经验，其实这个不就不难了：

叶子结点，就是没有子节点的节点。即root->left = root->right = NULL.

所以在这里我们就有两种返回情况，当遍历到NULL时，我们返回0， 当递归到叶子结点时，我们就返回1。借助函数栈帧，就可以进行计数！！

接下来我们来实现一下这个代码：

//求二叉树叶子节点的个数 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); }

我们可以先提前看看这颗二叉树有多少个叶子结点：

上面我们可以看出一共有3个没有子节点的节点，所以叶子结点的个数就是3

 

1.2.3 二叉树第K层的节点个数

// ⼆叉树第k层结点个数 int BinaryTreeLevelKSize(BTNode* root, int k);

我们要得到二叉树第K层节点的个数，其实也并不难，我们还是通过画图的方式来解析过程。

假设我们要求的是第三层的节点数：

 代码实现：

int BinaryTreeLevelKSize(BTNode* root, int k) { 	if (root == NULL) 	{ 		return 0; 	} 	if (k == 1) 		return 1; 	return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1); }

测试一下：

 1.2.4二叉树的深度/高度

//⼆叉树的深度/⾼度 int BinaryTreeDepth(BTNode* root);

在这里我们可以想出怎样的思路呢？

我们还是要先画图求证：

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

 代码测试：

 从上面我们事先创建的那棵树一样，树的深度为4.所以我们实现了我们的目的。

1.2.5二叉树查找置位x的节点

// ⼆叉树查找值为x的结点 BTNode* BinaryTreeFind(BTNode* root, BTDataType x);

这个操作也十分的简单，我们只需要遍历二叉树，找到与目标值相等的节点，我们就将其返回。

我们先看看实现代码：

// ⼆叉树查找值为x的结点 BTNode* BinaryTreeFind(BTNode* root, BTDataType x) { 	if (root == NULL) 		return NULL; 	if (root->val == x) 		return root; 	BTNode* left =BinaryTreeFind(root->left, x); 	if (left) 		return left; 	BTNode* right = BinaryTreeFind(root->right, x); 	if (right) 		return right; 	return NULL; }

在这里我们还是要进行二叉树的左右子树遍历，但是我们为了提高效率，只要在一边找到了符合目标的节点我们就直接返回该节点！！

小伙伴们可以根据上面的知识，自行画出递归栈帧图。

我们来测试以下代码：

可知其成功的找到了，值为6的节点！！ 

1.2.6 二叉树的销毁

// ⼆叉树销毁 void BinaryTreeDestory(BTNode** root);

销毁的逻辑也十分的简单了，通过了递归的操作，我们遍历所有不为NULL的节点并销毁，这里我们就直接写出代码，大家可以自己进行递归栈帧的推理：

void BinaryTreeDestory(BTNode** root) { 	if (*root == NULL) 	{ 		return; 	} 	BinaryTreeDestory(&((*root)->left)); 	BinaryTreeDestory(&((*root)->right)); 	free(*root); 	*root = NULL; }

代码测试：

进行销毁操作：

 2.代码展示

2.1Test.c

#define _CRT_SECURE_NO_WARNINGS 1  #include"Tree.h" BTNode* BuyBTNode(int val) { 	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode)); 	if (newnode == NULL) 	{ 		perror("malloc fail"); 		return NULL; 	}  	newnode->val = val; 	newnode->left = NULL; 	newnode->right = NULL; 	return newnode; }   BTNode* CreateTree() { 	BTNode* n1 = BuyBTNode(1); 	BTNode* n2 = BuyBTNode(2); 	BTNode* n3 = BuyBTNode(3); 	BTNode* n4 = BuyBTNode(4); 	BTNode* n5 = BuyBTNode(5); 	BTNode* n6 = BuyBTNode(6); 	BTNode* n7 = BuyBTNode(7); 	n1->left = n2; 	n1->right = n4; 	n2->left = n3; 	n4->left = n5; 	n4->right = n6; 	n5->left = n7; 	return n1;  }   int main() { 	BTNode* root = CreateTree(); 	PreOrder(root); 	printf("\n"); 	InOredr(root); 	printf("\n"); 	PostOrder( root); 	printf("\n"); 	printf("TreeNodeCount: %d\n", BinaryNodeCount(root)); 	printf("leafSize: %d\n", BinaryTreeLeafSize(root)); 	printf("TreeLevelKSize: %d\n", BinaryTreeLevelKSize(root, 3)); 	printf("TreeLevelDepth: %d\n", BinaryTreeDepth(root)); 	BTNode* find = BinaryTreeFind(root, 6); 	printf("%s ", find == NULL ? "没找到" : "找到了！！"); 	printf("返回节点的值为：%d\n", find->val); 	BinaryTreeDestory(&root); 	PostOrder(root); 	return 0; } 

2.2Tree.h

#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> #include<time.h> #include<stdbool.h> typedef int BTDataType; // ⼆叉链 typedef struct BinaryTreeNode { 	struct BinaryTreeNode* left; // 指向当前结点左孩⼦ 	struct BinaryTreeNode* right; // 指向当前结点右孩⼦ 	BTDataType val; // 当前结点值域 }BTNode; //前序遍历 void PreOrder(BTNode* root); //中序遍历 void InOredr(BTNode* root); //后序遍历 void PostOrder(BTNode* root); //计数二叉树的节点 int BinaryNodeCount(BTNode* root); //求二叉树叶子节点的个数 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);

2.3Tree.c

#define _CRT_SECURE_NO_WARNINGS 1 #include"Tree.h" void PreOrder(BTNode* root) { 	if (root == NULL) 	{ 		return; 	} 	printf("%d ", root->val); 	PreOrder(root->left); 	PreOrder(root->right); } void InOredr(BTNode* root) { 	if (root == NULL) 		return; 	InOredr(root->left); 	printf("%d ", root->val); 	InOredr(root->right); } void PostOrder(BTNode* root) { 	if (root == NULL) 	{ 		return; 	} 	PostOrder(root->left); 	PostOrder(root->right); 	printf("%d ", root->val); } int BinaryNodeCount(BTNode* root) { 	if (root == NULL) 		return 0; 	return 1 + BinaryNodeCount(root->left) + BinaryNodeCount(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); } int BinaryTreeLevelKSize(BTNode* root, int k) { 	if (root == NULL) 	{ 		return 0; 	} 	if (k == 1) 		return 1; 	return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1); } int BinaryTreeDepth(BTNode* root) { 	if (root == NULL) 		return 0; 	int leftDepth = BinaryTreeDepth(root->left); 	int rightDepth = BinaryTreeDepth(root->right); 	return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1; } // ⼆叉树查找值为x的结点 BTNode* BinaryTreeFind(BTNode* root, BTDataType x) { 	if (root == NULL) 		return NULL; 	if (root->val == x) 		return root; 	BTNode* left =BinaryTreeFind(root->left, x); 	if (left) 		return left; 	BTNode* right = BinaryTreeFind(root->right, x); 	if (right) 		return right; 	return NULL; } void BinaryTreeDestory(BTNode** root) { 	if (*root == NULL) 	{ 		return; 	} 	BinaryTreeDestory(&((*root)->left)); 	BinaryTreeDestory(&((*root)->right)); 	free(*root); 	*root = NULL; }

好，今天的学习就到这里，我们下期再见，拜拜！！