平衡二叉树
提示
- 定义：平衡二叉树，或高度平衡二叉树，是每个节点的左右子树高度差不超过1的二叉树。
- 平衡条件：为了保持平衡，该树的任意节点的左子树和右子树高度差必须不超过一，且左右子树本身也需保持平衡。
- 应用场景：平衡二叉树广泛应用于AVL树和二叉搜索树的平衡实现，以提高搜索、插入和删除等操作的效率。
平衡二叉树，也称为高度平衡二叉树，定义为任一节点的左右子树的高度差不超过 1 的二叉树。
要了解更多关于树/节点高度的信息，请访问树数据结构。下面是高度平衡二叉树的条件：
- 任一节点的左右子树高度差不超过一
- 左子树是平衡的
- 右子树是平衡的
Python、Java 和 C/C++ 示例
以下代码用于检查一棵树是否是高度平衡的。
# 用 Python 检查二叉树是否高度平衡
class Node:
def __init__(self, data):
self.data = data
self.left = self.right = None
class Height:
def __init__(self):
self.height = 0
def isHeightBalanced(root, height):
left_height = Height()
right_height = Height()
if root is None:
return True
l = isHeightBalanced(root.left, left_height)
r = isHeightBalanced(root.right, right_height)
height.height = max(left_height.height, right_height.height) + 1
if abs(left_height.height - right_height.height) <= 1:
return l and r
return False
height = Height()
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
if isHeightBalanced(root, height):
print('该树是平衡的')
else:
print('该树不是平衡的')
// 用 Java 检查二叉树是否高度平衡
// 节点创建
class Node {
int data;
Node left, right;
Node(int d) {
data = d;
left = right = null;
}
}
// 计算高度
class Height {
int height = 0;
}
class BinaryTree {
Node root;
// 检查高度平衡
boolean checkHeightBalance(Node root, Height height) {
// 检查空树
if (root == null) {
height.height = 0;
return true;
}
Height leftHeighteight = new Height(), rightHeighteight = new Height();
boolean l = checkHeightBalance(root.left, leftHeighteight);
boolean r = checkHeightBalance(root.right, rightHeighteight);
int leftHeight = leftHeighteight.height, rightHeight = rightHeighteight.height;
height.height = (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
if ((leftHeight - rightHeight >= 2) || (rightHeight - leftHeight >= 2))
return false;
else
return l && r;
}
public static void main(String args[]) {
Height height = new Height();
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);
if (tree.checkHeightBalance(tree.root, height))
System.out.println("该树是平衡的");
else
System.out.println("该树不是平衡的");
}
}
```// 在 C 中检查二叉树是否高度平衡
```c
#include <stdio.h>
#include <stdlib.h>
#define bool int
// 创建节点
struct node {
int item;
struct node *left;
struct node *right;
};
// 创建新节点
struct node *newNode(int item) {
struct node *node = (struct node *)malloc(sizeof(struct node));
node->item = item;
node->left = NULL;
node->right = NULL;
return (node);
}
// 检查高度平衡
bool checkHeightBalance(struct node *root, int *height) {
// 检查是否为空
int leftHeight = 0, rightHeight = 0;
int l = 0, r = 0;
if (root == NULL) {
*height = 0;
return 1;
}
l = checkHeightBalance(root->left, &leftHeight);
r = checkHeightBalance(root->right, &rightHeight);
*height = (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
if ((leftHeight - rightHeight >= 2) || (rightHeight - leftHeight >= 2))
return 0;
else
return l && r;
}
int main() {
int height = 0;
struct node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
if (checkHeightBalance(root, &height))
printf("该树是平衡的");
else
printf("该树不是平衡的");
}
// 在 C++ 中检查二叉树是否高度平衡
#include <iostream>
using namespace std;
#define bool int
class node {
public:
int item;
node *left;
node *right;
};
// 创建新节点
node *newNode(int item) {
node *Node = new node();
Node->item = item;
Node->left = NULL;
Node->right = NULL;
return (Node);
}
// 检查高度平衡
bool checkHeightBalance(node *root, int *height) {
// 检查是否为空
int leftHeight = 0, rightHeight = 0;
int l = 0, r = 0;
if (root == NULL) {
*height = 0;
return 1;
}
l = checkHeightBalance(root->left, &leftHeight);
r = checkHeightBalance(root->right, &rightHeight);
*height = (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
if (std::abs(leftHeight - rightHeight >= 2))
return 0;
else
return l && r;
}
int main() {
int height = 0;
node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
if (checkHeightBalance(root, &height))
cout << "该树是平衡的";
else
cout << "该树不是平衡的";
}