【新春不断更】数据结构与算法之美：二叉树

         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博客

        好了，今天的内容就分享到这，我们下期再见！