题目

已知非空二叉树T，写一个算法，求度为2的结点的个数。
要求：
1、定义二叉树的抽象数据类型和型BTREE，并定义基本操作。
2、编写函数count2(BTREE T)，返回度为2的节点的个数。
3、在主函数中，构建一个二叉树，并验证所编写的算法。

代码

#include <iostream>
using namespace std;

struct node {
   
	int data;
	node* left;
	node* right;
};

typedef node* BTREE;

node* newNode(int data)  // 构造新结点
{
   
	node* tmp = new node;
	if (tmp)
	{
   
		tmp->data = data;
		tmp->left = NULL;
		tmp->right = NULL;
	}
	return tmp;
}

int count2(BTREE T)
{
   
	if (T)
		return count2(T->left) + count2(T->right) + (T->left && T->right);
	else
		return 0;
}

int main()
{
   
	BTREE root = newNode(1);
	root->left = newNode(2);
	root->right = newNode(3);
	root->left->left = newNode(4);
	root->right->left = newNode(5);
	root->right->right = newNode(6);

	cout << count2(root) << endl;
}