【数据结构】平衡二叉树的判断

平衡二叉树(Balanced Binary Tree)具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。

问题分析

判断一棵树是否为平衡二叉树我们用递归方法实现。
首先考录特殊情况,如果树为空则是平衡二叉树,否则判断它的左子树是不是平衡二叉树,如果是在判断右子树是不是平衡二叉树,判断的同时记录左右子树的高度,最后判断该树是否为平衡二叉树

算法步骤

1 如果为空树,返回真
2 递归判断左子树是否为平衡二叉树,同时记录左子树高度lheight
3 递归判断右子树是否为平衡二叉树,同时记录右子树高度rheight
4 判断此二叉树是否为平衡二叉树,即abs(lheight-rheigh)<2?如果是树的高度Height为左右子树中较大者加上1(根高度为1)
5 否则返回假

代码如下

bool BinaryTree<T>::IsBalancedBT(BinTreeNode<T> *subTree,int& height)
{
	//递归算法实现判断二叉树是否为平衡二叉树
	int lh , rh;
	if (subTree == nullptr)
	{
		height = 0;
		return true;
	}
	bool l = IsBalancedBT(subTree->leftChild, lh);  //递归判断左子树是否为平衡二叉树
	bool r = IsBalancedBT(subTree->rightChild, rh); //递归判断右子树是否为平衡二叉树
	if (l&&r)//如果左子树和右子树为平衡二叉树
	{
		if (abs(lh - rh) <= 1)        //判断整个二叉树是不是平衡二叉树
		{
			height = 1 +(lh > rh ? lh : rh); //如果是,树的高度为左右子树中高度较大的加上1
			return true;                   //该树为平衡二叉树			}
		}
	}
	return false;
}
原文地址:https://www.cnblogs.com/muyefeiwu/p/11743522.html