首页 > 试题广场 >

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

[问答题]
平衡二叉树是任意结点左右子树的深度相差不超过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)