有m个叶子的完全二叉树最多有多少个节点?

这里说一下自己的答案，如果有m个叶子的完全二叉树最多有2m个节点。推导如下:

					 1
				   /   
				  2	    3
				 /	   / 
			    4    5 6   7
			  /   /  /  /
			 8  9 10 
如上图所述，假设m=8，也就是叶子节点是8个完全的二叉树，那么它最大有2*8个节点。
现在用数学方法推导:
	(1)因为第一层最多有2^(1-1) = 1个叶子节点，那么第h层最多有2^(h-1)个叶子节点。所以我们首先可以根据m来得出我们的完全二叉树可以最多有多少层:
		2^(h-2) <= m <= 2^(h-1);
首先我们找到了处于m=8在的最大的二叉树的层数是5(2^(5-2)<= m <= 2^(5-1))。
	(2)因为找到了最大的层数，因为是完全二叉树，所以倒数第二层以上的树肯定是一个满二叉树了，那么倒数二层以上的节点一共有2^(h-1)-1个节点。
	(3)那么还剩下倒数最后一层的节点数，我们只需要把它们求出来就可以知道所有的节点了。那么我们假设最后一层有x个节点。但是请注意这个x必定是一个奇数。为什么呢？假设最后一层的节点数是一个偶数的话。就比方说上面图的8,9两个节点，那么我完全可以在节点5下加一个左子树(因为增加一个左子树不会增加叶子节点数)，所以就可以在不增加叶子节点的情况下增加一个节点)。在拿一个例子来说:
					1
				   / 
				  2   3
				 /   /
				4  5 6  7
假设我现在是m=4，那么根据2^(h-2) <= m <= 2^(h-1)得出h=3，那么倒数第二层以前的树是满二叉树，所以有2^2-1个节点，然后最后一层因为也是个偶数，所以我完全可以在4节点下增加一个左子树，也可以保证是m=4比如下面这个图:
					1
				   / 
				  2   3
				 /   /
				4  5 6  7
			   /
			  8
所以我们得出最后一层的叶子节点数必定是一个奇数的。所以我们假设最后一层的节点数是x，那么我们可以通过(x+1)/2得出上一层不是叶子节点的个数。那么根据倒数第二层的
中所占有的节点个数是2^(h-2)。可以得出倒数第二层中剩余的叶子节点数是
		2^(h-2)-(x+1)/2;
那么又因为一共有m个叶子节点；所以可以得出:
		2^(h-2)-(x+1)/2 + x = m;
		//两边同时乘以2得出
		2^(h-1)-1+x=2m;
		推出
		x = 2m-2^(h-1)+1;
		然后加上倒数第二层总的节点个数:
		x+2^(h-1)-1 = 2m-2^(h-1)+1+2^(h-1)-1=2m
所以推出:
		如果有m个叶子节点的完全二叉树，那么其最多有2m个节点

最后

以上就是紧张钢笔为你收集整理的有m个叶子的完全二叉树最多有多少个节点?的全部内容，希望文章能够帮你解决有m个叶子的完全二叉树最多有多少个节点?所遇到的程序开发问题。

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