Question

判断是否为完全二叉树

输入一串字符串，建立二叉树的二叉链表，判断该二叉树是否是一棵完全二叉树

请把这个的算法的c语言程序写出来吧，谢谢了

Answer 1

建立二叉树有点复杂，可以找书看看，一般数据结构的书上是会有的吧。
判断是否完全二叉树的代码如下（直接根据完全二叉树定义编写的）：

//假设之前定义的二叉树的节点类型为struct BT_Node。
/*下面的函数判断子树sub_root是否为完全二叉树，是则返回true,否则返回false.同时，将子树的高度通过pHight返回。这是一个辅助函数。
*/
bool __IsBalanced(BT_Node* sub_root,int *pHight)
{
int lHight,rHight;//左、右子树的高度。
bool result1,result2;
if(sub_root == NULL){
*pHight = 0;
return true;
}
result1 = __IsBalanced(sub_root->lChild,&lHight);
result2 = __IsBalanced(sub_root->rChild,&rHight);
*pHight = 1 + （lHight>rHight? lHight: rHight）;
if(result1 && result2 && lHight == rHight)
return ture;
else
return false;
}
///下面的函数判断二叉树root是否完全二叉树。
bool IsBalanced(BT_Node* root)
{
int hight;
return __IsBalanced(root,&hight);
}

Answer 2

完全二叉树(Complete
BinaryTree)
若一棵二叉树至多只有最下面的两层上结点的度数可以小于2，并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。
特点：
（1）
满二叉树是完全二叉树，完全二叉树不一定是满二叉树。
（2）
在满二叉树的最下一层上，从最右边开始连续删去若干结点后得到的二叉树仍然是一棵完全二叉树。
（3）
在完全二叉树中，若某个结点没有左孩子，则它一定没有右孩子，即该结点必是叶结点。
利用特点进行判断

Answer 3

给你讲讲方法吧，实现就自己写了。
完全二叉树(complete
binary
tree)：
若设二叉树的高度为h，除第
h
层外，其它各层
(1～h-1)
的结点数都达到最大个数，第
h
层所有的节点都连续集中在最左边，这就是完全二叉树。
判断很简单，广度优先搜索整个二叉树，一旦找一个不含有子节点或者只含有一个左子节点之后，那么后续的所有节点都必须是叶子节点。否则，该树就不是完全二叉树。
实现的时候要用到队列。