一、实验内容

编写递归算法计算二叉树中度为1
⭐ ⭐ ⭐

二、问题分析

通过二叉树结构的递归特性来实现。若某结点的左右子树都不为空，则该结点拥有的度为1的结点为左右孩子结点拥有的之和；若某结点的左子树为空，右子树不为空，则该结点拥有的度为1的结点为该结点自身加上，右子树拥有的之和；同理，某结点的右子树为空，左子树不为空，则该结点拥有的度为1的结点为该结点自身加上，右子树拥有的之和；若该结点没有左右子树，则返回0。

三、解答

1
2
3
4
5
typedef struct Node {
	DataType data;//数据域
	struct Node *leftchild;//左子树指针
	struct Node *rightchild;//右子树指针
}BTNode;
1
2
3
4
5
6
7
8
9
10
11
12
13
14

//使用递归
//计算二叉树中度为1的结点总数
int singleNodes(BTNode *b) {
	if (b==NULL) {
		return 0;
	}
	if ((b->leftchild == NULL && b->rightchild != NULL) || (b->leftchild != NULL && b->rightchild == NULL))
	{
		return 1 + singleNodes(b->leftchild) + singleNodes(b->rightchild);
	}
	return singleNodes(b->leftchild) + singleNodes(b->rightchild);
}