中科新闻网川军出川抗战:判断一棵二叉树是否为完全二叉树的函数
来源：百度文库 编辑：中科新闻网 时间：2024/05/06 12:07:41
数据结构方面的问题
完全二叉树中，任意结点的左、右子树的深度都相等，所以你只需做一个后根遍历，即可知道一个二叉树是否为完全二叉树；
下面假设二叉树的结点结构是：
typedef struct _Node
{
_Node* lchild;
_Node* rchild;
}BinaryTree;
用VC编程，算法如下：
//检查二叉树是否完全二叉树，如果不是，返回0，
//否则返回二叉树的高度
int checkCompleteBinaryTree(BinaryTree* tree)
{
//叶子结点
if(tree->lchild==NULL && tree->rchild==NULL)return 1;
//缺一个子树，不是完全二叉树
if(tree->lchild==NULL || tree->rchild==NULL)return 0;
//左子树高度
int lheight=checkCompleteBinaryTree(tree->lchild);
//左子树不是完全二叉树
if(lheight==0)return 0;
//右子树高度
int rheight=checkCompleteBinaryTree(tree->rchild);
//右子树不是完全二叉树
if(rheight==0)return 0;
//左右子树高度不相同，因此不是完全二叉树
if(lheight!=rheight)return 0;
//返回二叉树的高度
return lheight+1;
}
………………