# 平衡二叉樹 > 原文： [https://www.programiz.com/dsa/balanced-binary-tree](https://www.programiz.com/dsa/balanced-binary-tree) #### 在本教程中，您將了解平衡的二叉樹及其不同類型。 此外，您還將在 C，C++ ，Java 和 Python 中找到平衡二叉樹的工作示例。 平衡二叉樹（也稱為高度平衡二叉樹）定義為二叉樹，其中任何節點的左和右子樹的高度相差不超過 1。 要了解有關樹/節點的高度的更多信息，請訪問[樹數據結構](https://www.programiz.com/dsa/trees)。以下是高度平衡的二叉樹的條件： 1. 任何節點的左和右子樹之間的差異不超過一個 2. 左子樹是平衡的 3. 右子樹是平衡的  每個級別都有深度的平衡二叉樹  每個級別都有深度的不平衡二叉樹 * * * ## Python，Java 和 C/C++ 示例 以下代碼用于檢查樹是否高度平衡。 ```py # Checking if a binary tree is CalculateHeight balanced in Python # CreateNode creation class CreateNode: def __init__(self, item): self.item = item self.left = self.right = None # Calculate height class CalculateHeight: def __init__(self): self.CalculateHeight = 0 # Check height balance def is_height_balanced(root, CalculateHeight): left_height = CalculateHeight() right_height = CalculateHeight() if root is None: return True l = is_height_balanced(root.left, left_height) r = is_height_balanced(root.right, right_height) CalculateHeight.CalculateHeight = max( left_height.CalculateHeight, right_height.CalculateHeight) + 1 if abs(left_height.CalculateHeight - right_height.CalculateHeight) <= 1: return l and r return False CalculateHeight = CalculateHeight() root = CreateNode(1) root.left = CreateNode(2) root.right = CreateNode(3) root.left.left = CreateNode(4) root.left.right = CreateNode(5) if is_height_balanced(root, CalculateHeight): print('The tree is balanced') else: print('The tree is not balanced') ``` ```java // Checking if a binary tree is height balanced in Java // Node creation class Node { int data; Node left, right; Node(int d) { data = d; left = right = null; } } // Calculate height class Height { int height = 0; } class BinaryTree { Node root; // Check height balance boolean checkHeightBalance(Node root, Height height) { // Check for emptiness 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("The tree is balanced"); else System.out.println("The tree is not balanced"); } } ``` ```c // Checking if a binary tree is height balanced in C #include <stdio.h> #include <stdlib.h> #define bool int // Node creation struct node { int item; struct node *left; struct node *right; }; // Create a new node 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); } // Check for height balance bool checkHeightBalance(struct node *root, int *height) { // Check for emptiness 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("The tree is balanced"); else printf("The tree is not balanced"); } ``` ```cpp // Checking if a binary tree is height balanced in C++ #include <iostream> using namespace std; #define bool int class node { public: int item; node *left; node *right; }; // Create anew node node *newNode(int item) { node *Node = new node(); Node->item = item; Node->left = NULL; Node->right = NULL; return (Node); } // Check height balance bool checkHeightBalance(node *root, int *height) { // Check for emptiness 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; 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 << "The tree is balanced"; else cout << "The tree is not balanced"; } ``` * * * ## 平衡二叉樹應用 * [AVL 樹](https://www.programiz.com/dsa/avl-tree) * 平衡的[二叉搜索樹](https://www.programiz.com/dsa/binary-search-tree)