数据结构之判断平衡二叉树详解与示例（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");
    else
        printf("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;
            else
        cout << "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; // 新节点被当做叶子节点加入，高度为1
    return(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");
    else
        printf("Tree is not balanced\n");

    return 0;
}

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

结论

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