如何判断二叉树是否平衡

题目：输入一棵二叉树的根结点，判断该树是不是平衡二叉树。如果某二叉树中任意结点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

注：这里不考虑该二叉树是否是二叉排序树

解决要点：

1.后序遍历二叉树；

2.递归。

核心算法：

bool isBalanced(pTree pT,int *depth)
{
    if(!pT)//参数判断
    {
        *depth = 0;
        return true;
    }
    //后序遍历
    int left,right;
    if(isBalanced(pT->lChild,&left) && isBalanced(pT->rChild,&right))
    {
        int differ = left-right;
        if(differ >= -1 && differ <= 1)
        {        //记录深度
            *depth = (left > right) ? left+1 : right+1;
            return true;
        }
    }
    return false;
}
bool isBalanced(pTree root)//传入二叉树根节点
{
    int depth = 0;
    return isBalanced(root,&depth);
}

返回栏目页：http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/

完整程序：

/*********************************
判断二叉树是否是平衡二叉树
by Rowandjj
2014/7/13
*********************************/
#include<iostream>
using namespace std;
typedef struct _NODE_
{
    int data;
    struct _NODE_ *lChild;
    struct _NODE_ *rChild;
}TreeNode,*pTree;
void Create(pTree *pT)
{
    int e;
    cin>>e;
    if(e != -1)
    {
        *pT = (TreeNode*)malloc(sizeof(TreeNode));
        if(!pT)
        {
            exit(-1);
        }
        (*pT)->data = e;
        (*pT)->lChild = NULL;
        (*pT)->rChild = NULL;
        Create(&(*pT)->lChild);
        Create(&(*pT)->rChild);
    }
}
bool isBalanced(pTree pT,int *depth)
{
    if(!pT)
    {
        *depth = 0;
        return true;
    }  

    int left,right;
    if(isBalanced(pT->lChild,&left) && isBalanced(pT->rChild,&right))
    {
        int differ = left-right;
        if(differ >= -1 && differ <= 1)
        {
            *depth = (left > right) ? left+1 : right+1;
            return true;
        }
    }
    return false;
}
bool isBalanced(pTree root)//传入二叉树根节点
{
    int depth = 0;
    return isBalanced(root,&depth);
}
void travel(pTree pT)
{
    if(pT != NULL)
    {
        travel(pT->lChild);
        travel(pT->rChild);
        cout<<pT->data<<" ";
    }
}
int main()
{
    pTree pT;
    Create(&pT);
    travel(pT);
    cout<<endl;
    cout<<isBalanced(pT);
    return 0;
}

作者：csdn博客 RowandJJ

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索int
， 二叉树
， return
， 平衡二叉树
， 二叉树深度遍历可视化
， 平衡树
， 二叉树排序
， pt
， 平衡二叉树课程设计
right
如何判断平衡二叉树、判断是否为平衡二叉树、判断是否是平衡二叉树、判断平衡二叉树、判断平衡二叉树 java，以便于您获取更多的相关知识。