学步园

昨天面试，有一道题是：完全二叉树，知道总节点数，计算叶子结点的数量。由于当时要求在纸上写代码，没有实际运行，所以回来后他这个代码调试一下.

// Challenge8.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "math.h"


//问题：完全二叉树知道总节点数, 求叶子节点的数量

//求某层节点个个数
int levelnode(int deep)
{
	int sum = 1;
	for(int i = 0; i < deep; i++)
	{
		sum *= 2;
	}
	return sum;
}

//计算叶子节点的数量
int leafnode(int allnode)
{
	int deep = 0;
	while (allnode > 0)
	{
		allnode -= levelnode(deep);
		deep++;
	}
	int leaf = levelnode(deep - 1) + allnode;
	return leaf;
}


int _tmain(int argc, _TCHAR* argv[])
{
	printf("leafnode=%d\n", leafnode(17));

	getchar();
	return 0;
}