【初阶数据结构篇】链式结构二叉树（二叉链）的实现（感受递归暴力美学）

文章目录

须知

💬 欢迎讨论：如果你在学习过程中有任何问题或想法，欢迎在评论区留言，我们一起交流学习。你的支持是我继续创作的动力！

👍 点赞、收藏与分享：觉得这篇文章对你有帮助吗？别忘了点赞、收藏并分享给更多的小伙伴哦！你们的支持是我不断进步的动力！
🚀 分享给更多人：如果你觉得这篇文章对你有帮助，欢迎分享给更多对C++感兴趣的朋友，让我们一起进步！

上篇已经实现过顺序结构二叉树-》堆

1. 链式结构二叉树的实现

1.1 二叉树的概念与结构

1.1.1 链式二叉树概念

⽤链表来表⽰⼀棵⼆叉树，即⽤链来指示元素的逻辑关系。通常的⽅法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别⽤来给出该结点左孩⼦和右孩⼦所在的链结点的存储地址。

1.1.2 链式二叉树结构

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

1.2 创建二叉树

⼆叉树的创建⽅式⽐较复杂，为了更好的步⼊到⼆叉树内容中，我们先⼿动创建⼀棵链式⼆叉树

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;
}

回顾

1. ⼆叉树分为空树和⾮空⼆叉树，⾮空⼆叉树由根结点、根结点的左⼦树、根结点的右⼦树组成的。

2. 根结点的左⼦树和右⼦树分别⼜是由⼦树结点、⼦树结点的左⼦树、⼦树结点的右⼦树组成的，因此⼆叉树定义是递归式的,后序链式⼆叉树的操作中基本都是按照该概念实现的。

BinaryTree.h

头文件包括函数的定义，其他头文件以及二叉树的结构

我们将依次实现下面重要的函数

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
//定义二叉树的链式结构
//二叉树结点的结构
typedef int BTDataType;
typedef struct BinaryTreeNode
{int 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);

在程序开发前，一般每次写出函数，就会进行测试，一遍进行检查错误。

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Binary.h"BTNode * buyNode(BTDataType 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;
}void test01()
{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 = node3;node2->right = node4;//node2->right = node5;//node3->left = node6;//PreOrder(node1);//printf("\n");//InOrder(node1);//printf("\n");//PostOrder(node1);//int size = 0;//BinaryTreeSize(node1, &size);//printf("size : %d\n", size);size = 0;//BinaryTreeSize(node1, &size);//printf("size : %d\n", size);//printf("size:%d\n", BinaryTreeSize(node1));//printf("size:%d\n", BinaryTreeSize(node1));//printf("size:%d\n", BinaryTreeSize(node1));//printf("leaf size: %d\n", BinaryTreeLeafSize(node1));//printf("第K层size : %d\n", BinaryTreeLevelKSize(node1, 2));//printf("depth/height:%d\n", BinaryTreeDepth(node1));//BTNode* find =BinaryTreeFind(node1, 33);//printf("%s\n", find == NULL ? "未找到！" : "找到了！");//LevelOrder(node1);bool ret = BinaryTreeComplete(node1);printf("%s\n", ret == false ? "不是完全二叉树" : "是完全二叉树");BinaryTreeDestory(&node1);
}int main()
{test01();return 0;
}

BinaryTree.cpp 这个源文件都是实现头文件的，定义。

下面我们将直接上高速，不再多废话了.

2. 函数的定义

2.1 二叉树的遍历

2.1.1遍历规则

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

1）前序遍历(Preorder Traversal 亦称先序遍历)：访问根结点的操作发⽣在遍历其左右⼦树之前

访问顺序为：根结点、左⼦树、右⼦树

2）中序遍历(Inorder Traversal)：访问根结点的操作发⽣在遍历其左右⼦树之中（间）

访问顺序为：左⼦树、根结点、右⼦树

3）后序遍历(Postorder Traversal)：访问根结点的操作发⽣在遍历其左右⼦树之后

访问顺序为：左⼦树、右⼦树、根结点

偷偷告诉大家我是如何记这个规则，自我感觉很有用，子树都是从左往右遍历，看什么遍历，例如前序遍历，就说明根在前。

2.1.1.1 前序遍历

核心思想：递归(先递推，再递归)

首先递归一定要有结束条件，没有则会无限递归，死循环。

当递归到叶子节点，左右节点都为NULL，结束递推，逐次递归回上一次创建函数栈帧。

即root==NULL

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

图示：

2.1.1.2 中序遍历

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

2.1.1.3 后序遍历

void PostOrder(BTNode* root)
{if (root == NULL){//printf("NULL ");return;}PostOrder(root->left);PostOrder(root->right);printf("%d ", root->data);
}

2.2 二叉树节点个数

本节点+左节点+右节点

当节点为空，返回0

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

图解：

2.3 二叉树叶子节点个数

叶子结点：度为0,即没有孩子节点

// ⼆叉树叶⼦结点个数
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);
}

图解：

2.4 二叉树第k层节点个数

求第k层左子树节点个数+第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);
}

图解：

2.5 二叉树的深度/高度

要求高度，即子树高度的最大值+1，子树高度的最大值又是其子树高度最大值+1，以此类推
当递推到空节点时结束——>返回0（空节点不算高度）
回归时每次返回左右子树高度取最大值+1

//⼆叉树的深度/⾼度
int BinaryTreeDepth(BTNode* root)
{if (root == NULL){return 0;}int leftDep = BinaryTreeDepth(root->left);int rightDep = BinaryTreeDepth(root->right);return leftDep > rightDep ? leftDep + 1 : rightDep + 1;
}

源代码（C++）

#define _CRT_SECURE_NO_WARNINGS 1
#include "Binary.h"
#include "Queue.h"
//前序遍历---根左右
void PreOrder(BTNode* root)
{if (root == NULL){return;}printf("%d ", root->data);PreOrder(root->left);PreOrder(root->right);
}//中序遍历--左根右
void InOrder(BTNode* root)
{if (root == 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);
}
// ⼆叉树结点个数
//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 0;
//	}
//	++(*psize);
//	BinaryTreeSize(root->left,psize);
//	BinaryTreeSize(root->right,psize);
//}// ⼆叉树结点个数
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;}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 leftDep = BinaryTreeDepth(root->left);int rightDep = BinaryTreeDepth(root->right);return leftDep > rightDep ? leftDep + 1 : rightDep + 1;
}
// ⼆叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root == NULL){return NULL;}if (root->data == x){return root;}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;
}