#include
typedef struct student{
char name[20];
int number;
int score;
} Student;
typedef struct node{
Student data; // 节点数据
struct node *left_child; // 左子节点指针
struct node *right_child; // 右子节点指针
} Node, *Tree; // 树的节点定义
void postorder_recursive(Tree tree); // 后序遍历(递归实现) void preorder_nonrecursive(Tree tree); // 前序遍历(非递归实现) void levelorder(Tree tree); // 层序遍历
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); // 计算学生信息数组的长度
Tree tree[n+1]; // 定义树,开辟 n+1个节点空间,因为根节点从 1 开始编号
for(int i = 1; i <= n; i++){ // 初始化节点,将学生信息存入节点数据中
Node *node = (Node*)malloc(sizeof(Node));
node->data = students[i-1];
node->left_child = NULL;
node->right_child = NULL;
tree[i] = node;
}
for(int i = 1; i <= n/2; i++){ // 构建完全二叉树
if(i*2 <= n){ // 左子节点存在时,将其指向对应的节点
tree[i]->left_child = tree[i*2];
}
if(i*2+1 <= n){ // 右子节点存在时,将其指向对应的节点
tree[i]->right_child = tree[i*2+1];
}
}
printf("Postorder recursive traversal:\n");
postorder_recursive(tree[1]); // 后序遍历二叉树(递归实现)
printf("\n");
printf("Preorder nonrecursive traversal:\n");
preorder_nonrecursive(tree[1]); // 前序遍历二叉树(非递归实现)
printf("\n");
printf("Levelorder traversal:\n");
levelorder(tree[1]); // 层序遍历二叉树
printf("\n");
return 0;
}
void postorder_recursive(Tree tree){
if(tree != NULL){ // 如果当前节点不为空,则继续递归下去
postorder_recursive(tree->left_child); // 遍历左子树
postorder_recursive(tree->right_child); // 遍历右子树
printf("%s %d %d ", tree->data.name, tree->data.number, tree->data.score); // 输出节点数据
}
}
void preorder_nonrecursive(Tree tree){
Tree stack[100]; // 定义栈,存储待遍历的节点
int top = -1; // 栈顶指针初始化为 -1
while(tree != NULL || top != -1){ // 当前节点不为空或者栈不为空时循环执行以下操作
while(tree != NULL){ // 循环将左子节点入栈,并遍历当前节点
printf("%s %d %d ", tree->data.name, tree->data.number, tree->data.score);
stack[++top] = tree;
tree = tree->left_child;
}
if(top != -1){ // 如果栈不为空,则弹出一个元素并访问其右子节点
tree = stack[top--]->right_child;
}
}
}
void levelorder(Tree tree){
Tree queue[100]; // 定义队列,存储待遍历的节点
int front = 0, rear = 0; // 队头和队尾指针初始化为 0
queue[rear++] = tree; // 将根节点入队列
while(front != rear){ // 当队列非空时循环执行以下操作
Tree node = queue[front++]; // 取出队头元素并访问其数据
printf("%s %d %d ", node->data.name, node->data.number, node->data.score);
if(node->left_child != NULL){ // 如果左子节点不为空,则将其入队列
queue[rear++] = node->left_child;
}
if(node->right_child != NULL){ // 如果右子节点不为空,则将其入队列
queue[rear++] = node->right_child;
}
}
}




