c++实现凹入表输出平衡二叉树

以下是C++实现凹入表输出平衡二叉树的代码和解释：

#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;

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

void printTree(TreeNode* root, int depth) {
    if (root == NULL) {
        return;
    }
    printTree(root->right, depth + 1);
    cout << setw(depth * 4) << root->val << endl;
    printTree(root->left, depth + 1);
}

void printTree(TreeNode* root) {
    int depth = 0;
    TreeNode* p = root;
    while (p != NULL) {
        depth++;
        p = p->left;
    }
    printTree(root, depth);
}

void buildTree(TreeNode*& root, int arr[], int start, int end) {
    if (start > end) {
        return;
    }
    int mid = (start + end) / 2;
    root = new TreeNode(arr[mid]);
    buildTree(root->left, arr, start, mid - 1);
    buildTree(root->right, arr, mid + 1, end);
}

int main() {
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int n = sizeof(arr) / sizeof(arr[0]);
    TreeNode* root = NULL;
    buildTree(root, arr, 0, n - 1);
    printTree(root);
    return 0;
}

代码解释：

1. 定义了一个结构体`TreeNode`，表示二叉树的节点，包含一个整数值`val`和左右子节点指针`left`和`right`。
2. `printTree`函数用于递归地输出平衡二叉树的凹入表形式，其中`depth`表示当前节点的深度。先递归输出右子树，再输出当前节点，最后递归输出左子树。
3. `printTree`函数的重载版本`printTree(TreeNode* root)`用于计算平衡二叉树的深度，并调用`printTree(TreeNode* root, int depth)`输出凹入表。
4. `buildTree`函数用于构建平衡二叉树，其中`start`和`end`表示当前子数组的起始和结束下标。每次取中间元素作为根节点，递归构建左右子树。
5. `main`函数中定义了一个有序数组`arr`，并调用`buildTree`函数构建平衡二叉树，最后调用`printTree`函数输出凹入表形式的平衡二叉树。