要求二叉树按二叉链表形式存储。 （1)写一个建立二叉树的算法。 （2)写一个判别给定的二叉
-
正确答案：二叉树是递归定义的以递归方式建立最简单。判定是否是完全二叉树可以使用队列在遍历中利用完全二叉树“某结点无左孩子则更无右孩子”的原则进行判断。 算法如下： BinTree Creat( ){ //建立二叉树的二叉链表形式的存储结构 ElemType x； BinTree*x： seanf(“%ElemType”&x)； if(x==NULL) bt=NULL； else{ bt=(BinNode*)malloc(sizeof(BinNode))； bt->data=x： bt->lehild=Creat( )； bt->rchild=Creat( )； } else error(“错误”)； return bt； }//endCreat int JudgeComplete(BinTree bt){ //判断二叉树是否是完全二叉树如果是返回1否则返回0 int tag=0； BinTree p=bt； Queue Q； //Q是队列元素为二叉树结点指针 if(p=NULL) return 1； Enqueue(Qp)； while(!QueueEmpty(Q)){ p=Dequeue(Q)； if(p->lchild&&!tag) Enqueue(Q．p->lehild)； //左孩子入队列 else if(p->lchild) //前面已有结点为空本结点不空 return 0； else tag=1； if(p->rchild&＆!tag) Enqueue(Qp->rchild)； else if(p->rchild) return 0； else tag=1； }//endwhile return 1； }
判别完全二叉树还有其他方法，考生容易犯的错误是证明该二叉树左子树和右子树都是完全二叉树，由此推出整棵二叉树必是完全二叉树。考生可自己思考为什么错。