用c++实现平衡二叉排序树的各种算法 用函数实现如下（平衡）二叉排序树算法： (1) 插入新结点 （2）前序、中序、后序遍历二叉树（递归）（3）前序、中序、后序遍历的非递归算法（4）层次遍历二叉树 （5)在二叉树中查找给定关键字(函数返回值为成功1. （6）交换各结点的左右子树 求二叉树的深度（8）叶子结点数 （9）删除某结点

1. 插入新节点

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

// 获取节点高度
int getHeight(TreeNode* root) {
    if (root == nullptr) return 0;
    return root->height;
}

// 获取节点平衡因子
int getBalanceFactor(TreeNode* root) {
    if (root == nullptr) return 0;
    return getHeight(root->left) - getHeight(root->right);
}

// 更新节点高度
void updateHeight(TreeNode* root) {
    root->height = max(getHeight(root->left), getHeight(root->right)) + 1;
}

// 左旋
TreeNode* leftRotate(TreeNode* root) {
    TreeNode* newRoot = root->right;
    root->right = newRoot->left;
    newRoot->left = root;
    updateHeight(root);
    updateHeight(newRoot);
    return newRoot;
}

// 右旋
TreeNode* rightRotate(TreeNode* root) {
    TreeNode* newRoot = root->left;
    root->left = newRoot->right;
    newRoot->right = root;
    updateHeight(root);
    updateHeight(newRoot);
    return newRoot;
}

// 插入节点
TreeNode* insert(TreeNode* root, int val) {
    if (root == nullptr) {
        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;
    }
    updateHeight(root);
    int balanceFactor = getBalanceFactor(root);
    if (balanceFactor > 1 && getBalanceFactor(root->left) >= 0) {
        return rightRotate(root);
    }
    if (balanceFactor > 1 && getBalanceFactor(root->left) < 0) {
        root->left = leftRotate(root->left);
        return rightRotate(root);
    }
    if (balanceFactor < -1 && getBalanceFactor(root->right) <= 0) {
        return leftRotate(root);
    }
    if (balanceFactor < -1 && getBalanceFactor(root->right) > 0) {
        root->right = rightRotate(root->right);
        return leftRotate(root);
    }
    return root;
}

2. 前序遍历二叉树（递归）

void preOrder(TreeNode* root) {
    if (root == nullptr) return;
    cout << root->val << " ";
    preOrder(root->left);
    preOrder(root->right);
}

3. 中序遍历二叉树（递归）

void inOrder(TreeNode* root) {
    if (root == nullptr) return;
    inOrder(root->left);
    cout << root->val << " ";
    inOrder(root->right);
}

4. 后序遍历二叉树（递归）

void postOrder(TreeNode* root) {
    if (root == nullptr) return;
    postOrder(root->left);
    postOrder(root->right);
    cout << root->val << " ";
}

5. 前序遍历二叉树（非递归）

void preOrder2(TreeNode* root) {
    if (root == nullptr) return;
    stack<TreeNode*> st;
    st.push(root);
    while (!st.empty()) {
        TreeNode* node = st.top();
        st.pop();
        cout << node->val << " ";
        if (node->right) st.push(node->right);
        if (node->left) st.push(node->left);
    }
}

6. 中序遍历二叉树（非递归）

void inOrder2(TreeNode* root) {
    if (root == nullptr) return;
    stack<TreeNode*> st;
    TreeNode* node = root;
    while (node || !st.empty()) {
        while (node) {
            st.push(node);
            node = node->left;
        }
        node = st.top();
        st.pop();
        cout << node->val << " ";
        node = node->right;
    }
}

7. 后序遍历二叉树（非递归）

void postOrder2(TreeNode* root) {
    if (root == nullptr) return;
    stack<TreeNode*> st;
    TreeNode* prev = nullptr;
    st.push(root);
    while (!st.empty()) {
        TreeNode* node = st.top();
        if ((!node->left && !node->right) || (prev && (prev == node->left || prev == node->right))) {
            cout << node->val << " ";
            st.pop();
            prev = node;
        } else {
            if (node->right) st.push(node->right);
            if (node->left) st.push(node->left);
        }
    }
}

8. 层次遍历二叉树

void levelOrder(TreeNode* root) {
    if (root == nullptr) return;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            TreeNode* node = q.front();
            q.pop();
            cout << node->val << " ";
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
    }
}

9. 在二叉树中查找给定关键字

bool search(TreeNode* root, int val) {
    if (root == nullptr) return false;
    if (root->val == val) return true;
    if (val < root->val) return search(root->left, val);
    return search(root->right, val);
}

10. 交换各结点的左右子树

void swapLeftRight(TreeNode* root) {
    if (root == nullptr) return;
    swap(root->left, root->right);
    swapLeftRight(root->left);
    swapLeftRight(root->right);
}

11. 求二叉树的深度

int getDepth(TreeNode* root) {
    if (root == nullptr) return 0;
    return max(getDepth(root->left), getDepth(root->right)) + 1;
}

12. 叶子结点数

int getLeafCount(TreeNode* root) {
    if (root == nullptr) return 0;
    if (root->left == nullptr && root->right == nullptr) return 1;
    return getLeafCount(root->left) + getLeafCount(root->right);
}

13. 删除某结点

TreeNode* deleteNode(TreeNode* root, int val) {
    if (root == nullptr) return nullptr;
    if (val < root->val) {
        root->left = deleteNode(root->left, val);
    } else if (val > root->val) {
        root->right = deleteNode(root->right, val);
    } else {
        if (root->left == nullptr || root->right == nullptr) {
            TreeNode* tmp = root->left ? root->left : root->right;
            delete root;
            root = tmp;
        } else {
            TreeNode* tmp = root->right;
            while (tmp->left) tmp = tmp->left;
            root->val = tmp->val;
            root->right = deleteNode(root->right, tmp->val);
        }
    }
    if (root == nullptr) return nullptr;
    updateHeight(root);
    int balanceFactor = getBalanceFactor(root);
    if (balanceFactor > 1 && getBalanceFactor(root->left) >= 0) {
        return rightRotate(root);
    }
    if (balanceFactor > 1 && getBalanceFactor(root->left) < 0) {
        root->left = leftRotate(root->left);
        return rightRotate(root);
    }
    if (balanceFactor < -1 && getBalanceFactor(root->right) <= 0) {
        return leftRotate(root);
    }
    if (balanceFactor < -1 && getBalanceFactor(root->right) > 0) {
        root->right = rightRotate(root->right);
        return leftRotate(root);
    }
    return root;
}