当前位置: 首页 > >

如何判断一颗二叉树是否是完全二叉树?

发布时间:


算法思想:完全二叉树满足:若节点的左孩子为空,则右节点必为空,故只要判断,前面已经出现空节点,则以后的节点也必须为空。


?


bool Judge(BTree *T)
{
?? ?queue Q;
?? ?Q.push(T);
?? ?BTree* p;
?? ?
?? ?bool flag = true;
?? ?while(!Q.empty())
?? ?{
?? ??? ?p = Q.front();
?? ??? ?Q.pop();
?? ??? ?
?? ??? ?if(p->lchild)
?? ??? ?{
?? ??? ??? ?if(flag)?
?? ??? ??? ??? ?Q.push(p->lchild);
?? ??? ??? ?else ? ? ? ? ? ?//前面已经有空节点,但是本节点不为空,则不是完全二叉树?
?? ??? ??? ??? ?return false;
?? ??? ?}?
?? ??? ?else
?? ??? ??? ?flag = false; ? ?//第一次出现左子树为空?
?? ??? ??? ??
?? ??? ?if(p->rchild)
?? ??? ?{
?? ??? ??? ?if(flag)
?? ??? ??? ??? ?Q.push(p->rchild);?? ?
?? ??? ??? ?else ? ? ? ? ? ?//前面已经有空节点,但是本节点不为空,则不是完全二叉树 ?
?? ??? ??? ??? ?return false;
?? ??? ?}
?? ??? ?else ? ? ? ? ? ? ? //第一次出现右子树为空?
?? ??? ??? ?flag = false;
?? ?}?? ?
?? ?
?? ?return true;?
}?




友情链接: 时尚网 总结汇报 幼儿教育 小学教育 初中学习资料网