【数据结构】C语言二叉树中求度为2的结点的个数、交换二叉树的左右子树、二叉树中先序输出各结点及其层次
二叉树中求度为2的结点的个数
要求
编写算法，在以二叉链表存储的二叉树中，求度为2的结点的个数。
思路
- 首先先定义一个
count变量来记录结果 - 如果该结点为所求结点：
- count++
- 统计左子树，并加到count中
- 统计右子树，并加到count中 - 如果该结点不是所有结点：
- 统计其左子树，并加到count中
- 统计其右子树，并加到count中
函数代码
int Degree2(BiTree bt) {
int count = 0;//设置count来记录度为2的结点个数
if (bt == NULL) {
return 0;//如果该结点不存在则返回0
}
//如果该结点的度为2，即为所求结点
if (bt->Lchild && bt->Rchild) {
count++;//count加一
//递归，分别计算该结点的左子树和右子树中满足条件的结点个数
count += Degree2(bt->Lchild);
count += Degree2(bt->Rchild);
}
//如果该结点为叶子结点或者度为1的结点
else {
//统计该结点的左子树和右子树中满足条件的结点个数
count += Degree2(bt->Lchild);
count += Degree2(bt->Rchild);
}
return count;
}
交换二叉树的左右子树
要求
编写算法，在以二叉链表存储的二叉树中，交换二叉树各结点的左右子树。
思路
- 首先先判断遍历到的这个结点是否为空
- 判断该结点是否是孩子
- 如果有孩子：
- 定义一个中间变量来交换左孩子和右孩子
- 通过递归的方法分别以左孩子和右孩子作为下一个根节点 - 如果没有孩子：
- 也就是两个孩子都是NULL，无需进行交换。
函数代码
void SwapLR(BiTree bt) {
//如果该结点为空，则返回
if (bt == NULL) {
return;
}
//如果该结点不为空，即有左结点或者右结点
if (bt->Lchild || bt->Rchild) {
//定义一个同结点类型相同的中间变量来实现左结点和右结点的交换
BiTree tempNode = bt->Lchild;
bt->Lchild = bt->Rchild;
bt->Rchild = tempNode;
//遍历该结点的左子树
SwapLR(bt->Lchild);
//遍历该结点的右子树
SwapLR(bt->Rchild);
}
}
二叉树中先序输出各结点及其层次
要求
编写算法，在以二叉链表存储的二叉树中，按先序次序输出各结点的内容及相应的层次数，要求以二元组的形式输出。（输出格式参见样例）
思路
- 首先判断当前结点是否为空
- 如果该结点为空，无需处理，返回即可 - 由于是按照先序遍历，所以先进行输出再进行遍历其左子树和右子树
- 通过递归的方法分别处理该结点的左孩子和右孩子，同时lay+1表示进入了二叉树的下一层
函数代码
void PreOrderLayer(BiTree bt, int lay) {
//如果该结点为空，无需处理，返回即可
if (bt == NULL) {
return;
}
//按照输出格式进行打印
printf("(%c,%d)", bt->data, lay);
//通过递归的方法分别处理该结点的左孩子和右孩子
//同时lay+1表示进入了二叉树的下一层
PreOrderLayer(bt->Lchild, lay + 1);
PreOrderLayer(bt->Rchild, lay + 1);
}
原文地址：https://blog.csdn.net/samroom/article/details/143694611
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！