# 如何确定二叉树是否高度平衡？

## 本文概述

1)T的左子树是平衡的

2)T的右子树是平衡的

3)左子树和右子树的高度之差不大于1。

## C++

``````/* CPP program to check if
a tree is height-balanced or not */
#include <bits/stdc++.h>
using namespace std;

/* A binary tree node has data, pointer to left child and
a pointer to right child */
class node {
public :
int data;
node* left;
node* right;
};

/* Returns the height of a binary tree */
int height(node* node);

/* Returns true if binary tree
with root as root is height-balanced */
bool isBalanced(node* root)
{
int lh; /* for height of left subtree */
int rh; /* for height of right subtree */

/* If tree is empty then return true */
if (root == NULL)
return 1;

/* Get the height of left and right sub trees */
lh = height(root->left);
rh = height(root->right);

if ( abs (lh - rh) <= 1 && isBalanced(root->left) && isBalanced(root->right))
return 1;

/* If we reach here then
tree is not height-balanced */
return 0;
}

/* UTILITY FUNCTIONS TO TEST isBalanced() FUNCTION */

/* returns maximum of two integers */
int max( int a, int b)
{
return (a>= b) ? a : b;
}

/* The function Compute the "height"
of a tree. Height is the number of
nodes along the longest path from
the root node down to the farthest leaf node.*/
int height(node* node)
{
/* base case tree is empty */
if (node == NULL)
return 0;

/* If tree is not empty then
height = 1 + max of left
height and right heights */
return 1 + max(height(node->left), height(node->right));
}

/* Helper function that allocates
a new node with the given data
and NULL left and right pointers. */
node* newNode( int data)
{
node* Node = new node();
Node->data = data;
Node->left = NULL;
Node->right = NULL;

return (Node);
}

//Driver code
int main()
{
node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->left->left->left = newNode(8);

if (isBalanced(root))
cout <<"Tree is balanced" ;
else
cout <<"Tree is not balanced" ;
return 0;
}

//This code is contributed by rathbhupendra``````

## C

``````/* C program to check if a tree is height-balanced or not */
#include <stdio.h>
#include <stdlib.h>
#define bool int

/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node {
int data;
struct node* left;
struct node* right;
};

/* Returns the height of a binary tree */
int height( struct node* node);

/* Returns true if binary tree with root as root is height-balanced */
bool isBalanced( struct node* root)
{
int lh; /* for height of left subtree */
int rh; /* for height of right subtree */

/* If tree is empty then return true */
if (root == NULL)
return 1;

/* Get the height of left and right sub trees */
lh = height(root->left);
rh = height(root->right);

if ( abs (lh - rh) <= 1 && isBalanced(root->left) && isBalanced(root->right))
return 1;

/* If we reach here then tree is not height-balanced */
return 0;
}

/* UTILITY FUNCTIONS TO TEST isBalanced() FUNCTION */

/* returns maximum of two integers */
int max( int a, int b)
{
return (a>= b) ? a : b;
}

/*  The function Compute the "height" of a tree. Height is the
number of nodes along the longest path from the root node
down to the farthest leaf node.*/
int height( struct node* node)
{
/* base case tree is empty */
if (node == NULL)
return 0;

/* If tree is not empty then height = 1 + max of left
height and right heights */
return 1 + max(height(node->left), height(node->right));
}

/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct node* newNode( int data)
{
struct node* node = ( struct node*)
malloc ( sizeof ( struct node));
node->data = data;
node->left = NULL;
node->right = NULL;

return (node);
}

int main()
{
struct node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->left->left->left = newNode(8);

if (isBalanced(root))
printf ( "Tree is balanced" );
else
printf ( "Tree is not balanced" );

getchar ();
return 0;
}``````

## Java

``````/* Java program to determine if binary tree is
height balanced or not */

/* A binary tree node has data, pointer to left child, and a pointer to right child */
class Node {
int data;
Node left, right;
Node( int d)
{
data = d;
left = right = null ;
}
}

class BinaryTree {
Node root;

/* Returns true if binary tree with root as root is height-balanced */
boolean isBalanced(Node node)
{
int lh; /* for height of left subtree */

int rh; /* for height of right subtree */

/* If tree is empty then return true */
if (node == null )
return true ;

/* Get the height of left and right sub trees */
lh = height(node.left);
rh = height(node.right);

if (Math.abs(lh - rh) <= 1
&& isBalanced(node.left)
&& isBalanced(node.right))
return true ;

/* If we reach here then tree is not height-balanced */
return false ;
}

/* UTILITY FUNCTIONS TO TEST isBalanced() FUNCTION */
/*  The function Compute the "height" of a tree. Height is the
number of nodes along the longest path from the root node
down to the farthest leaf node.*/
int height(Node node)
{
/* base case tree is empty */
if (node == null )
return 0 ;

/* If tree is not empty then height = 1 + max of left
height and right heights */
return 1 + Math.max(height(node.left), height(node.right));
}

public static void main(String args[])
{
BinaryTree tree = new BinaryTree();
tree.root = new Node( 1 );
tree.root.left = new Node( 2 );
tree.root.right = new Node( 3 );
tree.root.left.left = new Node( 4 );
tree.root.left.right = new Node( 5 );
tree.root.left.left.left = new Node( 8 );

if (tree.isBalanced(tree.root))
System.out.println( "Tree is balanced" );
else
System.out.println( "Tree is not balanced" );
}
}

//This code has been contributed by Mayank Jaiswal(mayank_24)``````

## Python3

``````"""
Python3 program to check if a tree is height-balanced
"""
# A binary tree Node

class Node:
# Constructor to create a new Node
def __init__( self , data):
self .data = data
self .left = None
self .right = None

# function to find height of binary tree
def height(root):

# base condition when binary tree is empty
if root is None :
return 0
return max (height(root.left), height(root.right)) + 1

# function to check if tree is height-balanced or not
def isBalanced(root):

# Base condition
if root is None :
return True

# for left and right subtree height
lh = height(root.left)
rh = height(root.right)

# allowed values for (lh - rh) are 1, -1, 0
if ( abs (lh - rh) <= 1 ) and isBalanced(
root.left) is True and isBalanced( root.right) is True :
return True

# if we reach here means tree is not
# height-balanced tree
return False

# Driver function to test the above function
root = Node( 1 )
root.left = Node( 2 )
root.right = Node( 3 )
root.left.left = Node( 4 )
root.left.right = Node( 5 )
root.left.left.left = Node( 8 )
if isBalanced(root):
print ( "Tree is balanced" )
else :
print ( "Tree is not balanced" )

# This code is contributed by Shweta Singh``````

## C#

``````using System;

/* C# program to determine if binary tree is
height balanced or not */

/* A binary tree node has data, pointer to left child, and a pointer to right child */
public class Node {
public int data;
public Node left, right;
public Node( int d)
{
data = d;
left = right = null ;
}
}

public class BinaryTree {
public Node root;

/* Returns true if binary tree with root as
root is height-balanced */
public virtual bool isBalanced(Node node)
{
int lh; //for height of left subtree

int rh; //for height of right subtree

/* If tree is empty then return true */
if (node == null ) {
return true ;
}

/* Get the height of left and right sub trees */
lh = height(node.left);
rh = height(node.right);

if (Math.Abs(lh - rh) <= 1 && isBalanced(node.left)
&& isBalanced(node.right)) {
return true ;
}

/* If we reach here then tree is not height-balanced */
return false ;
}

/* UTILITY FUNCTIONS TO TEST isBalanced() FUNCTION */
/* The function Compute the "height" of a tree. Height is the
number of nodes along the longest path from the root node
down to the farthest leaf node.*/
public virtual int height(Node node)
{
/* base case tree is empty */
if (node == null ) {
return 0;
}

/* If tree is not empty then height = 1 + max of left
height and right heights */
return 1 + Math.Max(height(node.left), height(node.right));
}

public static void Main( string [] args)
{
BinaryTree tree = new BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
tree.root.left.left.left = new Node(8);

if (tree.isBalanced(tree.root)) {
Console.WriteLine( "Tree is balanced" );
}
else {
Console.WriteLine( "Tree is not balanced" );
}
}
}

//This code is contributed by Shrikant13``````

``Tree is not balanced``

## C++

``````/* C++ program to check if a tree
is height-balanced or not */
#include <bits/stdc++.h>
using namespace std;
#define bool int

/* A binary tree node has data, pointer to left child and
a pointer to right child */
class node {
public :
int data;
node* left;
node* right;
};

/* The function returns true if root is
balanced else false The second parameter
is to store the height of tree. Initially, we need to pass a pointer to a location with
value as 0. We can also write a wrapper
over this function */
bool isBalanced(node* root, int * height)
{

/* lh --> Height of left subtree
rh --> Height of right subtree */
int lh = 0, rh = 0;

/* l will be true if left subtree is balanced
and r will be true if right subtree is balanced */
int l = 0, r = 0;

if (root == NULL) {
*height = 0;
return 1;
}

/* Get the heights of left and right subtrees in lh and rh
And store the returned values in l and r */
l = isBalanced(root->left, &lh);
r = isBalanced(root->right, &rh);

/* Height of current node is max of heights of left and
right subtrees plus 1*/
*height = (lh> rh ? lh : rh) + 1;

/* If difference between heights of left and right
subtrees is more than 2 then this node is not balanced
so return 0 */
if ( abs (lh - rh)>= 2)
return 0;

/* If this node is balanced and left and right subtrees
are balanced then return true */
else
return l && r;
}

/* UTILITY FUNCTIONS TO TEST isBalanced() FUNCTION */

/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
node* newNode( int data)
{
node* Node = new node();
Node->data = data;
Node->left = NULL;
Node->right = NULL;

return (Node);
}

//Driver code
int main()
{
int height = 0;

/* Constructed binary tree is
1
/\
2 3
/\ /
4 5 6
/
7
*/
node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->right->left = newNode(6);
root->left->left->left = newNode(7);

if (isBalanced(root, &height))
cout <<"Tree is balanced" ;
else
cout <<"Tree is not balanced" ;

return 0;
}

//This is code is contributed by rathbhupendra``````

## C

``````/* C program to check if a tree is height-balanced or not */
#include <stdio.h>
#include <stdlib.h>
#define bool int

/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node {
int data;
struct node* left;
struct node* right;
};

/* The function returns true if root is balanced else false
The second parameter is to store the height of tree.
Initially, we need to pass a pointer to a location with value
as 0. We can also write a wrapper over this function */
bool isBalanced( struct node* root, int * height)
{
/* lh --> Height of left subtree
rh --> Height of right subtree */
int lh = 0, rh = 0;

/* l will be true if left subtree is balanced
and r will be true if right subtree is balanced */
int l = 0, r = 0;

if (root == NULL) {
*height = 0;
return 1;
}

/* Get the heights of left and right subtrees in lh and rh
And store the returned values in l and r */
l = isBalanced(root->left, &lh);
r = isBalanced(root->right, &rh);

/* Height of current node is max of heights of left and
right subtrees plus 1*/
*height = (lh> rh ? lh : rh) + 1;

/* If difference between heights of left and right
subtrees is more than 2 then this node is not balanced
so return 0 */
if ( abs (lh - rh)>= 2)
return 0;

/* If this node is balanced and left and right subtrees
are balanced then return true */
else
return l && r;
}

/* UTILITY FUNCTIONS TO TEST isBalanced() FUNCTION */

/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct node* newNode( int data)
{
struct node* node = ( struct node*)
malloc ( sizeof ( struct node));
node->data = data;
node->left = NULL;
node->right = NULL;

return (node);
}

//Driver code
int main()
{
int height = 0;

/* Constructed binary tree is
1
/  \
2      3
/ \    /
4     5  6
/
7
*/
struct node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->right->left = newNode(6);
root->left->left->left = newNode(7);

if (isBalanced(root, &height))
printf ( "Tree is balanced" );
else
printf ( "Tree is not balanced" );

getchar ();
return 0;
}``````

## Java

``````/* Java program to determine if binary tree is
height balanced or not */

/* A binary tree node has data, pointer to left child, and a pointer to right child */
class Node {

int data;
Node left, right;

Node( int d)
{
data = d;
left = right = null ;
}
}

//A wrapper class used to modify height across
//recursive calls.
class Height {
int height = 0 ;
}

class BinaryTree {

Node root;

/* Returns true if binary tree with root as root is height-balanced */
boolean isBalanced(Node root, Height height)
{
/* If tree is empty then return true */
if (root == null ) {
height.height = 0 ;
return true ;
}

/* Get heights of left and right sub trees */
Height lheight = new Height(), rheight = new Height();
boolean l = isBalanced(root.left, lheight);
boolean r = isBalanced(root.right, rheight);
int lh = lheight.height, rh = rheight.height;

/* Height of current node is max of heights of
left and right subtrees plus 1*/
height.height = (lh> rh ? lh : rh) + 1 ;

/* If difference between heights of left and right
subtrees is more than 2 then this node is not balanced
so return 0 */
if (Math.abs(lh - rh)>= 2 )
return false ;

/* If this node is balanced and left and right subtrees
are balanced then return true */
else
return l && r;
}

public static void main(String args[])
{
Height height = new Height();

/* Constructed binary tree is
1
/  \
2      3
/ \    /
4     5  6
/
7         */
BinaryTree tree = new BinaryTree();
tree.root = new Node( 1 );
tree.root.left = new Node( 2 );
tree.root.right = new Node( 3 );
tree.root.left.left = new Node( 4 );
tree.root.left.right = new Node( 5 );
tree.root.right.right = new Node( 6 );
tree.root.left.left.left = new Node( 7 );

if (tree.isBalanced(tree.root, height))
System.out.println( "Tree is balanced" );
else
System.out.println( "Tree is not balanced" );
}
}

//This code has been contributed by Mayank Jaiswal(mayank_24)``````

## Python3

``````"""
Python3 program to check if Binary tree is
height-balanced
"""

# A binary tree node
class Node:

# constructor to create node of
# binary tree
def __init__( self , data):
self .data = data
self .left = self .right = None

# utility class to pass height object
class Height:
def __init__( self ):
self .height = 0

# helper function to check if binary
# tree is height balanced
def isBalanced(root):

# lh and rh to store height of
# left and right subtree
lh = Height()
rh = Height()

# Base condition when tree is
# empty return true
if root is None :
return True

# l and r are used to check if left
# and right subtree are balanced
l = isBalanced(root.left)
r = isBalanced(root.right)

# height of tree is maximum of
# left subtree height and
# right subtree height plus 1

if abs (lh.height - rh.height) <= 1 :
return l and r

# if we reach here then the tree
# is not balanced
return False

# Driver function to test the above function
"""
Constructed binary tree is
1
/\
2     3
/\ /
4 5 6 /7
"""
# to store the height of tree during traversal

root = Node( 1 )
root.left = Node( 2 )
root.right = Node( 3 )
root.left.left = Node( 4 )
root.left.right = Node( 5 )
root.right.left = Node( 6 )
root.left.left.left = Node( 7 )

if isBalanced(root):
print ( 'Tree is balanced' )
else :
print ( 'Tree is not balanced' )

# This code is contributed by Shweta Singh``````

## C#

``````using System;

/* C# program to determine if binary tree is
height balanced or not */

/* A binary tree node has data, pointer to left child, and a pointer to right child */
public class Node {

public int data;
public Node left, right;

public Node( int d)
{
data = d;
left = right = null ;
}
}

//A wrapper class used to modify height across
//recursive calls.
public class Height {
public int height = 0;
}

public class BinaryTree {

public Node root;

/* Returns true if binary tree with root as root is height-balanced */
public virtual bool isBalanced(Node root, Height height)
{
/* If tree is empty then return true */
if (root == null ) {
height.height = 0;
return true ;
}

/* Get heights of left and right sub trees */
Height lheight = new Height(), rheight = new Height();
bool l = isBalanced(root.left, lheight);
bool r = isBalanced(root.right, rheight);
int lh = lheight.height, rh = rheight.height;

/* Height of current node is max of heights of
left and right subtrees plus 1*/
height.height = (lh> rh ? lh : rh) + 1;

/* If difference between heights of left and right
subtrees is more than 2 then this node is not balanced
so return 0 */
if (Math.Abs(lh - rh)>= 2) {
return false ;
}

/* If this node is balanced and left and right subtrees
are balanced then return true */
else {
return l && r;
}
}

/*  The function Compute the "height" of a tree. Height is the
number of nodes along the longest path from the root node
down to the farthest leaf node.*/
public virtual int height(Node node)
{
/* base case tree is empty */
if (node == null ) {
return 0;
}

/* If tree is not empty then height = 1 + max of left
height and right heights */
return 1 + Math.Max(height(node.left), height(node.right));
}

public static void Main( string [] args)
{
Height height = new Height();

/* Constructed binary tree is
1
/  \
2      3
/ \    /
4     5  6
/
7         */
BinaryTree tree = new BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
tree.root.right.right = new Node(6);
tree.root.left.left.left = new Node(7);

if (tree.isBalanced(tree.root, height)) {
Console.WriteLine( "Tree is balanced" );
}
else {
Console.WriteLine( "Tree is not balanced" );
}
}
}

//This code is contributed by Shrikant13``````

``Tree is balanced``

• 回顶