判断二叉树是否是平衡二叉树
程序员文章站
2022-05-20 10:16:02
...
平衡二叉搜索树(Balanced Binary Tree)具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。
思路:如果一颗二叉树的所有子树都是平衡二叉树,它一定是平衡二叉树。
#include <bits/stdc++.h>
using namespace std;
typedef struct BNode* BTree;
struct BNode
{
int data;
BTree left;
BTree right;
};
void Insert(BTree &t,int data){
if(!t){
BTree p=(BTree)malloc(sizeof(BTree));
p->data=data;
p->left=NULL;
p->right=NULL;
t=p;
}
else if(data<t->data)Insert(t->left,data);
else if(data>=t->data)Insert(t->right,data);
}
bool IsBalanceTree(BTree root, int &depth)
{
if (root == NULL){
depth = 0;
return true;
}
int ldepth = 0,rdepth=0;
if (!IsBalanceTree(root->left, ldepth)||!IsBalanceTree(root->right, rdepth)){
return false;
}
depth = rdepth > ldepth ? rdepth + 1 : ldepth + 1;
return abs(ldepth - rdepth) < 2;
}
int main()
{
int n,depth;
int a[1001];
cin>>n;
BTree t=NULL;
for(int i=0;i<n;i++){
cin>>a[i];
Insert(t,a[i]);
}
if(IsBalanceTree(t,depth))cout<<"YES"<<" "<<depth<<endl;
else cout<<"NO"<<endl;
}
上一篇: 一次Debug的遐想