作业社区
探索学习新天地，共享知识资源！
慕尼黑0001808 的学生作业：
// 大家自己写代码实现求二叉树的深度。 #include "tree.h" int main() { bitree_t * root = create_node(1); root->lchild = create_node(2); root->rchild = create_node(3); root->lchild->lchild = create_node(4); root->lchild->rchild = create_node(5); int result = max_depth(root); printf("二叉树深度是：%d\n",result); return 0; } // tree.h #ifndef __TREE_H__ #define __TREE_H__ #include #include //二叉树结构体 typedef struct bitree{ int val;//保存编号 struct bitree *lchild;//保存左孩子地址 struct bitree *rchild;//保存右孩子地址 }bitree_t; extern bitree_t * create_node(int val); extern int max_depth(bitree_t * root); #endif // tree.c #include "tree.h" bitree_t * create_node(int val) { bitree_t * node = (bitree_t *)malloc(sizeof(bitree_t)); if(node == NULL) { printf("bitree_t malloc fail\n"); exit(EXIT_FAILURE); } node->val = val; node->lchild = NULL; node->rchild = NULL; return node; } int max_depth(bitree_t * root) { if(NULL == root) { return 0; } int left_depth = max_depth(root->lchild); int right_depth = max_depth(root->rchild); return 1 + (left_depth>right_depth?left_depth:right_depth); } //main.c //在单向链表中实现冒泡排序。 #include "link.h" int main() { int arr[] = {5,2,7,4,8,9}; int len = sizeof(arr)/sizeof(arr[0]); node_t * head = create_empty_linklist(); for(int i = 0;i < len;i++) { insert_tail_linklist(head,arr[i]); } print_linklist(head); sort_linklist(head); print_linklist(head); return 0; } //link.h #ifndef __LINK_H__ #define __LINK_H__ #include #include #include //单向链表节点结构体 typedef struct node{ int data; struct node * next; }node_t; //创建空的单向链表头节点 extern node_t * create_empty_linklist(); //单向链表尾插法 extern void insert_tail_linklist(node_t * head,int data); //单向链表冒泡排序 extern void sort_linklist(node_t * head); //顺序打印单向链表数据 extern void print_linklist(node_t * head); #endif //link.c #include "link.h" node_t * create_empty_linklist() { node_t * head = NULL; head = (node_t*)malloc(sizeof(node_t)); if(NULL == head) { printf("malloc head fail\n"); exit(EXIT_FAILURE); } memset(head,0,sizeof(node_t)); head->next = NULL; return head; } void insert_tail_linklist(node_t * head,int data) { node_t * temp = NULL; temp = (node_t*)malloc(sizeof(node_t)); if(NULL == temp) { printf("malloc temp fail\n"); exit(EXIT_FAILURE); } memset(temp,0,sizeof(node_t)); temp->data = data; temp->next = NULL; node_t * p = head; while(p->next!=NULL)p = p->next; p->next = temp; } void sort_linklist(node_t * head) { if (head == NULL || head->next == NULL) { return; // 空链表或只有一个节点，无需排序 } int swapped; node_t * prev; // 前一个节点 node_t * curr; // 当前节点 node_t * next_node; // 下一个节点 do { swapped = 0; curr = head->next; // 第一个有效节点 prev = head; // 头节点 while (curr->next != NULL) { next_node = curr->next; if (curr->data > next_node->data) { // 交换curr和next_node两个节点 curr->next = next_node->next; next_node->next = curr; prev->next = next_node; // 更新指针位置 curr = next_node; // curr现在指向原来的next_node swapped = 1; } prev = curr; curr = curr->next; } } while (swapped); } void print_linklist(node_t * head) { node_t * temp = head->next; while(temp->next!=NULL) { printf("%d ",temp->data); temp = temp->next; } printf("%d ",temp->data); printf("\n"); } //将两个有序链表合成一个有序链表。 //main.c #include "tree.h" int main() { int arr1[] = {1,3,5,7,9}; int arr2[] = {2,4,6,8,10}; int len1 = sizeof(arr1)/sizeof(arr1[0]); int len2 = sizeof(arr2)/sizeof(arr2[0]); linknode_t * head1 = create_empty_linknode(); linknode_t * head2 = create_empty_linknode(); for(int i = 0;i < len1;i++) { insert_tail_linknode(head1,arr1[i]); } for(int i = 0;i < len2;i++) { insert_tail_linknode(head2,arr2[i]); } print_linklist(head1); print_linklist(head2); linknode_t * head = and_linklist(head1,head2); print_linklist(head); head == head1 ? free(head2) : free(head1); // 释放内存 free_linklist(head); return 0; } //tree.h #ifndef __TREE_H__ #define __TREE_H__ #include #include #include typedef struct node{ int data; struct node * next; }linknode_t; extern linknode_t * create_empty_linknode(); extern void insert_tail_linknode(linknode_t * head,int data); extern linknode_t * and_linklist(linknode_t * head1,linknode_t * head2); extern void print_linklist(linknode_t * head); extern void free_linklist(linknode_t * head); #endif //tree.c #include "tree.h" linknode_t * create_empty_linknode() { linknode_t * head = (linknode_t*)malloc(sizeof(linknode_t)); if(NULL == head) { printf("malloc head fail\n"); exit(EXIT_FAILURE); } memset(head,0,sizeof(linknode_t)); head->next = NULL; return head; } void insert_tail_linknode(linknode_t * head,int data) { linknode_t * temp = (linknode_t*)malloc(sizeof(linknode_t)); if(NULL == temp) { printf("malloc temp fail\n"); exit(EXIT_FAILURE); } temp->data = data; temp->next = NULL; linknode_t * p = head; while(p->next != NULL)p = p->next; p->next = temp; return; } linknode_t * and_linklist(linknode_t * head1, linknode_t * head2) { if (head1->next == NULL) return head2; if (head2->next == NULL) return head1; linknode_t *head, *tail; linknode_t *p1 = head1->next; linknode_t *p2 = head2->next; // 选择第一个节点较小的链表作为结果链表 if (p1->data data) { head = head1; tail = p1; p1 = p1->next; } else { head = head2; tail = p2; p2 = p2->next; } head->next = tail; // 合并剩余节点 while (p1 != NULL && p2 != NULL) { if (p1->data data) { tail->next = p1; tail = p1; p1 = p1->next; } else { tail->next = p2; tail = p2; p2 = p2->next; } } // 连接剩余链表 if (p1 != NULL) { tail->next = p1; } else { tail->next = p2; } return head; } void print_linklist(linknode_t * head) { linknode_t * p = head->next; while(NULL != p) { printf("%d ",p->data); p = p->next; } printf("\n"); } void free_linklist(linknode_t * head) { linknode_t * current = head; while (current != NULL) { linknode_t * temp = current; current = current->next; free(temp); } } //已经知道一棵二叉树。 //先序遍历：ABDGHCEIF //中序遍历：GDHBAEICF //要求大家画出这颗二叉树。 /* A / \ B C / / \ D E F / \ \ G H I */
+8
