#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; // 返回程序执行结果正常退出。
}