编写算法判断该二叉树是否是一棵平衡二叉树。

[问答题]

平衡二叉树是任意结点左右子树的深度相差不超过1的二叉树，例如下图所示的二叉树就是一棵平衡二叉树。

已知一棵二叉树采用二叉链表存储，结点结构为（left,data,right），root指向根节点。

算法题要求：

（1）概要描述算法的思想；

（2）在关键的地方给出简明的注释；

（3）算法可使用C或ADL语言描述。

小杨你好

bool IsAVL(BianryTreeNode* pRoot, int& height)
{
	if(pRoot == 0)
		return true;
	
	int leftHeight;
	bool leftResult = IsAVL(pRoot->left, leftHeight);
	int rightHeight;
	bool rightResult = IsAVL(pRoot->right, rightHeight);
	if(leftResult && rightResult && abs(leftHeight - rightHeight) <= 1)
	{
		height = max(leftHeight, rightHeight) + 1;
		return true;
	}
	else
	{
		height = max(leftHeight, rightHeight) + 1;
		return false;
	}
}

发表于 2017-09-07 20:56:49 回复(0)