参考答案

正确答案：typedef struct BiNode{ElemType data；BiNode*lchild：BiNode*rchild：}*BiTree；BiTree Creat()／／建立二叉树的二叉链表形式的存储结构{ElemType x；BiTree bt；scanf(“％d”＆x)；／／本题假定结点数据域为整型if(x==0)bt=null；else if(x>0){bt=(BiNode*)malloc(sizeof(BiNode))；bt一>data=x；bt一>1child=ereat()；bt->rchild=creat()；}else error(”输入错误”)；return(bt)；}／／结束BiTreeint JudgeComplete(BiTree bt)／／判断二叉树是否是完全二叉树如是返回1否则返回0{int tag=0；BiTree P=btQ[ ]；／／Q是队列元素是二叉树结点指针容量足够大if(P==null)return(1)；QueueInit(Q)；QueueIn(QP)；／／初始化队列根结点指针入队while(!QueueEmpty(Q)){P=QueueOut(Q)；／／出队if(p一>lchild＆＆!tag)QueueIn(Qp->lchild)；／／左子女人队else{if(p一>lchild)return 0；／／前边已有结点为空本结点不空else tag=1；／／首次出现结点为空if(p一>rchild&&!tag)Queueln(Qp->rchild)；／／右子女人队else if(p->rchild)return 0；else tag=1；}／／whilereturn 1；}／／JudgeC0mplete
此问题考查的知识点是二叉树的建立算法。二叉树是递归定义的，以递归方式建立最简单。判定是否是完全二叉树，可以使用队列，在遍历中利用完全二叉树“若某结点无左子女就不应有右子女”的原则进行判断。完全二叉树证明还有很多方法。判断时易犯的错误是证明其左子树和右子数都是完全二叉树，由此推出整棵二叉树必是完全二叉树的错误结论。