博客

很多书上其实都有提到和该算法。但是经过自己的学习我自己想到一个算法。算是结合了其中的优点吧。

算法描述：该算法递归去统计结点个数。值得一提的是该系列算法都是统计根结点以下的符和条件的结点的个数进行了加和。免去的设置全局变量和void的类型的函数。

int	CountNodes(LBTree* lbt)
{
	int n = 0;
	if (lbt != NULL)
	{
		++n;
		n += CountNodes(lbt->lchild);
		n += CountNodes(lbt->rchild);
	}
	return n;
}
 
int CountLeaves(LBTree* lbt)
{
	int n = 0;
	if (lbt != NULL)
	{
		if (lbt->lchild == NULL && lbt->rchild == NULL)
			++n;
		n += CountLeaves(lbt->lchild);
		n += CountLeaves(lbt->rchild);
	}
	return n;
}
 
int CountSingleNode(LBTree* lbt)
{
	int n = 0;
	if (lbt != NULL)
	{
		if ((lbt->lchild == NULL && lbt->rchild != NULL) || (lbt->rchild == NULL && lbt->lchild != NULL))
			++n;
		n += CountSingleNode(lbt->lchild);
		n += CountSingleNode(lbt->rchild);
	}
	return n;
}
 
int	CountDoubleNode(LBTree* lbt)
{
	int n = 0;
	if (lbt != NULL)
	{
		if (lbt->lchild != NULL && lbt->rchild != NULL)
			++n;
		n += CountDoubleNode(lbt->lchild);
		n += CountDoubleNode(lbt->rchild);
	}
	return n;
}

框架都一样，只是判断结点是有不同的。这个框架适用于很多场景，希望读者思考。