level-order traversal

层序遍历是一种二叉树的遍历方式，它按照从上到下、从左到右的顺序遍历二叉树的每个节点。具体实现方式是使用队列来存储每一层的节点，先将根节点入队，然后依次出队每个节点，并将其左右子节点入队，直到队列为空。这样就可以按照层次顺序遍历整个二叉树。

相关问题

代码改进，用printf代替cout。#include <iostream> #include <queue> #include <stack> #include <string> using namespace std; struct Student { string name; int number; int score; }; struct TreeNode { Student data; TreeNode* left; TreeNode* right; TreeNode(Student s) : data(s), left(nullptr), right(nullptr) {} }; void postOrder(TreeNode* root) { if (!root) return; postOrder(root->left); postOrder(root->right); cout << root->data.name << " " << root->data.number << " " << root->data.score << endl; } void preOrder(TreeNode* root) { stack<TreeNode*> s; s.push(root); while (!s.empty()) { TreeNode* node = s.top(); s.pop(); if (node) { cout << node->data.name << " " << node->data.number << " " << node->data.score << endl; s.push(node->right); s.push(node->left); } } } void levelOrder(TreeNode* root) { queue<TreeNode*> q; q.push(root); while (!q.empty()) { TreeNode* node = q.front(); q.pop(); if (node) { cout << node->data.name << " " << node->data.number << " " << node->data.score << endl; q.push(node->left); q.push(node->right); } } } int main() { Student students[] = { {"Lei Zhenzi", 101401, 82}, {"Jiang Ziya", 100032, 90}, {"Ne Zha", 101674, 70}, {"Shen Gongbao", 101982, 87}, {"Jiu Weihu", 107431, 75}, {"Tian Zun", 100001, 98}, {"Tai Yi", 101009, 81}, {"Yang Jian", 101321, 63}, {"Huang Feihu", 101567, 72}, {"Zhou Wang", 108160, 55}, {"Li Jing", 102456, 84}, {"Tu Xingsun", 102245, 65}, }; int n = sizeof(students) / sizeof(Student); TreeNode* root = new TreeNode(students[0]); queue<TreeNode*> q; q.push(root); for (int i = 1; i < n; i += 2) { TreeNode* parent = q.front(); q.pop(); parent->left = new TreeNode(students[i]); q.push(parent->left); if (i + 1 < n) { parent->right = new TreeNode(students[i + 1]); q.push(parent->right); } } cout << "Post-order traversal: " << endl; postOrder(root); cout << "Pre-order traversal: " << endl; preOrder(root); cout << "Level-order traversal: " << endl; levelOrder(root); return 0; }

好的，这里是使用 printf 替换 cout 后的代码：

#include <cstdio>
#include <queue>
#include <stack>
#include <string>

using namespace std;

struct Student {
string name;
int number;
int score;
};

struct TreeNode {
Student data;
TreeNode* left;
TreeNode* right;
TreeNode(Student s) : data(s), left(nullptr), right(nullptr) {}
};

void postOrder(TreeNode* root) {
if (!root) return;
postOrder(root->left);
postOrder(root->right);
printf("%s %d %d\n", root->data.name.c_str(), root->data.number, root->data.score);
}

void preOrder(TreeNode* root) {
stack<TreeNode*> s;
s.push(root);
while (!s.empty()) {
TreeNode* node = s.top();
s.pop();
if (node) {
printf("%s %d %d\n", node->data.name.c_str(), node->data.number, node->data.score);
s.push(node->right);
s.push(node->left);
}
}
}

void levelOrder(TreeNode* root) {
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* node = q.front();
q.pop();
if (node) {
printf("%s %d %d\n", node->data.name.c_str(), node->data.number, node->data.score);
q.push(node->left);
q.push(node->right);
}
}
}

int main() {
Student students[] = {
{"Lei Zhenzi", 101401, 82},
{"Jiang Ziya", 100032, 90},
{"Ne Zha", 101674, 70},
{"Shen Gongbao", 101982, 87},
{"Jiu Weihu", 107431, 75},
{"Tian Zun", 100001, 98},
{"Tai Yi", 101009, 81},
{"Yang Jian", 101321, 63},
{"Huang Feihu", 101567, 72},
{"Zhou Wang", 108160, 55},
{"Li Jing", 102456, 84},
{"Tu Xingsun", 102245, 65},
};
int n = sizeof(students) / sizeof(Student);

TreeNode* root = new TreeNode(students[0]);
queue<TreeNode*> q;
q.push(root);
for (int i = 1; i < n; i += 2) {
TreeNode* parent = q.front();
q.pop();
parent->left = new TreeNode(students[i]);
q.push(parent->left);
if (i + 1 < n) {
parent->right = new TreeNode(students[i + 1]);
q.push(parent->right);
}
}

printf("Post-order traversal: \n");
postOrder(root);

printf("Pre-order traversal: \n");
preOrder(root);

printf("Level-order traversal: \n");
levelOrder(root);

return 0;
}

代码改进，用printf代替cout。#include <iostream> #include <queue> #include <string> using namespace std; struct Student { string name; int number; int score; }; struct TreeNode { Student data; TreeNode* left; TreeNode* right; TreeNode(Student s) : data(s), left(nullptr), right(nullptr) {} }; void inOrder(TreeNode* root) { if (!root) return; inOrder(root->left); cout << root->data.name << " " << root->data.number << " " << root->data.score << endl; inOrder(root->right); } TreeNode* insert(TreeNode* root, Student s) { if (!root) return new TreeNode(s); if (s.number < root->data.number) { root->left = insert(root->left, s); } else { root->right = insert(root->right, s); } return root; } TreeNode* search(TreeNode* root, string name) { if (!root) return nullptr; if (name == root->data.name) { return root; } else if (name < root->data.name) { return search(root->left, name); } else { return search(root->right, name); } } void print(TreeNode* root) { if (!root) return; if (root->data.score <= 75) { cout << root->data.name << " " << root->data.number << " " << root->data.score << endl; } print(root->left); print(root->right); } int main() { Student students[] = { {"Lei Zhenzi", 101401, 82}, {"Jiang Ziya", 100032, 90}, {"Ne Zha", 101674, 70}, {"Shen Gongbao", 101982, 87}, {"Jiu Weihu", 107431, 75}, {"Tian Zun", 100001, 98}, {"Tai Yi", 101009, 81}, {"Yang Jian", 101321, 63}, {"Huang Feihu", 101567, 72}, {"Zhou Wang", 108160, 55}, {"Li Jing", 102456, 84}, {"Tu Xingsun", 102245, 65}, }; int n = sizeof(students) / sizeof(Student); TreeNode* root = nullptr; for (int i = 0; i < n; i++) { root = insert(root, students[i]); } cout << "In-order traversal: " << endl; inOrder(root); cout << "Level-order traversal: " << endl; queue<TreeNode*> q; q.push(root); while (!q.empty()) { TreeNode* node = q.front(); q.pop(); if (node) { cout << node->data.name << " " << node->data.number << " " << node->data.score << endl; q.push(node->left); q.push(node->right); } } cout << "Search for Tai Yi: " << endl; TreeNode* node = search(root, "Tai Yi"); if (node) { cout << node->data.name << " " << node->data.number << " " << node->data.score << endl; } else { cout << "Not found." << endl; } cout << "Students with score <= 75: " << endl; print(root); return 0; }

以下是使用printf替换cout后的改进代码：

#include <iostream>
#include <queue>
#include <string>
using namespace std;

struct Student {
    string name;
    int number;
    int score;
};

struct TreeNode {
    Student data;
    TreeNode* left;
    TreeNode* right;
    TreeNode(Student s) : data(s), left(nullptr), right(nullptr) {}
};

void inOrder(TreeNode* root) {
    if (!root) return;
    inOrder(root->left);
    printf("%s %d %d\n", root->data.name.c_str(), root->data.number, root->data.score);
    inOrder(root->right);
}

TreeNode* insert(TreeNode* root, Student s) {
    if (!root) return new TreeNode(s);
    if (s.number < root->data.number) {
        root->left = insert(root->left, s);
    } else {
        root->right = insert(root->right, s);
    }
    return root;
}

TreeNode* search(TreeNode* root, string name) {
    if (!root) return nullptr;
    if (name == root->data.name) {
        return root;
    } else if (name < root->data.name) {
        return search(root->left, name);
    } else {
        return search(root->right, name);
    }
}

void print(TreeNode* root) {
    if (!root) return;
    if (root->data.score <= 75) {
        printf("%s %d %d\n", root->data.name.c_str(), root->data.number, root->data.score);
    }
    print(root->left);
    print(root->right);
}

int main() {
    Student students[] = {
        {"Lei Zhenzi", 101401, 82},
        {"Jiang Ziya", 100032, 90},
        {"Ne Zha", 101674, 70},
        {"Shen Gongbao", 101982, 87},
        {"Jiu Weihu", 107431, 75},
        {"Tian Zun", 100001, 98},
        {"Tai Yi", 101009, 81},
        {"Yang Jian", 101321, 63},
        {"Huang Feihu", 101567, 72},
        {"Zhou Wang", 108160, 55},
        {"Li Jing", 102456, 84},
        {"Tu Xingsun", 102245, 65},
    };
    int n = sizeof(students) / sizeof(Student);
    TreeNode* root = nullptr;
    for (int i = 0; i < n; i++) {
        root = insert(root, students[i]);
    }
    printf("In-order traversal: \n");
    inOrder(root);
    printf("Level-order traversal: \n");
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();
        if (node) {
            printf("%s %d %d\n", node->data.name.c_str(), node->data.number, node->data.score);
            q.push(node->left);
            q.push(node->right);
        }
    }
    printf("Search for Tai Yi: \n");
    TreeNode* node = search(root, "Tai Yi");
    if (node) {
        printf("%s %d %d\n", node->data.name.c_str(), node->data.number, node->data.score);
    } else {
        printf("Not found.\n");
    }
    printf("Students with score <= 75: \n");
    print(root);
    return 0;
}

使用printf的好处是可以提高输出效率，特别是当需要输出大量的数据时，printf的效率要比cout高。除此之外，printf的格式化输出优势也非常明显，格式化后的输出更加美观易读。