#include #include #include

// 定义一个学生结构体 typedef struct student {

char name[20];  // 学生姓名
int number;     // 学号
int score;      // 分数

} Student;

// 定义二叉树结点结构体 typedef struct node {

Student data;           // 结点数据，即学生信息
struct node *left;      // 左子结点指针
struct node *right;     // 右子结点指针

} Node;

// 创建一个新结点函数，传入一个学生信息，返回创建的二叉树结点指针 Node *new_node(Student data) {

Node *node = (Node *)malloc(sizeof(Node));  // 动态分配空间创建新结点，并将其地址赋给指针变量node
node->data = data;  // 将传入的学生信息保存到新结点中的数据域中
node->left = NULL;  // 初始化左右子树为空指针NULL
node->right = NULL;
return node;        // 返回新创建的二叉树结点的指针变量node

}

// 按层次遍历的顺序构造完全二叉树函数，传入存放学生信息的数组和数组长度n，返回构建好的完全二叉树根节点指针。 Node *build_complete_binary_tree(Student students[], int n) {

Node *root = new_node(students[0]);     // 先以第一个学生信息创建根节点
Node *queue[n];                         // 创建一个指针数组，用于辅助构建完全二叉树
int front = 0, rear = 0;                // 定义队列的头和尾指针，用于存储新创建的结点
queue[rear++] = root;                   // 将根节点入队列
for (int i = 1; i < n; i++) {           // 循环遍历剩余的n-1个学生信息
    Node *node = new_node(students[i]); // 以当前学生信息创建一个新结点node
    queue[rear++] = node;               // 将新结点node入队列
    if (rear % 2 == 0) {                // 如果队尾是偶数，则说明前面有一对兄弟结点没有右子树，当前结点可以作为他们的右子树。
        queue[front]->left = node;      // 设置前面那个兄弟结点的左子树为当前结点。
    } else {
        queue[front]->right = node;     // 否则，前面那个兄弟结点已经有左右子树了，将当前结点作为后面未来某个兄弟结点的左子树。
        front++;                        // 并将头指针向后移动到下一组兄弟结点位置。
    }
}
return root;                            // 返回完整构建好的完全二叉树根节点指针。

}

// 后序遍历二叉树（递归函数），传入二叉树根节点指针，输出每个结点的学生信息。 void postorder_traversal_recursive(Node *root) {

if (root == NULL) {     // 如果当前结点为空，则直接返回
    return;
}
postorder_traversal_recursive(root->left);   // 递归遍历左子树
postorder_traversal_recursive(root->right);  // 递归遍历右子树
printf("%s %d %d\n", root->data.name, root->data.number, root->data.score);  // 输出当前结点的学生信息。

}

// 先序遍历二叉树（非递归函数），传入二叉树根节点指针，输出每个结点的学生信息。 void preorder_traversal_nonrecursive(Node *root) {

if (root == NULL) {     // 如果当前结点为空，则直接返回
    return;
}
Node *stack[100];       // 创建一个指针数组作为堆栈，用于辅助实现非递归先序遍历。
int top = 0;            // 定义堆栈顶部指针
stack[top++] = root;    // 将根节点压入堆栈中
while (top > 0) {       // 当堆栈不为空时循环执行以下操作：
    Node *node = stack[--top];          // 取出堆栈顶部结点
    printf("%s %d %d\n", node->data.name, node->data.number, node->data.score);  // 输出当前结点的学生信息。
    if (node->right != NULL) {          // 如果当前结点有右子树，则将其压入堆栈中
        stack[top++] = node->right;
    }
    if (node->left != NULL) {           // 如果当前结点有左子树，则将其压入堆栈中（注意先压右子树再压左子树，保证先遍历左子树）
        stack[top++] = node->left;
    }
}

}

// 广度优先遍历二叉树函数，传入二叉树根节点指针，输出每个结点的学生信息。 void breadth_first_traversal(Node *root) {

if (root == NULL) {     // 如果当前结点为空，则直接返回
    return;
}
Node *queue[100];       // 创建一个指针数组作为队列，用于辅助实现广度优先遍历。
int front = 0, rear = 0;                // 定义队列的头和尾指针，用于存储新创建的结点
queue[rear++] = root;                   // 将根节点入队列
while (front < rear) {                  // 当队列不为空时循环执行以下操作：
    Node *node = queue[front++];                // 取出队首元素（即当前要访问的结点）
    printf("%s %d %d\n", node->data.name, node->data.number, node->data.score);  // 输出当前结点的学生信息。
    if (node->left != NULL) {           // 如果当前结点有左子树，则将其压入队列中
        queue[rear++] = node->left;
    }
    if (node->right != NULL) {          // 如果当前结点有右子树，则将其压入队列中
        queue[rear++] = 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(students[0]);   // 计算出学生信息数组的长度n
Node *root = build_complete_binary_tree(students,n);   // 构建完全二叉树，并返回根节点指针存储在变量root中。
printf("后序遍历：\n");
postorder_traversal_recursive(root);                // 后序遍历二叉树，并输出每个结点的学生信息
printf("先序遍历：\n");
preorder_traversal_nonrecursive(root);              // 先序遍历二叉树（非递归），并输出每个结点的学生信息
printf("广度优先遍历：\n");
breadth_first_traversal(root);                      // 广度优先遍历二叉树，并输出每个结点的学生信息
return 0;                                           // 返回程序执行结果正常退出。

}