ZBLOG

#include #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 po...

#include #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;
    }
}

}

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

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

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

联系我们

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

微信号:3007537140

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

关注我们
x

注册

已经有帐号?