判断是否是平衡二叉树--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 <iostream>
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) <= 1) {
            height = max(leftHeight, rightHeight) + 1;  //取左右子树的较大者，并加上根节点
            return true;
        }
    }
    return false;

}
// 插入数据
void insertBST(BiNode*& bt, int key)
{
    if (bt == NULL)
    {
        bt = new BiNode;
        bt->data = key;
        bt->lchild = NULL;
        bt->rchild = NULL;
    }
    else
    {
        if (key < bt->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 << bt->data<<" ";
        Display(bt->rchild);

    }
}
int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        int num;
        cin >> num;
        insertBST(root, num);
    }
   /* cout << "inorder\n";
    Display(root);*/
    bool flag = false;
    int height;
    flag = isBalance(root,height);
    if (flag)
    {
        cout << "是二叉平衡树" ;
    }
    else
    {
        cout << "不是二叉平衡树" ;
    }
    return 0;
}