平衡二叉树非递归实现c++代码

平衡二叉树（AVL树）是一种自平衡的二叉搜索树，它的左右子树的高度差不超过1。下面是一个非递归实现的平衡二叉树的C++代码示例：

#include <iostream>
#include <stack>
using namespace std;

struct TreeNode {
    int val;
    int height;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), height(1), left(NULL), right(NULL) {}
};

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

int getBalanceFactor(TreeNode* node) {
    if (node == NULL) {
        return 0;
    }
    return getHeight(node->left) - getHeight(node->right);
}

TreeNode* rotateLeft(TreeNode* node) {
    TreeNode* newRoot = node->right;
    node->right = newRoot->left;
    newRoot->left = node;
    node->height = max(getHeight(node->left), getHeight(node->right)) + 1;
    newRoot->height = max(getHeight(newRoot->left), getHeight(newRoot->right)) + 1;
    return newRoot;
}

TreeNode* rotateRight(TreeNode* node) {
    TreeNode* newRoot = node->left;
    node->left = newRoot->right;
    newRoot->right = node;
    node->height = max(getHeight(node->left), getHeight(node->right)) + 1;
    newRoot->height = max(getHeight(newRoot->left), getHeight(newRoot->right)) + 1;
    return newRoot;
}

TreeNode* insert(TreeNode* root, int val) {
    if (root == NULL) {
        return new TreeNode(val);
    }
    if (val < root->val) {
        root->left = insert(root->left, val);
    } else if (val > root->val) {
        root->right = insert(root->right, val);
    } else {
        return root;  // 不允许插入重复的节点
    }
    root->height = max(getHeight(root->left), getHeight(root->right)) + 1;
    int balanceFactor = getBalanceFactor(root);
    if (balanceFactor > 1 && val < root->left->val) {
        return rotateRight(root);
    }
    if (balanceFactor < -1 && val > root->right->val) {
        return rotateLeft(root);
    }
    if (balanceFactor > 1 && val > root->left->val) {
        root->left = rotateLeft(root->left);
        return rotateRight(root);
    }
    if (balanceFactor < -1 && val < root->right->val) {
        root->right = rotateRight(root->right);
        return rotateLeft(root);
    }
    return root;
}

void inorderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    stack<TreeNode*> s;
    TreeNode* curr = root;
    while (curr != NULL || !s.empty()) {
        while (curr != NULL) {
            s.push(curr);
            curr = curr->left;
        }
        curr = s.top();
        s.pop();
        cout << curr->val << " ";
        curr = curr->right;
    }
}

int main() {
    TreeNode* root = NULL;
    int arr[] = {3, 2, 4, 5, 6, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    for (int i = 0; i < n; i++) {
        root = insert(root, arr[i]);
    }
    cout << "Inorder traversal of the AVL tree: ";
    inorderTraversal(root);
    return 0;
}

这段代码实现了平衡二叉树的插入操作，并通过中序遍历打印出了平衡后的树节点值。你可以根据需要进行修改和扩展。