ZBLOG

#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; // 创...

#include #include #include

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

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

} Student;

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

  1. Student data; // 结点数据,即学生信息
  2. struct node *left; // 左子结点指针
  3. struct node *right; // 右子结点指针

} Node;

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

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

}

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

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

}

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

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

}

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

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

}

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

  1. if (root == NULL) { // 如果当前结点为空,则直接返回
  2. return;
  3. }
  4. Node *queue[100]; // 创建一个指针数组作为队列,用于辅助实现广度优先遍历。
  5. int front = 0, rear = 0; // 定义队列的头和尾指针,用于存储新创建的结点
  6. queue[rear++] = root; // 将根节点入队列
  7. while (front < rear) { // 当队列不为空时循环执行以下操作:
  8. Node *node = queue[front++]; // 取出队首元素(即当前要访问的结点)
  9. printf("%s %d %d\n", node->data.name, node->data.number, node->data.score); // 输出当前结点的学生信息。
  10. if (node->left != NULL) { // 如果当前结点有左子树,则将其压入队列中
  11. queue[rear++] = node->left;
  12. }
  13. if (node->right != NULL) { // 如果当前结点有右子树,则将其压入队列中
  14. queue[rear++] = node->right;
  15. }
  16. }

}

int main() {

  1. Student students[] = { // 定义一个学生信息数组,用于构建二叉树
  2. {"Lei Zhenzi", 101401, 82},
  3. {"Jiang Ziya", 100032, 90},
  4. {"Ne Zha", 101674, 70},
  5. {"Shen Gongbao", 101982, 87},
  6. {"Jiu Weihu", 107431, 75},
  7. {"Tian Zun", 100001, 98},
  8. {"Tai Yi", 101009, 81},
  9. {"Yang Jian", 101321, 63},
  10. {"Huang Feihu", 101567, 72},
  11. {"Zhou Wang", 108160, 55},
  12. {"Li Jing", 102456, 84},
  13. {"Tu Xingsun", 102245,65}
  14. };
  15. int n = sizeof(students) / sizeof(students[0]); // 计算出学生信息数组的长度n
  16. Node *root = build_complete_binary_tree(students,n); // 构建完全二叉树,并返回根节点指针存储在变量root中。
  17. printf("后序遍历:\n");
  18. postorder_traversal_recursive(root); // 后序遍历二叉树,并输出每个结点的学生信息
  19. printf("先序遍历:\n");
  20. preorder_traversal_nonrecursive(root); // 先序遍历二叉树(非递归),并输出每个结点的学生信息
  21. printf("广度优先遍历:\n");
  22. breadth_first_traversal(root); // 广度优先遍历二叉树,并输出每个结点的学生信息
  23. return 0; // 返回程序执行结果正常退出。

}

本站部分文章来源于网络,版权归原作者所有,如有侵权请联系站长删除。
转载请注明出处:https://golang.0voice.com/?id=4310

分享:
扫描分享到社交APP
上一篇
下一篇
发表列表
游客 游客
此处应有掌声~
评论列表

还没有评论,快来说点什么吧~

联系我们

在线咨询: 点击这里给我发消息

微信号:3007537140

上班时间: 10:30-22:30

关注我们
x

注册

已经有帐号?