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

糖逗

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

1. #include <iostream>
   
2. #include <vector>
   
3. #include <string>
   
4. #include<malloc.h>
   
5. #include <math.h>
   
6. 
   
7. using namespace std;
   
8. 
   
9. 
   
10. struct TreeNode{
    
11.         int val;
    
12.         TreeNode* left;
    
13.         TreeNode* right;
    
14.         TreeNode(int x): val(x), left(NULL), right(NULL){
    
15.         }
    
16. };
    
17. 
    
18. 
    
19. TreeNode* CreateTree(vector<int>& input){
    
20.         TreeNode* tree = (TreeNode*)malloc(sizeof(TreeNode)*input.size());
    
21.         for(int i = 0; i < input.size() ;i++){
    
22.                 tree[i].val = input[i];
    
23.                 tree[i].left = NULL;
    
24.                 tree[i].right = NULL;
    
25.                
    
26.         }
    
27.         for(int i = 0; i <= input.size()/2-1; i++){
    
28.                 if(2*i+1 <= input.size()){
    
29.                         tree[i].left = &tree[2*i+1];
    
30.                 }
    
31.                 if(2*i+2<=input.size()){
    
32.                         tree[i].right = &tree[2*i+2];
    
33.                 }
    
34.         }
    
35.         return tree;
    
36. }
    
37. 
    
38. 
    
39. void middle(TreeNode* root, vector<vector<int> >& res, int left, int right, int depth){
    
40.     if(root == NULL) return;
    
41.     int insert = left + (right - left) / 2;
    
42.     res[depth][insert] = root->val;
    
43.            
    
44.     middle(root->left, res, left, insert - 1, depth + 1);
    
45.     middle(root->right, res, insert + 1, right, depth + 1);
    
46.     }
    
47. 
    
48. int treeDepth(TreeNode* root){
    
49.     if(root == NULL) return 0;
    
50.     return max(treeDepth(root->left) + 1, treeDepth(root->right) + 1);
    
51.     }
    
52.        
    
53. vector<vector<int> > printTree(TreeNode* root) {
    
54.     int depth = treeDepth(root);
    
55.     int width = pow(2, depth) - 1;
    
56.     vector<vector<int> > res(depth, vector<int>(width, 0));
    
57.     middle(root, res, 0, width - 1, 0);
    
58.     return res;
    
59.     }
    
60. 
    
61. 
    
62. 
    
63. int main(void){
    
64.         vector<int>input;
    
65.         int number;
    
66.         cout << "please send numbers for this tree:" << endl;
    
67.         while(cin >> number){
    
68.                 input.push_back(number);
    
69.         }
    
70.         TreeNode* root = CreateTree(input);
    
71.         vector<vector<int> > res = printTree(root);
    
72.         for(int i = 0; i < res.size(); i++){
    
73.                 for(int j = 0; j < res[i].size();j++){
    
74.                         if(res[i][j] == 0){
    
75.                                 cout  << " ";
    
76.                         }
    
77.                         else{
    
78.                                 cout << res[i][j];
    
79.                         }
    
80.                        
    
81.                 }
    
82.                 cout << endl;
    
83.         }
    
84. 
    
85.         return 0;
    
86. }
    
87. 
    
88. 
    

复制代码

糖逗