问答题 已知深度为h的二叉树,以一维数组BT[0..2 h -2]作为其存储结构,试编写一算法,求该二叉树中叶子结点的个数,为简单起见,设二叉树中元素结点为非负整数,要求写出算法基本思想及相应的算法。【中南大学2003八(10分)】
【正确答案】正确答案:按完全二叉树形式顺序存储二叉树时,无元素的位置要当作“虚结点”。根据本题“二叉树中元素结点为非负整数”,可以设虚结点为负数。设结点序号为i(根结点编号为0),则当ih-1)/2(最后一个分支结点)时,若其2f+1和2i+2位置为虚结点,则i为叶子结点;当i≥(2 h -1)/2时,若i位置不是虚结点,则必为叶子结点。核心语句段如下: for(i=0;i k一1 if(i0)num++; //存储在数组后一半的元素是叶子结点
【答案解析】