AVL平衡树(非指针实现）

AVL平衡树是一种自平衡二叉搜索树，它的平衡因子是节点的左子树高度和右子树高度之差。当插入或删除一个节点后，如果发现树的平衡因子大于1或小于-1，就需要对树进行旋转，以恢复平衡。

下面是一个非指针实现的AVL平衡树的代码示例：

#include <iostream>

using namespace std;

template<typename T>
class AVLTree {
private:
    struct Node {
        T data;
        int height;
        Node *left;
        Node *right;

        Node(T data) : data(data), height(1), left(nullptr), right(nullptr) {}
    };

    Node *root;

    int getHeight(Node *node) {
        return node ? node->height : 0;
    }

    int getBalanceFactor(Node *node) {
        return node ? getHeight(node->left) - getHeight(node->right) : 0;
    }

    void updateHeight(Node *node) {
        node->height = max(getHeight(node->left), getHeight(node->right)) + 1;
    }

    void leftRotate(Node *&node) {
        Node *temp = node->right;
        node->right = temp->left;
        temp->left = node;

        updateHeight(node);
        updateHeight(temp);

        node = temp;
    }

    void rightRotate(Node *&node) {
        Node *temp = node->left;
        node->left = temp->right;
        temp->right = node;

        updateHeight(node);
        updateHeight(temp);

        node = temp;
    }

    void insert(Node *&node, T data) {
        if (!node) {
            node = new Node(data);
            return;
        }

        if (data < node->data)
            insert(node->left, data);
        else if (data > node->data)
            insert(node->right, data);

        updateHeight(node);

        int balanceFactor = getBalanceFactor(node);

        if (balanceFactor > 1) {
            if (getBalanceFactor(node->left) < 0)
                leftRotate(node->left);

            rightRotate(node);
        } else if (balanceFactor < -1) {
            if (getBalanceFactor(node->right) > 0)
                rightRotate(node->right);

            leftRotate(node);
        }
    }

    void inOrder(Node *node) {
        if (!node)
            return;

        inOrder(node->left);
        cout << node->data << " ";
        inOrder(node->right);
    }

public:
    AVLTree() : root(nullptr) {}

    void insert(T data) {
        insert(root, data);
    }

    void inOrder() {
        inOrder(root);
        cout << endl;
    }
};

这个代码示例中，AVLTree是一个模板类，可以存储任意类型的数据。Node结构体表示树的节点，包括数据、高度、左子节点和右子节点。getHeight函数返回节点的高度，getBalanceFactor函数返回节点的平衡因子（左子树高度减右子树高度），updateHeight函数更新节点的高度，leftRotate函数和rightRotate函数实现左旋和右旋操作，insert函数实现插入操作，inOrder函数实现中序遍历输出树的内容。

希望这个代码示例能对你有所帮助！