什么叫做平衡二叉树？
有12个节点的平衡二叉树的最大深度是 A.4 B.5 C.6 D.3 书上说平衡二叉树是对最佳二叉树的平衡处理。但是处理完后倒数第二层可能不是充满的了，那么什么样的树才算是平衡二叉树呢？上面的选择题又应该如何解答呢？
平衡二叉树的左右子树都是平衡二叉树，并且左右子树的深度的差值的绝对值不超过1。平衡二叉树上的任何节点的左子树和右子树的深度的差值只能是－1、0或1。 对于该题目： 首先一个完全二叉树必然是平衡二叉树。对于深度为N的完全二叉树一共有2^N-1个节点。
当N=3时，共有2^3-1=7个节点； 当N=4时，共有2^4-1=15个节点； 当N=5时，共有2^5-1=31个节点； 当N=6时，共有2^6-1=63个节点。 而一颗平衡二叉树的节点数必然小于等于同深度的完全二叉树，答案D排除。
根据平衡二叉树的性质，不难得到，对于N>2的平衡二叉树，其前N-2层必然是完全二叉树。所以对于深度为6的平衡二叉树至少应有15个节点。答案C排除。 很显然对于答案A,12个节点可以构成一个平衡二叉树，问题是其是不是最大深度,问题就归结到答案B是否成立。
对于答案B,深度为5，前3层为完全二叉树，用去节点7个，还剩5个节点。剩余的5个节点要加到第三层的4个节点上，保持左右子树的平衡。很显然这是可以的。所以选B。 最后给出一个答案示例，如图： 。
答：详情>>
