MK
摩柯社区 - 一个极简的技术知识社区
AI 面试

二叉树与平衡树在C语言中的实现

2024-06-264.5k 阅读

二叉树基础概念及在C语言中的实现

二叉树的定义

二叉树是一种重要的树形数据结构，它的每个节点最多有两个子节点，分别称为左子节点和右子节点。从递归的角度来看，二叉树要么为空，要么由一个根节点、一个左子树和一个右子树组成，而左子树和右子树同样也是二叉树。

在C语言中，我们可以通过结构体来定义二叉树节点。例如：

#include <stdio.h>
#include <stdlib.h>

// 定义二叉树节点结构体
typedef struct TreeNode {
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// 创建新节点的函数
TreeNode* createNode(int data) {
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

这里定义了一个TreeNode结构体，它包含一个整数类型的数据成员data，以及两个指向TreeNode类型的指针left和right，分别用于指向左子节点和右子节点。createNode函数用于创建一个新的二叉树节点，它接受一个整数参数data，为新节点分配内存，并初始化节点的数据和子节点指针。

二叉树的遍历

  1. 先序遍历 先序遍历的顺序是先访问根节点，然后递归地先序遍历左子树，最后递归地先序遍历右子树。其C语言实现如下：
// 先序遍历
void preOrderTraversal(TreeNode* root) {
    if (root != NULL) {
        printf("%d ", root->data);
        preOrderTraversal(root->left);
        preOrderTraversal(root->right);
    }
}

在preOrderTraversal函数中，首先检查根节点是否为空，如果不为空，则输出根节点的数据，然后递归调用该函数分别遍历左子树和右子树。

  1. 中序遍历 中序遍历的顺序是先递归地中序遍历左子树，然后访问根节点，最后递归地中序遍历右子树。代码实现如下：
// 中序遍历
void inOrderTraversal(TreeNode* root) {
    if (root != NULL) {
        inOrderTraversal(root->left);
        printf("%d ", root->data);
        inOrderTraversal(root->right);
    }
}

在inOrderTraversal函数中，先递归遍历左子树，然后输出根节点数据，最后递归遍历右子树。

  1. 后序遍历 后序遍历的顺序是先递归地后序遍历左子树，然后递归地后序遍历右子树，最后访问根节点。实现代码如下：
// 后序遍历
void postOrderTraversal(TreeNode* root) {
    if (root != NULL) {
        postOrderTraversal(root->left);
        postOrderTraversal(root->right);
        printf("%d ", root->data);
    }
}

在postOrderTraversal函数中，先递归遍历左子树和右子树，最后输出根节点数据。

二叉树的插入操作

二叉树的插入操作通常是将新节点插入到合适的位置。一种常见的插入方式是将新节点插入到树的最底层，从左到右填充空位。以下是一个简单的插入函数示例，将新节点插入到二叉树的叶子节点位置：

// 插入节点到二叉树
TreeNode* insertNode(TreeNode* root, int data) {
    if (root == NULL) {
        return createNode(data);
    }
    if (root->left == NULL) {
        root->left = createNode(data);
    } else if (root->right == NULL) {
        root->right = createNode(data);
    } else {
        if (root->left != NULL && root->right != NULL) {
            TreeNode* current = root->left;
            while (current->left != NULL || current->right != NULL) {
                if (current->left != NULL) {
                    current = current->left;
                } else {
                    current = current->right;
                }
            }
            current->left = createNode(data);
        }
    }
    return root;
}

在insertNode函数中，首先检查根节点是否为空，如果为空则直接创建新节点并返回。如果根节点的左子节点为空，则将新节点插入到左子节点位置；如果左子节点不为空但右子节点为空，则将新节点插入到右子节点位置。如果左右子节点都不为空，则找到最底层最左边的叶子节点，并将新节点插入到其左子节点位置。

平衡树的概念及与二叉树的关系

平衡树的定义

平衡树是一种特殊的二叉树，它的左右子树高度差的绝对值不超过1，并且左右子树都是平衡树。常见的平衡树有AVL树、红黑树等。平衡树的主要目的是为了保持树的高度相对较低，从而提高查找、插入和删除操作的效率。与普通二叉树相比，平衡树在数据动态变化的情况下，能更好地维持良好的性能。

以AVL树为例，AVL树的每个节点都有一个平衡因子（Balance Factor），平衡因子是该节点左子树高度减去右子树高度的值。对于AVL树的每个节点，其平衡因子只能是 -1、0 或 1。如果某个节点的平衡因子绝对值大于1，则说明该树失去平衡，需要通过旋转操作来恢复平衡。

平衡树的优势

在普通二叉树中，如果节点插入或删除操作不当，可能会导致树的高度变得非常高，从而使查找、插入和删除操作的时间复杂度从理想的O(log n) 退化为O(n)，其中n是树中节点的数量。而平衡树通过维持树的平衡，能保证这些操作的时间复杂度始终保持在O(log n)。

例如，在一个存储大量数据的查找表中，如果使用普通二叉树，随着数据的不断插入，树可能会变得非常不平衡，导致查找操作变得很慢。而使用平衡树，无论数据如何动态变化，都能保证高效的查找性能。这在数据库索引、编译器符号表等应用场景中具有重要意义。

AVL树在C语言中的实现

AVL树节点定义

AVL树节点除了包含数据、左右子节点指针外，还需要包含平衡因子。在C语言中定义如下：

// 定义AVL树节点结构体
typedef struct AVLNode {
    int data;
    struct AVLNode *left;
    struct AVLNode *right;
    int balanceFactor;
} AVLNode;

// 创建新的AVL树节点
AVLNode* createAVLNode(int data) {
    AVLNode* newNode = (AVLNode*)malloc(sizeof(AVLNode));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    newNode->balanceFactor = 0;
    return newNode;
}

这里定义的AVLNode结构体比普通二叉树节点结构体多了一个balanceFactor成员，用于存储节点的平衡因子。createAVLNode函数用于创建新的AVL树节点，并初始化其成员。

获取树的高度

为了计算平衡因子和进行旋转操作，我们需要获取树的高度。以下是获取AVL树高度的函数：

// 获取树的高度
int getHeight(AVLNode* root) {
    if (root == NULL) {
        return 0;
    }
    int leftHeight = getHeight(root->left);
    int rightHeight = getHeight(root->right);
    return (leftHeight > rightHeight? leftHeight : rightHeight) + 1;
}

getHeight函数通过递归的方式分别获取左子树和右子树的高度，然后返回两者中的较大值加1，即为当前树的高度。

计算平衡因子

计算平衡因子是判断AVL树是否平衡的关键步骤。代码如下：

// 计算平衡因子
void updateBalanceFactor(AVLNode* root) {
    root->balanceFactor = getHeight(root->left) - getHeight(root->right);
}

updateBalanceFactor函数调用getHeight函数分别获取左子树和右子树的高度，并计算两者差值，将结果赋值给节点的balanceFactor。

旋转操作

  1. 右旋（Left Rotation） 当某个节点的右子树高度比左子树高度大2，且右子节点的平衡因子为1时，需要进行右旋操作。右旋操作可以恢复树的平衡。
// 右旋
AVLNode* rightRotate(AVLNode* y) {
    AVLNode* x = y->left;
    AVLNode* T2 = x->right;

    // 执行旋转
    x->right = y;
    y->left = T2;

    // 更新平衡因子
    updateBalanceFactor(y);
    updateBalanceFactor(x);

    return x;
}

在rightRotate函数中，首先定义变量x指向y的左子节点，T2指向x的右子节点。然后进行指针调整，将x的右子节点指向y，y的左子节点指向T2。最后更新y和x的平衡因子，并返回新的根节点x。

  1. 左旋（Right Rotation） 当某个节点的左子树高度比右子树高度大2，且左子节点的平衡因子为1时，需要进行左旋操作。
// 左旋
AVLNode* leftRotate(AVLNode* x) {
    AVLNode* y = x->right;
    AVLNode* T2 = y->left;

    // 执行旋转
    y->left = x;
    x->right = T2;

    // 更新平衡因子
    updateBalanceFactor(x);
    updateBalanceFactor(y);

    return y;
}

leftRotate函数的操作与右旋类似，只是方向相反。首先定义变量y指向x的右子节点，T2指向y的左子节点。然后调整指针，将y的左子节点指向x，x的右子节点指向T2。最后更新平衡因子并返回新的根节点y。

  1. 左右旋（Left - Right Rotation） 当某个节点的左子树高度比右子树高度大2，且左子节点的平衡因子为 -1时，需要进行左右旋操作。这是先左旋左子节点，再右旋该节点。
// 左右旋
AVLNode* leftRightRotate(AVLNode* root) {
    root->left = leftRotate(root->left);
    return rightRotate(root);
}

leftRightRotate函数首先对根节点的左子节点进行左旋操作，然后对根节点进行右旋操作，以恢复树的平衡。

  1. 右左旋（Right - Left Rotation） 当某个节点的右子树高度比左子树高度大2，且右子节点的平衡因子为 -1时，需要进行右左旋操作。这是先右旋右子节点，再左旋该节点。
// 右左旋
AVLNode* rightLeftRotate(AVLNode* root) {
    root->right = rightRotate(root->right);
    return leftRotate(root);
}

rightLeftRotate函数首先对根节点的右子节点进行右旋操作，然后对根节点进行左旋操作，从而使树恢复平衡。

AVL树的插入操作

AVL树的插入操作与普通二叉树类似，但在插入后需要检查并调整树的平衡。

// AVL树插入节点
AVLNode* insertAVLNode(AVLNode* root, int data) {
    if (root == NULL) {
        return createAVLNode(data);
    }
    if (data < root->data) {
        root->left = insertAVLNode(root->left, data);
    } else if (data > root->data) {
        root->right = insertAVLNode(root->right, data);
    } else {
        return root;
    }

    // 更新平衡因子
    updateBalanceFactor(root);

    // 检查并调整平衡
    if (root->balanceFactor > 1) {
        if (data < root->left->data) {
            return rightRotate(root);
        } else {
            return leftRightRotate(root);
        }
    }
    if (root->balanceFactor < -1) {
        if (data > root->right->data) {
            return leftRotate(root);
        } else {
            return rightLeftRotate(root);
        }
    }

    return root;
}

在insertAVLNode函数中，首先按照普通二叉树的插入方式找到插入位置并插入新节点。然后更新根节点的平衡因子。接着检查根节点的平衡因子，如果平衡因子大于1，说明左子树较高，根据新节点与左子节点数据的比较决定进行右旋或左右旋操作；如果平衡因子小于 -1，说明右子树较高，根据新节点与右子节点数据的比较决定进行左旋或右左旋操作。最后返回调整后的根节点。

AVL树的删除操作

AVL树的删除操作比插入操作更为复杂，因为删除节点后不仅要恢复树的平衡，还需要处理节点删除后的结构调整。

// 找到最小节点
AVLNode* findMin(AVLNode* root) {
    while (root->left != NULL) {
        root = root->left;
    }
    return root;
}

// AVL树删除节点
AVLNode* deleteAVLNode(AVLNode* root, int data) {
    if (root == NULL) {
        return root;
    }
    if (data < root->data) {
        root->left = deleteAVLNode(root->left, data);
    } else if (data > root->data) {
        root->right = deleteAVLNode(root->right, data);
    } else {
        if (root->left == NULL || root->right == NULL) {
            AVLNode* temp = root->left? root->left : root->right;
            if (temp == NULL) {
                temp = root;
                root = NULL;
            } else {
                *root = *temp;
            }
            free(temp);
        } else {
            AVLNode* temp = findMin(root->right);
            root->data = temp->data;
            root->right = deleteAVLNode(root->right, temp->data);
        }
    }

    if (root == NULL) {
        return root;
    }

    // 更新平衡因子
    updateBalanceFactor(root);

    // 检查并调整平衡
    if (root->balanceFactor > 1) {
        if (getHeight(root->left->left) >= getHeight(root->left->right)) {
            return rightRotate(root);
        } else {
            return leftRightRotate(root);
        }
    }
    if (root->balanceFactor < -1) {
        if (getHeight(root->right->right) >= getHeight(root->right->left)) {
            return leftRotate(root);
        } else {
            return rightLeftRotate(root);
        }
    }

    return root;
}

在deleteAVLNode函数中，首先按照普通二叉树的删除方式找到要删除的节点。如果该节点只有一个子节点或没有子节点，直接将子节点替换该节点并释放内存；如果该节点有两个子节点，则找到其右子树中的最小节点，将最小节点的数据替换到要删除的节点，然后删除右子树中的最小节点。删除节点后，更新根节点的平衡因子，并根据平衡因子的情况进行相应的旋转操作来恢复树的平衡。

AVL树的遍历

AVL树的遍历方式与普通二叉树相同，包括先序、中序和后序遍历。以下以中序遍历为例：

// AVL树中序遍历
void inOrderAVLTraversal(AVLNode* root) {
    if (root != NULL) {
        inOrderAVLTraversal(root->left);
        printf("%d ", root->data);
        inOrderAVLTraversal(root->right);
    }
}

inOrderAVLTraversal函数实现了AVL树的中序遍历，与普通二叉树中序遍历的逻辑一致，先递归遍历左子树，然后输出根节点数据，最后递归遍历右子树。

通过以上对二叉树和平衡树（以AVL树为例）在C语言中的详细介绍和代码实现，我们可以深入理解这两种数据结构的本质和应用。二叉树是一种基础的数据结构，而平衡树则在二叉树的基础上通过维持平衡来优化性能，在实际编程中，根据具体的需求选择合适的数据结构能有效提高程序的效率和稳定性。