TreeNode.cpp

//顶级垃圾程序
//A very bad program
#include <bits/stdc++.h>
using namespace std;

string s;
int num;
vector<int> nums;
vector<int> v1, v2, v3, v4;
struct TreeNode { // 定义二叉树的结点结构体
    int val; // 结点的值
    TreeNode *left; // 左子结点
    TreeNode *right; // 右子结点
    TreeNode() : val(INT_MIN), left(nullptr), right(nullptr) {} // 构造函数
    TreeNode(int _val) : val(_val), left(nullptr), right(nullptr) {} // 构造函数
    TreeNode(int _val, TreeNode *_left, TreeNode *_right) : val(_val), left(_left), right(_right) {} // 构造函数
};
TreeNode *buildTree(vector<int> &nums, int index){
	if (index >= int(nums.size()) || nums[index] == INT_MIN){
		return nullptr;
	}
	TreeNode *root = new TreeNode(nums[index]);
	root->left = buildTree(nums, 2 * index + 1); //左子树的索引=它的根节点的下标 * 2 + 1(下标为0
	root->right = buildTree(nums, 2 * index + 2);//右子树的索引=它的根节点的下标 * 2 + 2(下标为0
	return root;
}
void printLeverOrder(TreeNode *root){
	// 初始化队列，加入根节点
    queue<TreeNode *> queue;
    queue.push(root);
    // 初始化一个列表，用于保存遍历序列
    while (!queue.empty()) {
        TreeNode *node = queue.front();
        queue.pop();              // 队列出队
        v1.push_back(node->val); // 保存节点值
        if (node->left != nullptr)
            queue.push(node->left); // 左子节点入队
        if (node->right != nullptr)
            queue.push(node->right); // 右子节点入队
    }
}
/* 前序遍历 */
void preOrder(TreeNode *root) {
    if (!root)
        return;
    // 访问优先级：根节点 -> 左子树 -> 右子树
    v2.push_back(root->val);
    preOrder(root->left);
    preOrder(root->right);
}

/* 中序遍历 */
void inOrder(TreeNode *root) {
    if (root == nullptr)
        return;
    // 访问优先级：左子树 -> 根节点 -> 右子树
    inOrder(root->left);
    v3.push_back(root->val);
    inOrder(root->right);
}

/* 后序遍历 */
void postOrder(TreeNode *root) {
    if (root == nullptr)
        return;
    // 访问优先级：左子树 -> 右子树 -> 根节点
    postOrder(root->left);
    postOrder(root->right);
    v4.push_back(root->val);
}
int main(){
    while (cin >> s) {
        if (s == "null") num = INT_MIN; // 如果s等于null，num等于 INT_MIN
        else num = stoi(s.c_str()); // 否则num等于s
        nums.push_back(num);
        if (cin.get() == '\n') break;
    } 
    TreeNode *root = buildTree(nums, 0); // 建立二叉树
    printLeverOrder(root);
	preOrder(root);
    inOrder(root);
	postOrder(root);
    cout << "层序遍历:" << endl;
    for (auto at : v1) cout << at << " ";
    cout << endl;
    cout << "前序遍历:" << endl;
    for (auto at : v2) cout << at << " ";
    cout << endl;
    cout << "中序遍历:" << endl;
    for (auto at : v3) cout << at << " ";
    cout << endl;
    cout << "后序遍历:" << endl;
    for (auto at : v4) cout << at << " ";
    cout << endl;
	return 0;
}