要求二叉树按二叉链表形式存储，编写算法实现：(1)建立二叉树的算法。(2)判别给定的二叉树是否是完全二叉树的算法。(完全二叉树的定义为：深度为K，具有N个结点的二叉树的每个结点都与深度为K的满二叉树中编号从1～N的结点一一对应。此题以此定义为准)
typedefstructBiNode{ElemTypedata；BiNode*lchild：BiNode*rchild：}*BiTree；BiTreeCreat()／／建立二叉树的二叉链表形式的存储结构{ElemTypex；BiTreebt；scanf(“％d”＆x)；／／本题假定结点数据域为整型if(x==0)bt=null；elseif(x>0){bt=(BiNode*)malloc(sizeof(BiNode))；bt一>data=x；bt一>1child=ereat()；bt->rchild=creat()；}elseerror(”输入错误”)；return(bt)；}／／结束BiTreeintJudgeComplete(BiTreebt)／／判断二叉树是否是完全二叉树如是返回1否则返回0{inttag=0；BiTreeP=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)return0；／／前边已有结点为空本结点不空elsetag=1；／／首次出现结点为空if(p一>rchild&&!tag)Queueln(Qp->rchild)；／／右子女人队elseif(p->rchild)return0；elsetag=1；}／／whilereturn1；}／／JudgeC0mplete此问题考查的知识点是二叉树的建立算法。二叉树是递归定义的，以递归方式建立最简单。判定是否是完全二叉树，可以使用队列，在遍历中利用完全二叉树“若某结点无左子女就不应有右子女”的原则进行判断。完全二叉树证明还有很多方法。判断时易犯的错误是证明其左子树和右子数都是完全二叉树，由此推出整棵二叉树必是完全二叉树的错误结论。
举一反三
内容
- 0
完全二叉树一定是二叉平衡树
- 1
某个二叉查找树（即二叉排序树）中进行查找时，效率最差的情形是该二叉查找树是（）。 A: 完全二叉树 B: 平衡二叉树 C: 单枝树 D: 满二叉树
- 2
要求二叉树按二叉链表形式存储。(1)写一个建立二叉树的算法。(2)写一个判别给定的二叉树是否是完全二叉树的算法。
- 3
如果一棵二叉树的左右子树都是二叉查找树,则该二叉树也是二叉查找树。( ) A: 对 B: 错
- 4
若二叉搜索树是有N个结点的完全二叉树，则不正确的说法是：（）