数据结构考研分类复习真题 第六章 答案 (五)[5]

．[题目分析]二叉树是递归定义的以递归方式建立最简单判定是否是完全二叉树可以使用队列在遍历中利用完全二叉树若某结点无左子女就不应有右子女的原则进行判断

BiTree Creat() //建立二叉树的二叉链表形式的存储结构

{ElemType xBiTree bt;

scanf(%d&x); //本题假定结点数据域为整型

if(x==) bt=null;

else if(x>)

{bt=(BiNode *)malloc(sizeof(BiNode));

bt>data=x; bt>lchild=creat(); bt>rchild=creat();

}

else error(输入错误)

return(bt);

}//结束 BiTree

int JudgeComplete(BiTree bt) //判断二叉树是否是完全二叉树如是返回否则返回

{int tag=; BiTree p=bt Q[]; // Q是队列元素是二叉树结点指针容量足够大

if(p==null) return ();

QueueInit(Q); QueueIn(Qp); //初始化队列根结点指针入队

while (!QueueEmpty(Q))

{p=QueueOut(Q); //出队

if (p>lchild && !tag) QueueIn(Qp>lchild); //左子女入队

else {if (p>lchild) return ; //前边已有结点为空本结点不空

else tag=; //首次出现结点为空

if (p>rchild && !tag) QueueIn(Qp>rchild); //右子女入队

else if (p>rchild) return ; else tag=;

} //while

return ; } //JudgeComplete

[算法讨论]完全二叉树证明还有其它方法判断时易犯的错误是证明其左子树和右子数都是完全二叉树由此推出整棵二叉树必是完全二叉树的错误结论

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []