问答题
设二叉树结点结构为：(1eR，data，bf，right)。定义二叉树结点的平衡因子bf(T)=h
L
一h
R
，写一递归算法确定二又树tree中各结点的平衡因子bf,同时返回二叉树tree中非叶子结点的个数。【东南大学2005三(10分)】
【正确答案】正确答案：为避免在求每个结点的平衡因子(bf)时，都要调用求结点的左、右子树的高度，可以在遍历时将bf值暂存为结点的层次数(见第6章算法设计题第1题)。再用O(n)时间复杂度确定各结点的bf(结点左子树的层次减去右子树的层次)，要考虑无左(或右)子树的情况。
【答案解析】