为了账号安全,请及时绑定邮箱和手机立即绑定

作业社区

探索学习新天地,共享知识资源!

0 提交作业
0 布置作业
0 满分作业
得分 98
学习任务

RX0_UNICORN 的学生作业:

// linkstack.h #ifndef __LINKSTACK_H__ #define __LINKSTACK_H__ #include #include #include #include "bitree.h" typedef bitree_t *datatype_t; // 节点类型 typedef struct node { datatype_t data; struct node *next; }linknode_t; // 栈头类型 typedef struct { linknode_t *top; // 栈顶指针 int n; // 记录当前栈中元素的个数 }linkstack_t; extern linkstack_t *create_empty_linkstack(); extern int is_empty_linkstack(linkstack_t *ls); extern void push_linkstack(linkstack_t *ls, datatype_t data); extern datatype_t pop_linkstack(linkstack_t *ls); extern datatype_t get_top_data(linkstack_t *ls); #endif // linkstack.c #include "linkstack.h" linkstack_t *create_empty_linkstack() { linkstack_t *ls = NULL; ls = (linkstack_t *)malloc(sizeof(linkstack_t)); if(NULL == ls) { printf("malloc linkstack_t *ls is fail!\n"); return NULL; } memset(ls, 0, sizeof(linkstack_t)); return ls; } // 判空 int is_empty_linkstack(linkstack_t *ls) { return ls->top == NULL ? 1 : 0; } // 入栈 void push_linkstack(linkstack_t *ls, datatype_t data) { linknode_t *temp = NULL; temp = (linknode_t *)malloc(sizeof(linknode_t)); if(NULL == temp) { printf("malloc linknode_t *temp is fail!\n"); return; } temp->data = data; // 将节点数据插入栈中 temp->next = ls->top; ls->top = temp; // 更新n 的值 ls->n++; return; } datatype_t pop_linkstack(linkstack_t *ls) { linknode_t *temp = NULL; datatype_t data; // 保存要删除的节点地址 temp = ls->top; // 取出数据 data = temp->data; // 更新头部指针 ls->top = temp->next; // 释放 temp free(temp); temp = NULL; // 更新 n 的值 ls->n--; return data; } // 输出栈顶元素 datatype_t get_top_data(linkstack_t *ls) { return ls->top->data; } // bitree.h #ifndef __BITREE_H__ #define __BITREE_H__ #include #include #include #define N 6 typedef char data_t; typedef struct bitree { int n; data_t data; struct bitree *lchild; struct bitree *rchild; }bitree_t; extern bitree_t *create_empty_bitree(int n); extern void pre_order(bitree_t *bt); extern void in_order(bitree_t *bt); extern void post_order(bitree_t *bt); #endif // bitree.c #include "bitree.h" #include "linkstack.h" bitree_t *create_empty_bitree(int n) { bitree_t *bt = NULL; bt = (bitree_t *)malloc(sizeof(bitree_t)); if(NULL == bt) { printf("malloc bitree_t *bt is fail!\n"); return NULL; } memset(bt, 0, sizeof(bitree_t)); bt->n = n; bt->lchild = bt->rchild = NULL; printf("input %d node data : ", n); scanf("%c", &(bt->data)); // 清除缓存区数据 while(getchar() != '\n'); // 左子节点存在条件 if(2 * n lchild = create_empty_bitree(2 * n); } // 右子节点存在条件 if(2 * n + 1 rchild = create_empty_bitree(2 * n + 1); } return bt; } // 前序非递归遍历 void pre_order(bitree_t *bt) { if(bt == NULL) return; linkstack_t *ls = create_empty_linkstack(); bitree_t *temp = bt; while(temp != NULL || !is_empty_linkstack(ls)) { while(temp != NULL) { printf("(%c : %d)", temp->data, temp->n); push_linkstack(ls, temp); temp = temp->lchild; } if(!is_empty_linkstack(ls)) { temp = pop_linkstack(ls); temp = temp->rchild; } } free(ls); return; } //中序遍历 void in_order(bitree_t *root) { if(NULL == root) return ; linkstack_t *ls = create_empty_linkstack(); bitree_t *temp = root; while(temp != NULL || !is_empty_linkstack(ls)) { if(temp != NULL) { push_linkstack(ls, temp); temp = temp->lchild; } else { temp = pop_linkstack(ls); printf("(%c : %d)",temp->data,temp->n); temp = temp->rchild; } } free(ls); } //后序遍历 void post_order(bitree_t *root) { if(NULL == root) return ; linkstack_t *ls = create_empty_linkstack(); bitree_t *pre = NULL; bitree_t *cur = NULL; push_linkstack(ls, root); while(!is_empty_linkstack(ls)) { cur = get_top_data(ls); // 以下情况,可以直接输出值 // 左右孩子都为空 // 左右孩子存在,并且左孩子或右孩子都被访问过 if((cur->lchild == NULL && cur->rchild == NULL) || (pre != NULL && (pre == cur->lchild || pre == cur->rchild))) { printf("(%c : %d) ",cur->data,cur->n); pop_linkstack(ls); pre = cur; } else { if(cur->rchild != NULL) { push_linkstack(ls, cur->rchild); } if(cur->lchild != NULL) { push_linkstack(ls, cur->lchild); } } } free(ls); return; } // main.c #include "bitree.h" int main(int argc, const char *argv[]) { bitree_t *bt = create_empty_bitree(1); printf("pre_order : "); pre_order(bt); printf("\n"); printf("in_order : "); in_order(bt); printf("\n"); printf("post_order : "); post_order(bt); printf("\n"); return 0; } 【图片】

微信客服

购课补贴
联系客服咨询优惠详情

帮助反馈 APP下载

慕课网APP
您的移动学习伙伴

公众号

扫描二维码
关注慕课网微信公众号