二叉树中求度为2的结点的个数

要求

编写算法，在以二叉链表存储的二叉树中，求度为2的结点的个数。

思路

1. 首先先定义一个count变量来记录结果
2. 如果该结点为所求结点：
   - count++
   - 统计左子树，并加到count中
   - 统计右子树，并加到count中
3. 如果该结点不是所有结点：
   - 统计其左子树，并加到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;
}

交换二叉树的左右子树

要求

编写算法，在以二叉链表存储的二叉树中，交换二叉树各结点的左右子树。

思路

1. 首先先判断遍历到的这个结点是否为空
2. 判断该结点是否是孩子
3. 如果有孩子：
   - 定义一个中间变量来交换左孩子和右孩子
   - 通过递归的方法分别以左孩子和右孩子作为下一个根节点
4. 如果没有孩子：
   - 也就是两个孩子都是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);
	}
}

二叉树中先序输出各结点及其层次

要求

编写算法，在以二叉链表存储的二叉树中，按先序次序输出各结点的内容及相应的层次数，要求以二元组的形式输出。（输出格式参见样例）

思路

1. 首先判断当前结点是否为空
   - 如果该结点为空，无需处理，返回即可
2. 由于是按照先序遍历，所以先进行输出再进行遍历其左子树和右子树
3. 通过递归的方法分别处理该结点的左孩子和右孩子，同时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);
}