玉帝让孙悟空看守蟠桃园。到了蟠桃园土地神向孙悟空介绍仙桃树的仙桃特点,哪些三千年成熟,哪些六千年成熟,哪些九千年成熟。还介绍了其中有一片叫“桃圣”的仙桃树很特别,悬空生长,根在上,枝叶在下,树上所有树杈最多只有左右两个分支。树上仙桃要一万年成熟,它们要么长在树枝顶端,要么长在树杈上,每个仙桃都有一个编号。对于每个树杈上的仙桃来说,其左边子树上如果长有仙桃则编号都比它小,右边子树上如果长有仙桃则编号都比它大。更奇怪的是长在树杈上的仙桃虽然有糖度,但都是苦的,只有长在顶端的仙桃有甜味,尤其是仙桃糖度在7-9之间的最好、最甜。
孙悟空听了记在心里,并向土地神请教如何辨别仙桃的糖度。土地神说太上老君有一个宝物——老花镜,这个宝物一照就能知道长在顶端仙桃的糖度。孙悟空等土地神走后,去太上老君那里偷来了宝物,带上老花镜后,把所有“桃圣”区域仙桃树顶端糖度在7-9之间的仙桃摘下吃了精光。
输入:一些仙桃的编号,根据仙桃的编号构建一棵“桃圣”仙桃树(即二叉排序树),用宝物老花镜可以看出仙桃的糖度:方法是仙桃糖度就是仙桃编码模10后的结果,如编号45糖度为5,编号29糖度为9。
其中二叉排序树的定义为:
一棵空树,或者是具有下列性质的二叉树:
(1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值;
(2)若右子树不空,则右子树上所有结点的值均大于它的根结点的值;
(3)左、右子树也分别为二叉排序树;
(4)没有键值相等的结点。
例如:输入仙桃编号42 38 50 23 47 10 65 78 18 58,创建“桃圣”仙桃树如下图
糖度为7-9之间的顶端仙桃为:18,47,58,78,共4个仙桃
输出:4
第一行输入仙桃的个数M,
下一行输入指定M个数仙桃的编号
输出这棵仙桃树孙悟空能吃到糖度在7-9之间的甜桃子数量。