设计师a 网站,cms网站群管理系统,广告制作公司起名,wordpress 主题 中国风Hello大家好#xff0c;我是但凡#xff01;很高兴我们又见面啦#xff01; 眨眼间已经到了2024年的最后一天#xff0c;在这里我要首先感谢过去一年陪我奋斗的每一位伙伴#xff0c;是你们给予我不断前行的动力。银蛇携福至#xff0c;万象启新程。蛇年新春之际#xf… 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* nodeABTbuybode(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(k1){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)
{queueBTnode* 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)
{queueBTnode* q;//创建队列q.push(root);while (!q.empty()){BTnode* tmp q.front();q.pop();if (tmpNULL){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;
} 所有测试代码
#includeBinaryTree.h
void test()
{//建树BTnode* nodeABTbuybode(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.
#includeiostream
#includequeue
using namespace std;
const int N 1e4 10;
int l[N], r[N];
queueint 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 i2;in;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博客 好了今天的内容就分享到这我们下期再见
