完全二叉树的结点个数

完全二叉树的结点个数

思路：

首先通过一直遍历节点的左节点，一直到最左下的结点，这就是二叉树的高度h，之后从根节点的右子树出发，找右子树的最左结点。
1.若右子树的最左结点处在h层上，说明根节点的左子树是一个高度为h-1的满二叉树，结点个数为2^(h-1)-1，之后+1（根节点），递归遍历根节点右子树。
2.若右子树的最左结点不在h层上，说明根节点的右子树是一个高度为h-2的满二叉树，同样上述计算，然后递归根节点的左子树。

代码如下：

public static int nodeNum(Node head)//主函数
{
	if(head == null)
		return 0;
	return bs(head, 1, mostleftlevel(head, 1));
} 

public static int bs(Node node, int l, int h)//递归求解的过程
{
	if(l == h)
	{
		return 1;
	}
	if(mostleftlevel(node.right, l+1) == h)
	{
		//若根节点右子树的高度在h时，则左子树为满二叉树再加上根节点，在加上递归右子树的节点数，即为下式
		return (1 << (h-l)) + bs(node.right, l+1, h);
	}
	else
	{
		return (l << (h-l-1)) + bs(node.left, l+1, h);
	}
}

//返回最左结点所在的高度
public static int mostleftlevel(Node node, int level)
{
	while(node != null)
	{
		level++;
		node = node.left;
	}
	return level-1;
}

最后

以上就是怕黑煎饼为你收集整理的完全二叉树的结点个数的全部内容，希望文章能够帮你解决完全二叉树的结点个数所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。