C++实现（根据vector输入得到并中序打印二叉树）

糖逗

要求描述：根据vector构建二叉树
例如 1 2 3 4 5 6 7 得到：图1

#include <iostream>
#include <vector>
#include <string>
#include<malloc.h>
#include <math.h> 

using namespace std;


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


TreeNode* CreateTree(vector<int>& input){
        TreeNode* tree = (TreeNode*)malloc(sizeof(TreeNode)*input.size());
        for(int i = 0; i < input.size() ;i++){
                tree[i].val = input[i];
                tree[i].left = NULL;
                tree[i].right = NULL;
                
        }
        for(int i = 0; i <= input.size()/2-1; i++){
                if(2*i+1 <= input.size()){
                        tree[i].left = &tree[2*i+1]; 
                }
                if(2*i+2<=input.size()){
                        tree[i].right = &tree[2*i+2];
                }
        }
        return tree;
}


void middle(TreeNode* root, vector<vector<int> >& res, int left, int right, int depth){
    if(root == NULL) return;
    int insert = left + (right - left) / 2;
    res[depth][insert] = root->val;
            
    middle(root->left, res, left, insert - 1, depth + 1);
    middle(root->right, res, insert + 1, right, depth + 1);
    }

int treeDepth(TreeNode* root){
    if(root == NULL) return 0;
    return max(treeDepth(root->left) + 1, treeDepth(root->right) + 1);
    }
        
vector<vector<int> > printTree(TreeNode* root) {
    int depth = treeDepth(root);
    int width = pow(2, depth) - 1;
    vector<vector<int> > res(depth, vector<int>(width, 0));
    middle(root, res, 0, width - 1, 0);
    return res;
    }



int main(void){
        vector<int>input;
        int number;
        cout << "please send numbers for this tree:" << endl;
        while(cin >> number){
                input.push_back(number);
        }
        TreeNode* root = CreateTree(input);
        vector<vector<int> > res = printTree(root);
        for(int i = 0; i < res.size(); i++){
                for(int j = 0; j < res[i].size();j++){
                        if(res[i][j] == 0){
                                cout  << " ";
                        }
                        else{
                                cout << res[i][j];
                        }
                        
                }
                cout << endl;
        }

        return 0;
}

糖逗