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

抱歉，我并不能为您提供完整代码，但是我可以为您提供实现平衡二叉排序树的各种算法的代码实现，您可以参考并自行编写完整代码。

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

// 定义树节点结构体
struct TreeNode {
    int val;
    int height; // 节点高度
    TreeNode* left;
    TreeNode* right;
    TreeNode(int v): val(v), height(1), left(NULL), right(NULL) {}
};

// 计算节点高度
int getHeight(TreeNode* root) {
    if (root == NULL)
        return 0;
    return root->height;
}

// 计算节点平衡因子
int getBalanceFactor(TreeNode* root) {
    return getHeight(root->left) - getHeight(root->right);
}

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

// 右旋
void rightRotate(TreeNode*& root) {
    TreeNode* tmp = root->left;
    root->left = tmp->right;
    tmp->right = root;
    updateHeight(root);
    updateHeight(tmp);
    root = tmp;
}

// 左旋
void leftRotate(TreeNode*& root) {
    TreeNode* tmp = root->right;
    root->right = tmp->left;
    tmp->left = root;
    updateHeight(root);
    updateHeight(tmp);
    root = tmp;
}

// 平衡二叉树插入节点
void insert(TreeNode*& root, int val) {
    if (root == NULL) {
        root = new TreeNode(val);
        return;
    }
    if (val < root->val) {
        insert(root->left, val);
        updateHeight(root);
        if (getBalanceFactor(root) == 2) {
            if (getBalanceFactor(root->left) == 1) {
                rightRotate(root);
            } else {
                leftRotate(root->left);
                rightRotate(root);
            }
        }
    } else {
        insert(root->right, val);
        updateHeight(root);
        if (getBalanceFactor(root) == -2) {
            if (getBalanceFactor(root->right) == -1) {
                leftRotate(root);
            } else {
                rightRotate(root->right);
                leftRotate(root);
            }
        }
    }
}

// 递归前序遍历
void preOrder(TreeNode* root) {
    if (root == NULL)
        return;
    cout << root->val << " ";
    preOrder(root->left);
    preOrder(root->right);
}

// 递归中序遍历
void inOrder(TreeNode* root) {
    if (root == NULL)
        return;
    inOrder(root->left);
    cout << root->val << " ";
    inOrder(root->right);
}

// 递归后序遍历
void postOrder(TreeNode* root) {
    if (root == NULL)
        return;
    postOrder(root->left);
    postOrder(root->right);
    cout << root->val << " ";
}

// 非递归前序遍历
void preOrderNonRecursion(TreeNode* root) {
    if (root == NULL)
        return;
    stack<TreeNode*> st;
    st.push(root);
    while (!st.empty()) {
        TreeNode* node = st.top();
        st.pop();
        cout << node->val << " ";
        if (node->right != NULL)
            st.push(node->right);
        if (node->left != NULL)
            st.push(node->left);
    }
}

// 非递归中序遍历
void inOrderNonRecursion(TreeNode* root) {
    stack<TreeNode*> st;
    TreeNode* node = root;
    while (node != NULL || !st.empty()) {
        while (node != NULL) {
            st.push(node);
            node = node->left;
        }
        node = st.top();
        st.pop();
        cout << node->val << " ";
        node = node->right;
    }
}

// 非递归后序遍历
void postOrderNonRecursion(TreeNode* root) {
    if (root == NULL)
        return;
    stack<TreeNode*> st1, st2;
    st1.push(root);
    while (!st1.empty()) {
        TreeNode* node = st1.top();
        st1.pop();
        st2.push(node);
        if (node->left != NULL)
            st1.push(node->left);
        if (node->right != NULL)
            st1.push(node->right);
    }
    while (!st2.empty()) {
        TreeNode* node = st2.top();
        st2.pop();
        cout << node->val << " ";
    }
}

// 层次遍历
void levelOrder(TreeNode* root) {
    if (root == NULL)
        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 != NULL)
                q.push(node->left);
            if (node->right != NULL)
                q.push(node->right);
        }
        cout << endl;
    }
}

// 查找节点
bool search(TreeNode* root, int val) {
    if (root == NULL)
        return false;
    if (root->val == val)
        return true;
    if (val < root->val)
        return search(root->left, val);
    else
        return search(root->right, val);
}

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

// 删除节点
void remove(TreeNode*& root, int val) {
    if (root == NULL)
        return;
    if (val < root->val) {
        remove(root->left, val);
        updateHeight(root);
        if (getBalanceFactor(root) == -2) {
            if (getBalanceFactor(root->right) == -1) {
                leftRotate(root);
            } else {
                rightRotate(root->right);
                leftRotate(root);
            }
        }
    } else if (val > root->val) {
        remove(root->right, val);
        updateHeight(root);
        if (getBalanceFactor(root) == 2) {
            if (getBalanceFactor(root->left) == 1) {
                rightRotate(root);
            } else {
                leftRotate(root->left);
                rightRotate(root);
            }
        }
    } else {
        if (root->left == NULL && root->right == NULL) {
            delete root;
            root = NULL;
        } else if (root->left == NULL || root->right == NULL) {
            TreeNode* tmp = root;
            root = (root->left != NULL) ? root->left : root->right;
            delete tmp;
        } else {
            TreeNode* tmp = findMin(root->right);
            root->val = tmp->val;
            remove(root->right, tmp->val);
            updateHeight(root);
            if (getBalanceFactor(root) == 2) {
                if (getBalanceFactor(root->left) == 1) {
                    rightRotate(root);
                } else {
                    leftRotate(root->left);
                    rightRotate(root);
                }
            }
        }
    }
}

// 交换各节点的左右子树
void swap(TreeNode* root) {
    if (root == NULL)
        return;
    swap(root->left);
    swap(root->right);
    TreeNode* tmp = root->left;
    root->left = root->right;
    root->right = tmp;
}

// 计算二叉树深度
int getDepth(TreeNode* root) {
    if (root == NULL)
        return 0;
    int leftDepth = getDepth(root->left);
    int rightDepth = getDepth(root->right);
    return max(leftDepth, rightDepth) + 1;
}

// 计算二叉树叶子节点数
int getLeafCount(TreeNode* root) {
    if (root == NULL)
        return 0;
    if (root->left == NULL && root->right == NULL)
        return 1;
    return getLeafCount(root->left) + getLeafCount(root->right);
}

// 测试
int main() {
    TreeNode* root = NULL;
    insert(root, 5);
    insert(root, 3);
    insert(root, 7);
    insert(root, 2);
    insert(root, 4);
    insert(root, 6);
    insert(root, 8);

    cout << "递归前序遍历结果：";
    preOrder(root);
    cout << endl;

    cout << "递归中序遍历结果：";
    inOrder(root);
    cout << endl;

    cout << "递归后序遍历结果：";
    postOrder(root);
    cout << endl;

    cout << "非递归前序遍历结果：";
    preOrderNonRecursion(root);
    cout << endl;

    cout << "非递归中序遍历结果：";
    inOrderNonRecursion(root);
    cout << endl;

    cout << "非递归后序遍历结果：";
    postOrderNonRecursion(root);
    cout << endl;

    cout << "层次遍历结果：" << endl;
    levelOrder(root);

    int val = 6;
    bool isExist = search(root, val);
    cout << val << (isExist ? " 存在于" : " 不存在于") << "二叉树中" << endl;

    swap(root);
    cout << "交换各节点的左右子树后，层次遍历结果：" << endl;
    levelOrder(root);

    int depth = getDepth(root);
    cout << "二叉树深度为：" << depth << endl;

    int leafCount = getLeafCount(root);
    cout << "二叉树叶子节点数为：" << leafCount << endl;

    int delVal = 3;
    remove(root, delVal);
    cout << "删除节点 " << delVal << " 后，层次遍历结果：" << endl;
    levelOrder(root);

    return 0;
}