python/TangDou/XiTi/1404.cpp

#include <bits/stdc++.h>

using namespace std;

#pragma region 二叉树模板

//二叉树结点结构
typedef struct Node {
    string data;                            //结点数据
    struct Node *left;                  //左孩子
    struct Node *right;                 //右孩子
} *Tree; //定义了一个指针，这个指针是一个TreeNode的指针


//通过字符串数据，按层遍历反向构建完全二叉树
Tree RebuildCompleteBinaryTree(string *arr, int n) {
    //构建一个指针组成的数组
    vector<Tree> trees;
    //遍历每一个字符串数组中的字符串，构建指针，然后将指针添加到指针数组中去
    for (int i = 0; i < n; i++) {
        //实例化指针
        Tree tree = new Node();
        tree->data = arr[i];//指针为->，对象为.
        tree->left = NULL;
        tree->right = NULL;
        trees.push_back(tree);
    }
    //从下往上遍历
    /*
                  0
              1      2
            3   4  5   6
     */
    for (int i = trees.size() - 1; i > 0; i--) {
        //奇数
        if (i % 2 != 0) {
            trees[(i - 1) / 2]->left = trees[i];  //好巧妙的 (i-1)/2，这个除法是整数除法，还带取整的，牛！
        } else//偶数
        {
            trees[(i - 1) / 2]->right = trees[i]; //好巧妙的 (i-1)/2，这个除法是整数除法，还带取整的，牛！
        }
    }
    return trees[0];//返回根节点
}


//前序遍历
void PreOrderTraverse(Tree T) {
    //利用递归前序输出二叉树
    if (T) {
        cout << T->data << " ";
        PreOrderTraverse(T->left);
        PreOrderTraverse(T->right);
    }
}

//中序遍历
void InOrderTraverse(Tree T) {
    //利用递归中序输出二叉树
    if (T) {
        InOrderTraverse(T->left);
        cout << T->data << " ";
        InOrderTraverse(T->right);
    }
}

//后序遍历
void PostOrderTraverse(Tree T) {
    //利用递归后序输出二叉树
    if (T) {
        PostOrderTraverse(T->left);
        PostOrderTraverse(T->right);
        cout << T->data << " ";
    }
}

// level : 用来控制是第几层的，默认为第0层，每一层增加1
// 容器   : vector<vector<Tree>> &vec
// 层序遍历(递归的核心函数)
void PreLevelOrderTraverse(Tree T, int level, vector<vector<Tree>> &vec) {
    //如果当前节点不是空
    if (T) {
        //如果当前行数不够，换句话说，就是又该新增加一层的时候，声明一个数组，追加上去。
        if (vec.size() < level + 1) {
            vector<Tree> arr;
            vec.push_back(arr);
        }

        //将当前的指针保存到数组中
        vec[level].push_back(T);

        //递归左子树
        PreLevelOrderTraverse(T->left, level + 1, vec);

        //递归右子树
        PreLevelOrderTraverse(T->right, level + 1, vec);
    }
}

//层次遍历
void LevelOrderTraverse(Tree T) {
    if (T) {
        vector<vector<Tree>> vec;

        //通过层序递归遍历进行构建
        PreLevelOrderTraverse(T, 0, vec);

        //输出构建结果
        for (int i = 0; i < vec.size(); i++) {
            for (int j = 0; j < vec[i].size(); j++) {
                cout << vec[i][j]->data << " ";
            }
            cout << endl;
        }
    }
}

#pragma endregion 二叉树模板
int main() {
    //输入+输出重定向
    //freopen("../x.in", "r", stdin);
    //freopen("../x.out", "w", stdout);

    string s;
    cin >> s;

    string arr[1000];
    for (int i = 0; i < s.size(); ++i) {
        arr[i] = s[i];
    }

    Tree root = RebuildCompleteBinaryTree(arr, s.size());
    PreOrderTraverse(root);
    //关闭文件
    //fclose(stdin);
    //fclose(stdout);
    return 0;
}