C++实现AVL树的完整代码

实现AVL树的完整代码需要遵循以下步骤：

第一步：头文件声明

在代码文件的开头，我们需要声明头文件，以引入所需的库和类。在实现AVL树的完整代码中，我们需要添加以下头文件：

#include <iostream>
#include <algorithm>

这里用到了C++标准库中的iostream库，用于输入输出操作，以及algorithm库，它包含了各种有用的算法，包括二叉搜索树中需要用到的max()和min()函数。

第二步：定义AVL树结构

在C++中，我们可以使用结构体来定义AVL树的节点结构。在实现AVL树的完整代码中，我们需要声明以下结构体：

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

这里声明了一个结构体node，其中包含了四个成员，分别是节点的值key，左子树指针left，右子树指针right，以及节点的高度height。其中，左右子树指针可以指向其他node结构体，形成树状结构。

第三步：定义基本操作函数

接下来，我们需要定义AVL树的基本操作函数。在实现AVL树的完整代码中，我们需要定义以下函数：

1. 计算节点高度

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

这里定义了一个计算节点高度的函数，它采用了递归的方法计算节点的高度。如果节点为空，则返回0；否则，返回节点的高度。

2. 求最大值和最小值

int max(int a, int b) {
    return (a > b) ? a : b;
}

int min(int a, int b) {
    return (a < b) ? a : b;
}

这里定义了求最大值和最小值的函数，它们采用了三目运算符，判断a和b的大小关系，返回较大或较小的值。

3. 新建节点

struct node* newNode(int key) {
    struct node* node = new struct node;
    node->key = key;
    node->left = NULL;
    node->right = NULL;
    node->height = 1;
    return(node);
}

这里定义了新建节点的函数，它创建一个新的node结构体，设置节点值为key，左右子树指针为NULL，高度为1，然后返回该节点。

4. 右旋函数

struct node* rightRotate(struct node* y) {
    struct node* x = y->left;
    struct node* T2 = x->right;
    x->right = y;
    y->left = T2;
    y->height = max(height(y->left), height(y->right)) + 1;
    x->height = max(height(x->left), height(x->right)) + 1;
    return x;
}

这里定义了右旋函数，它是AVL树中用于调整平衡的基本操作之一。右旋操作的目的是将左子树的较大节点上移一级，并且将原来的根节点下移一级作为右子树的节点。在右旋函数中，我们首先定义一个新的结构体x，它表示当前节点的左子节点。然后，我们将x的右子节点T2指向y的左子节点，将y的左节点指向x的右子节点T2。接下来，我们根据y和x的左右子节点的高度，重新计算y和x的高度，并将x作为新的根节点返回。

5. 左旋函数

struct node* leftRotate(struct node* x) {
    struct node* y = x->right;
    struct node* T2 = y->left;
    y->left = x;
    x->right = T2;
    x->height = max(height(x->left), height(x->right)) + 1;
    y->height = max(height(y->left), height(y->right)) + 1;
    return y;
}

这里定义了左旋函数，它与右旋函数实现的操作相反。在左旋函数中，我们首先定义一个新的结构体y，它表示当前节点的右子节点。然后，我们将y的左子节点T2指向x的右子节点，将x的右子节点指向y的左子节点T2。接下来，我们根据x和y的左右子节点的高度，重新计算x和y的高度，并将y作为新的根节点返回。

6. 获取平衡因子

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

这里定义了获取平衡因子的函数，它计算节点的左子树高度和右子树高度的差值，并返回该值作为平衡因子。

7. 插入节点函数

struct node* insert(struct node* node, int key) {
    if (node == NULL)
        return(newNode(key));
    if (key < node->key)
        node->left = insert(node->left, key);
    else if (key > node->key)
        node->right = insert(node->right, key);
    else
        return node;
    node->height = 1 + max(height(node->left), height(node->right));
    int balance = getBalance(node);
    if (balance > 1 && key < node->left->key)
        return rightRotate(node);
    if (balance < -1 && key > node->right->key)
        return leftRotate(node);
    if (balance > 1 && key > node->left->key) {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }
    if (balance < -1 && key < node->right->key) {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }
    return node;
}

这里定义了插入节点的函数，它采用了递归的方式。如果节点为空，则返回新建的节点；否则，如果关键字小于当前节点的关键字，则递归插入到左子树；如果关键字大于当前节点的关键字，则递归插入到右子树。然后，更新当前节点的高度，计算平衡因子，并依据平衡因子的值旋转子树，实现平衡。

第四步：测试示例

下面是两个测试示例。

示例1：插入节点

int main() {
    struct node *root = NULL;
    root = insert(root, 10);
    root = insert(root, 20);
    root = insert(root, 30);
    root = insert(root, 40);
    root = insert(root, 50);
    root = insert(root, 25);
    return 0;
}

在这个测试示例中，我们依次插入了6个节点，其中50为根节点，30和40为左子树，10和20为左子树的左子树，25为左子树的右子树。插入过程中，程序将自动调整AVL树中各个节点的高度，保持树的平衡。

示例2：输出节点

void preOrder(struct node *root) {
    if (root != NULL) {
        std::cout << root->key << " ";
        preOrder(root->left);
        preOrder(root->right);
    }
    return;
}

int main() {
    struct node *root = NULL;
    root = insert(root, 10);
    root = insert(root, 20);
    root = insert(root, 30);
    root = insert(root, 40);
    root = insert(root, 50);
    root = insert(root, 25);
    std::cout << "Preorder traversal of the constructed AVL tree is \n";
    preOrder(root);
    return 0;
}

在这个测试示例中，我们首先定义了一个输出节点的函数preOrder，在遍历过程中先输出当前节点，然后递归遍历左子树和右子树。然后，我们依然插入了6个节点，并调用preOrder函数输出所有节点的值。输出结果如下：

Preorder traversal of the constructed AVL tree is 
30 20 10 25 50 40 

可以看出，preOrder函数按照前序遍历的顺序输出了所有节点的值，验证了AVL树的正确性。

至此，我们完成了C++实现AVL树的完整代码。