PAGEPAGE3三、算法题:编写一算法，打印出一棵二叉树中所有非终端结点的值，并统计非终端结点的个数。(二叉树以二叉链表存储，根指针为bt)答:intT1(bitreptrbt)/*求二叉树bt中非叶结点的数目*/{if(bt==NULL)||(bt->lchild==NULL&&bt->rchild==NULL)return(0);/*树空或只有一个根结点时*/else{printf(bt->data);/*输出非终端结点值*/n=T1(bt->lchild);/*求左子树的非终端结点数目*/m=T1(bt->rchild);/*求右子树的非终端结点数目*/return(m+n+1);/*返回总的非终端结点数*/}}若二叉树用二叉链表表示，试完成下列要求：1）写出二叉树的二叉链表bitreptr高级语言的类型说明；2）编写一算法，统计一棵二叉树的所有结点个数。答:1)二叉链表的类型说明：typedefstructbtnode{intdata;structbtnode*lchild,*rchild;}*bitreptr;2)算法：intT2(bitreptrbt){/*求二叉树bt中结点的数目*/if(bt==NULL)return(0);else{n=T2(bt->lchild);/*求左子树的数目*/m=T2(bt->rchild);/*求右子树的数目*/return(m+n+1);}}现二叉排序树用二叉链表表示，试完成下列要求：1）简述二叉排序树的性质；2）编写算法将二叉排序树中各结点键值按减序打印出来。答:(1)二叉排序树的性质：中根遍历一棵二叉排序树所得的是键值的递增序列；(2)voidT3(bitreptrt)/*将二叉排序树中各结点键值按减序打印出来*/{if(t!=NULL){T4(t->rchild);printf(t->key);T3(t->lchild);}}若二叉树用二叉链表表示，试完成下列要求：1）写出二叉树的二叉链表bitreptr高级语言的类型说明；2）编写一算法计算一棵二叉树中所有度为2的结点个数（可采用递归算法描述）。答:1)二叉链表的类型说明：typedefstructbtnode{intdata;structbtnode*lchild,*rchild;}*bitreptr;2)算法：intT4(bitreptrBT)/*统计二叉树BT中所有度为2的结点的数目*/{if(BT==NULL)return(0);elseif(BT->lchild!=NULL&&BT->rchild!=NULL)return(T4(BT->lchild)+T4(BT->rchild)+1);elsereturn(T4(BT->lchild)+T4(BT->rchild));}若二叉树用二叉链表表示，试完成下列要求：1）写出二叉树的二叉链表bitreptr高级语言的类型说明；2）编写一算法计算一棵二叉树的叶子总数（可采用递归算法描述）。答:1)二叉链表的类型说明：typedefstructbtnode{intdata;structbtnode*lchild,*rchild;}*bitreptr;2)算法：intT5(bitreptrbt){/*求二叉树bt中叶结点的数目*/if(bt==NULL)return(0);elseif(bt->lchild==NULL&&bt->rchild==NULL)return(1);else{n=T5(bt->lchild);/*求左子树的叶子数目*/m=T5(bt->rchild);/*求右子树的叶子数目*/return(m+n);}}若二叉树用二叉链表表示，试完成下列要求：1）写出二叉树的二叉链表bitreptr高级语言的类型说明；2）另设二叉链表中每个结点的数据域中存放一个整数，试编写一个算法，求此二叉树上数据域的值为100的结点个数。（可采用递归算法描述）。答:1）二叉链表的类型说明：typedefstructbtnode{intdata;structbtnode*lchild,*rchild;}*bitreptr;2）算法：intT6(bitreptrbt)/*求二叉树bt结点数据域值为100的结点的数目*/{if(bt==NULL)return(0);elseif(bt->data=100)return(T6(bt->lchild)+T6(bt->rchild)+1);elsereturn(T6(bt->lchild)+