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

好的，我会尽力回答你的问题。以下是 C++ 实现平衡二叉排序树的各种算法，使用函数实现。

首先，我们需要定义一个平衡二叉排序树的结构体，包含左右子树指针和节点值：

struct AVLNode {
    int val;
    AVLNode* left;
    AVLNode* right;
};

### 插入新节点

插入新节点的算法需要考虑平衡二叉树的性质，即左子树和右子树的高度差不超过 1。我们可以使用递归实现：

AVLNode* insertNode(AVLNode* root, int val) {
    if (root == nullptr) {
        AVLNode* newNode = new AVLNode();
        newNode->val = val;
        newNode->left = nullptr;
        newNode->right = nullptr;
        return newNode;
    }

    if (val < root->val) {
        root->left = insertNode(root->left, val);
    } else {
        root->right = insertNode(root->right, val);
    }

    int balanceFactor = getBalanceFactor(root);
    if (balanceFactor > 1 && val < root->left->val) {
        return rightRotate(root);
    }
    if (balanceFactor < -1 && val > root->right->val) {
        return leftRotate(root);
    }
    if (balanceFactor > 1 && val > root->left->val) {
        root->left = leftRotate(root->left);
        return rightRotate(root);
    }
    if (balanceFactor < -1 && val < root->right->val) {
        root->right = rightRotate(root->right);
        return leftRotate(root);
    }

    return root;
}

其中，`getBalanceFactor` 函数用于计算节点的平衡因子，即左子树高度减右子树高度。`leftRotate` 和 `rightRotate` 用于左旋和右旋操作，调整平衡。

### 遍历二叉树

我们可以使用递归和非递归两种方式遍历二叉树。

#### 递归遍历

void preOrderTraversal(AVLNode* root) {
    if (root == nullptr) {
        return;
    }

    cout << root->val << " ";
    preOrderTraversal(root->left);
    preOrderTraversal(root->right);
}

void inOrderTraversal(AVLNode* root) {
    if (root == nullptr) {
        return;
    }

    inOrderTraversal(root->left);
    cout << root->val << " ";
    inOrderTraversal(root->right);
}

void postOrderTraversal(AVLNode* root) {
    if (root == nullptr) {
        return;
    }

    postOrderTraversal(root->left);
    postOrderTraversal(root->right);
    cout << root->val << " ";
}

#### 非递归遍历

void preOrderTraversalNonRecursive(AVLNode* root) {
    stack<AVLNode*> s;
    AVLNode* p = root;

    while (p != nullptr || !s.empty()) {
        while (p != nullptr) {
            cout << p->val << " ";
            s.push(p);
            p = p->left;
        }

        if (!s.empty()) {
            p = s.top();
            s.pop();
            p = p->right;
        }
    }
}

void inOrderTraversalNonRecursive(AVLNode* root) {
    stack<AVLNode*> s;
    AVLNode* p = root;

    while (p != nullptr || !s.empty()) {
        while (p != nullptr) {
            s.push(p);
            p = p->left;
        }

        if (!s.empty()) {
            p = s.top();
            s.pop();
            cout << p->val << " ";
            p = p->right;
        }
    }
}

void postOrderTraversalNonRecursive(AVLNode* root) {
    stack<AVLNode*> s1, s2;
    AVLNode* p = root;

    s1.push(p);
    while (!s1.empty()) {
        p = s1.top();
        s1.pop();
        s2.push(p);

        if (p->left != nullptr) {
            s1.push(p->left);
        }
        if (p->right != nullptr) {
            s1.push(p->right);
        }
    }

    while (!s2.empty()) {
        p = s2.top();
        s2.pop();
        cout << p->val << " ";
    }
}

### 层次遍历

层次遍历需要用到队列，我们可以从根节点开始，将其入队，然后依次出队，将其左右子节点入队，直到队列为空。

void levelOrderTraversal(AVLNode* root) {
    queue<AVLNode*> q;
    q.push(root);

    while (!q.empty()) {
        AVLNode* p = q.front();
        q.pop();
        cout << p->val << " ";

        if (p->left != nullptr) {
            q.push(p->left);
        }
        if (p->right != nullptr) {
            q.push(p->right);
        }
    }
}

### 查找给定关键字

查找给定关键字也可以使用递归实现：

bool searchNode(AVLNode* root, int val) {
    if (root == nullptr) {
        return false;
    }

    if (root->val == val) {
        return true;
    } else if (val < root->val) {
        return searchNode(root->left, val);
    } else {
        return searchNode(root->right, val);
    }
}

如果找到关键字，返回 true；否则返回 false。

### 交换左右子树

交换左右子树可以通过递归实现：

void swapSubtrees(AVLNode* root) {
    if (root == nullptr) {
        return;
    }

    swapSubtrees(root->left);
    swapSubtrees(root->right);

    AVLNode* temp = root->left;
    root->left = root->right;
    root->right = temp;
}

### 求二叉树深度

二叉树深度可以通过递归实现：

int getDepth(AVLNode* root) {
    if (root == nullptr) {
        return 0;
    }

    int leftDepth = getDepth(root->left);
    int rightDepth = getDepth(root->right);

    return max(leftDepth, rightDepth) + 1;
}

### 叶子节点数

叶子节点数也可以通过递归实现：

int getLeafCount(AVLNode* root) {
    if (root == nullptr) {
        return 0;
    }

    if (root->left == nullptr && root->right == nullptr) {
        return 1;
    }

    return getLeafCount(root->left) + getLeafCount(root->right);
}

### 删除某节点

删除某节点需要考虑平衡二叉树的性质，即删除节点后需要调整平衡。我们可以使用递归实现：

AVLNode* deleteNode(AVLNode* 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) {
            AVLNode* temp = root->left ? root->left : root->right;
            if (temp == nullptr) {
                temp = root;
                root = nullptr;
            } else {
                *root = *temp;
            }
            delete temp;
        } else {
            AVLNode* temp = getMinNode(root->right);
            root->val = temp->val;
            root->right = deleteNode(root->right, temp->val);
        }
    }

    if (root == nullptr) {
        return nullptr;
    }

    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;
}

AVLNode* getMinNode(AVLNode* node) {
    AVLNode* p = node;
    while (p->left != nullptr) {
        p = p->left;
    }
    return p;
}

其中，`getMinNode` 函数用于找到右子树中的最小节点，用于代替删除的节点。`leftRotate` 和 `rightRotate` 用于左旋和右旋操作，调整平衡。

以上就是 C++ 实现平衡二叉排序树的各种算法。