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.val = input;
tree.left = NULL;
tree.right = NULL;
}
for(int i = 0; i <= input.size()/2-1; i++){
if(2*i+1 <= input.size()){
tree.left = &tree;
}
if(2*i+2<=input.size()){
tree.right = &tree;
}
}
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 = 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.size();j++){
if(res == 0){
cout<< " ";
}
else{
cout << res;
}
}
cout << endl;
}
return 0;
}
{:10_312:}
页:
[1]