判断是否是平衡二叉树–c++【做题记录】
【问题描述】
设计算法判断一棵树是否是一棵平衡二叉树。
输入一组数据,按顺序构造出一个二叉排序树,不要平衡化,直接插入数据。判断树是否是平衡二叉树。
【参考算法】
递归算法
bool isBalance(BiNode *bt, int &height) //注意,将height用引用传进来,被调函数可以向主调函数传递计算出来的高度值
递归出口:
若为空,高度就为0,平衡
递归部分:
左递归判断左子树平衡吗?
右递归判断右子树平衡吗?
计算以bt为根的这棵树的高度。是root的左子树、右子树中的较高者加上root本身这个结点(即加1)
假设左子树平衡,右子树平衡,而且左右子树高度差小于等于1,则平衡
【输入输出】
第一行输入数据的个数n
第二行输入n个int型数据
第三行输出是否是平衡二叉树。
【测试数据】
11
38 12 34 56 13 6 98 3 17 40 78
不是二叉平衡树
3
12 11 13
是二叉平衡树
【代码】
#include
using namespace std;
struct BiNode
{
int data;
BiNode* lchild, * rchild;
};
BiNode* root=NULL;
//求二叉树的深度
int treeHeight(BiNode* bt)
{
if (bt == NULL)
return 0;
else
{
int h1 = treeHeight(bt->lchild);
int h2 = treeHeight(bt->rchild);
return h1 > h2 ? h1 + 1 : h2 + 1; // 取左右子树中的较高者,并加上根节点
}
}
// 判断是否为平衡二叉树
bool isBalance(BiNode* bt, int& height) {
if (bt == NULL) {
height = 0;
return true;
}
int leftHeight, rightHeight;
if (isBalance(bt->lchild, leftHeight) && isBalance(bt->rchild, rightHeight)) {
if (abs(leftHeight - rightHeight) data = key;
bt->lchild = NULL;
bt->rchild = NULL;
}
else
{
if (key data)
insertBST(bt->lchild, key);
else if (key > bt->data)
insertBST(bt->rchild, key);
}
}
//中序输出二叉树
void Display(BiNode* bt)
{
if (bt == NULL)
return;
else
{
Display(bt->lchild);
cout <data<rchild);
}
}
int main()
{
int n;
cin >> n;
for (int i = 0; i > num;
insertBST(root, num);
}
/* cout << "inorder
";
Display(root);*/
bool flag = false;
int height;
flag = isBalance(root,height);
if (flag)
{
cout << "是二叉平衡树" ;
}
else
{
cout << "不是二叉平衡树" ;
}
return 0;
}