用C++编写建立二叉树，层序、先序遍历 1、问题描述 要求能够输入树的各个结点，并能够输出用不同方法遍历的遍历序列；分别建立建立二叉树存储结构的的输入函数、输出层序遍历序列的函数、输出先序遍历序列的函数； 请写明：存储结构、基本算法（可以使用程序流程图）、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法。\

1. 存储结构：采用链式存储结构，每个节点包含左子树指针、右子树指针和数据域。

2. 基本算法：

输入函数：

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
TreeNode* BuildTree() { // 输入二叉树节点值，0表示空节点
    int val;
    cin >> val;
    if (val == 0) {
        return NULL;
    }
    TreeNode* root = new TreeNode(val);
    root->left = BuildTree();
    root->right = BuildTree();
    return root;
}

输出层序遍历序列的函数：

vector<int> LevelOrder(TreeNode* root) {
    vector<int> res;
    if (root == NULL) {
        return res;
    }
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* cur = q.front();
        q.pop();
        res.push_back(cur->val);
        if (cur->left) {
            q.push(cur->left);
        }
        if (cur->right) {
            q.push(cur->right);
        }
    }
    return res;
}

输出先序遍历序列的函数：

vector<int> PreOrder(TreeNode* root) {
    vector<int> res;
    if (root == NULL) {
        return res;
    }
    stack<TreeNode*> st;
    st.push(root);
    while (!st.empty()) {
        TreeNode* cur = st.top();
        st.pop();
        res.push_back(cur->val);
        if (cur->right) {
            st.push(cur->right);
        }
        if (cur->left) {
            st.push(cur->left);
        }
    }
    return res;
}

3. 源程序：

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
TreeNode* BuildTree() { // 输入二叉树节点值，0表示空节点
    int val;
    cin >> val;
    if (val == 0) {
        return NULL;
    }
    TreeNode* root = new TreeNode(val);
    root->left = BuildTree();
    root->right = BuildTree();
    return root;
}
vector<int> LevelOrder(TreeNode* root) {
    vector<int> res;
    if (root == NULL) {
        return res;
    }
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* cur = q.front();
        q.pop();
        res.push_back(cur->val);
        if (cur->left) {
            q.push(cur->left);
        }
        if (cur->right) {
            q.push(cur->right);
        }
    }
    return res;
}
vector<int> PreOrder(TreeNode* root) {
    vector<int> res;
    if (root == NULL) {
        return res;
    }
    stack<TreeNode*> st;
    st.push(root);
    while (!st.empty()) {
        TreeNode* cur = st.top();
        st.pop();
        res.push_back(cur->val);
        if (cur->right) {
            st.push(cur->right);
        }
        if (cur->left) {
            st.push(cur->left);
        }
    }
    return res;
}
int main() {
    TreeNode* root = BuildTree();
    vector<int> levelOrder = LevelOrder(root);
    vector<int> preOrder = PreOrder(root);
    cout << "层序遍历序列：";
    for (int i = 0; i < levelOrder.size(); i++) {
        cout << levelOrder[i] << " ";
    }
    cout << endl;
    cout << "先序遍历序列：";
    for (int i = 0; i < preOrder.size(); i++) {
        cout << preOrder[i] << " ";
    }
    cout << endl;
    return 0;
}

4. 测试数据和结果：

输入：

1
2
4
0
0
5
0
0
3
6
0
0
7
0
0

输出：

层序遍历序列：1 2 3 4 5 6 7 
先序遍历序列：1 2 4 5 3 6 7 

5. 时间复杂度：

输入函数的时间复杂度为 $O(n)$，其中 $n$ 是二叉树的节点数。

输出层序遍历序列的函数的时间复杂度为 $O(n)$。

输出先序遍历序列的函数的时间复杂度为 $O(n)$。

6. 改进方法：

可以使用递归实现先序遍历，使用迭代实现后序遍历和中序遍历。同时，可以优化层序遍历的空间复杂度，使用双向队列可以将空间复杂度降到 $O(1)$。