数据结构之判断平衡二叉树详解与示例（C，C++）

---

在计算机科学中，二叉树是一种非常重要的数据结构。它们被广泛用于多种算法中，如排序、查找等。然而，普通的二叉树在极端情况下可能退化成链表，导致算法性能大大降低。为了解决这个问题，Adelson-Velsky和Landis在1962年提出了平衡二叉树（AVL树）。本文将详细介绍如何判断一个二叉树是否为平衡二叉树，并提供C和C++语言的示例代码。

AVL树定义

AVL树是一种自平衡的二叉搜索树，其中任何节点的两个子树的高度最大差别为1。这种平衡保证了树的高度大约是log(n)，其中n是树中节点的数量。这使得AVL树在最坏情况下的查找、插入和删除操作的时间复杂度都是O(log n)。

节点定义

首先，我们需要定义树的节点结构。每个节点包含以下信息：

1. 键值（Key）
2. 左子树指针（Left）
3. 右子树指针（Right）
4. 节点高度（Height）

C语言示例

struct TreeNode {int key;struct TreeNode *left;struct TreeNode *right;int height;
};

C++语言示例

struct TreeNode {int key;TreeNode *left;TreeNode *right;int height;TreeNode(int k) : key(k), left(nullptr), right(nullptr), height(1) {}
};

计算高度

计算节点的高度，如果节点为空，则高度为-1。

C语言示例

int height(struct TreeNode *N) {if (N == NULL)return 0;return N->height;
}

C++语言示例

int height(TreeNode *N) {if (N == nullptr) return 0;return N->height;
}

获取平衡因子

平衡因子是右子树高度与左子树高度的差。如果节点的平衡因子绝对值大于1，则该树不是平衡的。

C语言示例

int getBalance(struct TreeNode *N) {if (N == NULL)return 0;return height(N->right) - height(N->left);
}

C++语言示例

int getBalance(TreeNode *N) {if (N == nullptr) return 0;return height(N->right) - height(N->left);
}

判断是否为平衡二叉树

通过递归检查每个节点，判断是否每个节点的平衡因子都在-1到1之间。

C语言示例

int isBalanced(struct TreeNode *root) {if (root == NULL)return 1;int leftHeight = height(root->left);int rightHeight = height(root->right);if (abs(leftHeight - rightHeight) > 1)return 0;return isBalanced(root->left) && isBalanced(root->right);
}

C++语言示例

bool isBalanced(TreeNode *root) {if (root == nullptr) return true;int leftHeight = height(root->left);int rightHeight = height(root->right);if (abs(leftHeight - rightHeight) > 1)return false;return isBalanced(root->left) && isBalanced(root->right);
}

完整示例代码

以下是完整的示例代码，包括创建树和判断是否为平衡二叉树。

C语言完整示例

#include <stdio.h>
#include <stdlib.h>
#include <math.h>// ... (省略之前定义的TreeNode结构和函数)int main() {struct TreeNode *root = newNode(1);root->left = newNode(2);root->right = newNode(3);root->left->left = newNode(4);root->left->right = newNode(5);if (isBalanced(root))printf("Tree is balanced\n");elseprintf("Tree is not balanced\n");return 0;
}

C++语言完整示例

#include <iostream>
#include <cmath>
#include <algorithm>using namespace std;// ... (省略之前定义的TreeNode结构和函数)int main() {TreeNode *root = new TreeNode(1);root->left = new TreeNode(2);root->right = new TreeNode(3);root->left->left = new TreeNode(4);root->left->right = new TreeNode(5);if (isBalanced(root))cout << "Tree is balanced" << endl;elsecout << "Tree is not balanced" << endl;// 注意：在C++中，使用new分配的内存需要手动释放delete root->left->left;delete root->left->right;delete root->left;delete root->right;delete root;return 0;
}

完整示例代码（C语言）
递归检查每个节点，如果发现任何节点的平衡因子不在-1到1之间，则整棵树不是平衡二叉树。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>struct TreeNode {int key;struct TreeNode *left;struct TreeNode *right;int height;
};int max(int a, int b) {return (a > b) ? a : b;
}int height(struct TreeNode *N) {if (N == NULL)return 0;return N->height;
}int getBalance(struct TreeNode *N) {if (N == NULL)return 0;return height(N->right) - height(N->left);
}struct TreeNode *newNode(int key) {struct TreeNode *node = (struct TreeNode *)malloc(sizeof(struct TreeNode));node->key = key;node->left = NULL;node->right = NULL;node->height = 1; // 新节点被当做叶子节点加入，高度为1return(node);
}int isBalanced(struct TreeNode *root) {if (root == NULL)return 1;int leftHeight = height(root->left);int rightHeight = height(root->right);if (abs(leftHeight - rightHeight) > 1)return 0;return isBalanced(root->left) && isBalanced(root->right);
}int main() {struct TreeNode *root = newNode(1);root->left = newNode(2);root->right = newNode(3);root->left->left = newNode(4);root->left->right = newNode(5);if (isBalanced(root))printf("Tree is balanced\n");elseprintf("Tree is not balanced\n");return 0;
}

此代码将创建一个简单的二叉树，并检查它是否为平衡二叉树。在实际应用中，平衡二叉树的插入和删除操作会更复杂，因为它们需要维护树的平衡，通常会涉及到节点的旋转操作。

结论

本文详细介绍了如何判断一个二叉树是否为平衡二叉树，并提供了C和C++语言的示例代码。在实际应用中，平衡二叉树的插入和删除操作会更复杂，因为它们需要维护树的平衡，通常会涉及到节点的旋转操作。理解并掌握AVL树是成为一名优秀程序员的重要一步，因为它不仅能够提高算法的效率，还能帮助我们在处理复杂问题时保持清晰的逻辑思维。