【新春不断更】数据结构与算法之美：二叉树
Hello大家好，我是但凡！很高兴我们又见面啦！
眨眼间已经到了2024年的最后一天，在这里我要首先感谢过去一年陪我奋斗的每一位伙伴，是你们给予我不断前行的动力。银蛇携福至，万象启新程。蛇年新春之际，愿你们万事顺遂，岁月皆安，新的一年所想皆如愿，所行皆坦途 。
好了，给生活添点passion，开始今天的编程之路！
我的博客：<但凡.
我的专栏：《编程之路》、《数据结构与算法之美》、《题海拾贝》
欢迎点赞，关注！
目录
1、 二叉树的动态模拟
1.1新建节点
1.2建树
1.3计算树的节点个数
1.3.1方法一
1.3.2方法二
1.4计算树的叶子节点个数
1.5 计算树的第K层节点个数
1.6 树的深度
1.7查找节点
1.8 遍历
1.8.1前序遍历
1.8.2中序遍历
1.8.3后序遍历
1.8.4层序遍历（广度优先遍历）
1.9判断二叉树是否为完全二叉树
1.10销毁二叉树
2、二叉树的静态模拟实现
1、 二叉树的动态模拟
我们用链式结构实现二叉树。一般链式结构实现二叉树，我们的结构中包含三个元素，一是该节点的数据，二是左子树节点，三是右子树节点
typedef char BTtype;
typedef struct BinaryTreeNode
{BTtype x;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTnode;1.1新建节点
BTnode* BTbuybode(char a)//你这声明和定义都不是一个意思好的
{BTnode* p = (BTnode*)malloc(sizeof(BTnode));if (p == NULL){perror("malloc error!");exit(1);}p->left = NULL;p->right = NULL;p->x = a;return p;
}1.2建树
需要注意的是，我们的树是需要手动去建的，所以我在这只是给大家一个示例：
//建树
BTnode* nodeA=BTbuybode('A');
BTnode* nodeB = BTbuybode('B');
BTnode* nodeC = BTbuybode('C');
BTnode* nodeD = BTbuybode('D');
BTnode* nodeE = BTbuybode('E');
nodeA->left = nodeB;
nodeA->right = nodeC;
nodeB->left = nodeD;
nodeC->left = nodeE;
BTnode* root = nodeA;建的树是这样的：
那么接下来我们就实现以下和树相关的操作。准备好迎接递归的极致暴力美学！
1.3计算树的节点个数
1.3.1方法一
方法一就是咱们把size作为一个函数的形参，然后把这个树遍历一遍，每遍历一个节点就size（节点个数）加一。但需要注意的是，我们需要传入size的地址才能改变size的值。
void BinaryTreeSize(BTnode* root,int* size)
{if (root == NULL){return;}(*size)++;BinaryTreeSize(root->left,size);BinaryTreeSize(root->right, size);
}1.3.2方法二
方法二是纯递归： 节点个数=左子树节点个数+右子树节点个数，所以我们以此为基础递归就可以了。
int BinaryTreeSize(BTnode* root)
{//节点个数=左子树节点个数+右子树节点个数//递归出口if (root == NULL){return 0;}return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}1.4计算树的叶子节点个数
树的叶子结点就是没有左右子树的节点，所以咱们得设置两个递归出口。
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);
}1.5 计算树的第K层节点个数
当咱们K减成1的时候，就说明到达了第K层。
int BinaryTreeLevelKSize(BTnode* root, int k)
{//递归出口if(k==1){if (root == NULL){return 0;}else{return 1;}}return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}1.6 树的深度
注意我是拿C++写的，用了自带的函数max，如果使用C语言写的话max函数得自己写，或者用一个问号表达式来实现类似效果。
int BinaryTreeDeep(BTnode* root)
{//计算树的深度if (root == NULL){return 0;}return 1 + max(BinaryTreeDeep(root->left), BinaryTreeDeep(root->right));
}1.7查找节点
BTnode* BinaryTreeFind(BTnode* root, BTtype x)
{//递归出口if (root == NULL){return 0;}if (root->x == x){return root;}BTnode* left = BinaryTreeFind(root->left, x);if(left){return root;}BTnode* right = BinaryTreeFind(root->right, x);if (right){return root;}return NULL;
}1.8 遍历
1.8.1前序遍历
前序遍历就是先遍历头节点，然后遍历左子树，最后遍历右子树。我们可以把它拆开来想，我们左子树依然用先遍历头，再遍历左子树，最后遍历右子树的方式来遍历，左子树的左子树依然如此......
void BinaryTreePrevOrder(BTnode* root)
{//头 左 右//递归出口if (root == NULL){cout << "NULL" << " ";return;}cout << root->x << " ";BinaryTreePrevOrder(root->left);BinaryTreePrevOrder(root->right);
}1.8.2中序遍历
void BinaryTreeInOrder(BTnode* root)
{//左 头 右//递归出口if (root == NULL){cout << "NULL" << " ";return;}BinaryTreeInOrder(root->left); //注意别调用错了，调用中序的cout << root->x << " ";BinaryTreeInOrder(root->right);
}1.8.3后序遍历
void BinaryTreePostOrder(BTnode* root)
{//递归出口if (root == NULL){cout << "NULL" << " ";return;}BinaryTreePostOrder(root->left);BinaryTreePostOrder(root->right);cout << root->x << " ";
}我们可以发现，这三个遍历的不同就是打印根节点的位置发生了变化 。我们以上三个遍历都属于深度优先遍历。
1.8.4层序遍历（广度优先遍历）
void BinaryTreeLevelOrder(BTnode* root)
{queue<BTnode*> q;//创建队列q.push(root);while (!q.empty()){BTnode* tmp = q.front();q.pop();cout << tmp->x << " ";//左右子树入队列if (tmp->left){q.push(tmp->left);}if (tmp->right){q.push(tmp->right);}}
}这个层序遍历我用了c++自带的队列，如果用C语言写的话我们可以把模拟实现的队列文件导入。我之前发过队列的模拟实现，给大家放在这里： 数据结构与算法之美：队列-CSDN博客
1.9判断二叉树是否为完全二叉树
bool BinaryTreeComplete(BTnode* root)
{queue<BTnode*> q;//创建队列q.push(root);while (!q.empty()){BTnode* tmp = q.front();q.pop();if (tmp==NULL){break;}//左右子树入队列q.push(tmp->left);q.push(tmp->right);}//现在队列中如果还有不为空的节点，就说明不是完全二叉树 while (!q.empty()){BTnode* tmp = q.front();q.pop();if (tmp){return false;}}return true;
}1.10销毁二叉树
void BinaryTreeDestory(BTnode** root)
{//这里因为咱们要改变根节点，应该传入的是根节点的地址，所以得拿二级指针接收//递归出口if ((*root) == NULL){return;}//自叶向根方向的释放//如果先释放的话，就找不到叶子节点了BinaryTreeDestory(&((*root)->left));BinaryTreeDestory(&((*root)->right));free(*root);*root = NULL;
}所有测试代码：
#include"BinaryTree.h"
void test()
{//建树BTnode* nodeA=BTbuybode('A');BTnode* nodeB = BTbuybode('B');BTnode* nodeC = BTbuybode('C');BTnode* nodeD = BTbuybode('D');BTnode* nodeE = BTbuybode('E');nodeA->left = nodeB;nodeA->right = nodeC;nodeB->left = nodeD;nodeC->left = nodeE;BTnode* root = nodeA;//计算节点个数int size = 0;BinaryTreeSize(root, &size);cout <<"节点个数:"<< size<< endl;//计算叶子节点个数cout << "叶子节点个数:" << BinaryTreeLeafSize(root) << endl;//计算第三层节点个数cout << "第三层节点个数:" << BinaryTreeLevelKSize(root, 3) << endl;//计算二叉树深度cout<<"二叉树深度："<< BinaryTreeDeep(root) << endl;//查找值为E的节点BTnode* node = BinaryTreeFind(root, 'E');if (node)//已找到{cout << "已找到该节点" << endl;}else{cout << "未找到该节点" << endl;}//查找值为G的节点BTnode* node1 = BinaryTreeFind(root, 'G');if (node1)//已找到{cout << "已找到该节点" << endl;}else{cout << "未找到该节点" << endl;}//前序遍历BinaryTreePrevOrder(root);cout << endl;// 二叉树中序遍历BinaryTreeInOrder(root);cout << endl;//后序遍历BinaryTreePostOrder(root);cout << endl;//广度优先遍历BinaryTreeLevelOrder(root);cout << endl;//是否为完全二叉树if (BinaryTreeComplete(root)){cout << "是完全二叉树" << endl;}else{cout << "不是完全二叉树" << endl;}//二叉树的销毁BinaryTreeDestory(&root);
}
int main()
{test();return 0;
}测试结果：
2、二叉树的静态模拟实现
之前我们介绍堆的时候建堆用的是vector数组，其实静态建树一共有两个方式。一个是vector数组，一个是链式前向星。二叉树当然也可以用这两个方法建，但是呢对于二叉树来说有一个特殊的方法来建树。
我们创建两个足够大数组，这两个数组分别记录着下标为k的左右节点的值。其中这个k是当前这个节点的值。咱们建树的时候都默认根节点的值为1.
#include<iostream>
#include<queue>
using namespace std;
const int N = 1e4 + 10;
int l[N], r[N];
queue<int> q;
void bfs()
{q.push(1);while (q.size()){int v = q.front();cout << v << " ";q.pop();//由于二叉树的存储找不到当前节点的父节点（也就是不能向上查找）//所以不需要bool数组标记if(l[v]){q.push(l[v]);}if(r[v]){q.push(r[v]);}}
}
void dfs1(int v)
{cout <<v<<" ";if (l[v]) dfs1(l[v]);if (r[v]) dfs1(r[v]);
}
void dfs2(int v)
{if (l[v]) dfs2(l[v]);cout << v << " ";if (r[v]) dfs2(r[v]);
}
void dfs3(int v)
{if (l[v]) dfs3(l[v]);if (r[v]) dfs3(r[v]);cout << v << " ";
}
int main()
{//建二叉树int n;cin >> n;//节点个数cin >> l[1] >> r[1];//l[],r[]分别存储当前节点的左右孩子，0代表没有该孩子 for(int i=2;i<=n;i++)//循环n-1次{cin >> l[i] >> r[i];}//二叉树新增的深度优先遍历方式//前序遍历dfs1(1);cout << endl;//中序遍历dfs2(1);cout << endl;//后序遍历dfs3(1);cout << endl;//宽度优先遍历bfs();
}我们可以发现他的各种遍历的思路是和咱们动态实现一样的。
二叉树练习题：题海拾贝：二叉树的模拟题-CSDN博客
题海拾贝：[USACO3.4] 美国血统AmericanHeritage（求先序排列问题）-CSDN博客
题海拾贝：[JLOI2009] 二叉树问题-CSDN博客
好了，今天的内容就分享到这，我们下期再见！