【MOOC-浙大数据结构】第三周的编程作业——建树,树的遍历

2024-03-29 12:58

本文主要是介绍【MOOC-浙大数据结构】第三周的编程作业——建树,树的遍历,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

第三周的编程作业:

1.树的同构

小白专场里讲解了找根节点的方法——没有一个指向他的结点,check一下~

#include<stdio.h>
struct TreeNode
{char c;int left,right;
}t1[15],t2[15];
int BuildTree(struct TreeNode t[])
{int check[15]={0};int n,i,root=-1;char cl,cr;scanf("%d",&n);for(i=0;i<n;i++){getchar();scanf("%c %c %c",&t[i].c,&cl,&cr);if(cl!='-'){t[i].left=cl-'0';check[t[i].left]=1;}else t[i].left=-1;if(cr!='-'){t[i].right=cr-'0';check[t[i].right]=1;}else t[i].right=-1;}for(i=0;i<n;i++){if(check[i]==0){root=i;break;}}return root;
}
int Isomorphic(int r1,int r2)
{if(r1==-1&&r2==-1)return 1;//均为空树 if(r1==-1||r2==-1)return 0;//一空一不空 if(t1[r1].c!=t2[r2].c)return 0;//数据不同 if((t1[r1].left!=-1)&&(t2[r2].left!=-1)&&(t1[t1[r1].left].c==t2[t2[r2].left].c))return (Isomorphic(t1[r1].left,t2[r2].left)&&Isomorphic(t1[r1].right,t2[r2].right));else //左右交换 return (Isomorphic(t1[r1].left,t2[r2].right)&&Isomorphic(t1[r1].right,t2[r2].left));
}
int main()
{int r1,r2;r1=BuildTree(t1);r2=BuildTree(t2);if(Isomorphic(r1,r2))printf("Yes\n");elseprintf("No\n");
} 

2.List Leaves

树的构建和存储同上一题,然后用广搜模拟层次遍历,从上到下从左到右输出叶子结点。

PS:如果只要求从左到右的话,用深搜。

#include<stdio.h>
#include<queue>
#include<algorithm>
#include<iostream>
using namespace std;
struct TreeNode
{int c;int left,right;
}tree[15];
int BuildTree(struct TreeNode t[])
{int check[15]={0};int n,i,root=-1;char cl,cr;scanf("%d",&n);for(i=0;i<n;i++){getchar();t[i].c=i; scanf("%c %c",&cl,&cr);if(cl!='-'){t[i].left=cl-'0';check[t[i].left]=1;}else t[i].left=-1;if(cr!='-'){t[i].right=cr-'0';check[t[i].right]=1;}else t[i].right=-1;}for(i=0;i<n;i++){if(check[i]==0){root=i;break;}}return root;
}
int main()
{int root;int k;//flag-空格root=BuildTree(tree);k=0; queue<TreeNode> q;q.push(tree[root]);while(!q.empty()){TreeNode cur=q.front();q.pop();if(cur.left!=-1)q.push(tree[cur.left]);if(cur.right!=-1)q.push(tree[cur.right]);if(cur.left==-1&&cur.right==-1){if(k)printf(" ");printf("%d",cur.c);k++;}		}printf("\n");
} 

3.Tree Traversals Again

方法一:观察可知这道题实际上是已知前序中序遍历,求后序遍历。(push的数为前序序列,pop的数为中序序列)

#include<stdio.h>
#include<string>
#include<stack>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
vector<int> pre,in,post;
stack<int> st;
void post_travel(int root,int start,int end)
{if(start>end) return;int i=start;while(i<=end&&pre[root]!=in[i]) i++;post_travel(root+1,start,i-1);post_travel(root+1+i-start,i+1,end);post.push_back(pre[root]);
}
int main()
{int n,i,x;string s;scanf("%d",&n);for(i=0;i<n*2;i++){cin>>s;if(s=="Push"){scanf("%d",&x);pre.push_back(x);st.push(x);}else if(!st.empty()){in.push_back(st.top());st.pop();}}post_travel(0,0,n-1);for(i=0;i<n;i++){if(i) printf(" ");printf("%d",post[i]);}printf("\n");
}

方法二:参考来自:https://www.cnblogs.com/clevercong/p/4177802.html

题目分析:借助“栈”进行树的后续遍历。栈工作记录中必须注明刚才是在左子树还是在右子树中。

  每次push,times = 1;

  每次pop检查栈顶记录的times:如果是1,弹出来变成2压回栈;

               如果是2,则弹出,放入存放结果的vector中,重复这一过程,直到栈顶times为1。

  所有push与pop操作执行完毕时,输出vector内的数据和stack中的数据即可。

#include<stdio.h>
#include<string>
#include<stack>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
struct node
{int data;int times;
}Node;
int main()
{int n,x,i;string cmd; stack<node> st; vector<int> vec; scanf("%d",&n);for(i=0;i<2*n;i++){cin>>cmd;if(cmd=="Push"){scanf("%d",&x);Node.data=x;Node.times=1;st.push(Node);}if(cmd=="Pop"){Node=st.top();st.pop();if(Node.times==1)  {Node.times=2;st.push(Node);}else if(Node.times==2)  {vec.push_back(Node.data);while(st.top().times==2)  {vec.push_back(st.top().data);st.pop();}if(st.size()!=0) st.top().times=2;                    }}}for(i=0;i<vec.size();i++)printf("%d ",vec[i]);while(st.size()!=0)  {printf("%d",st.top().data);st.pop();if(st.size()!=0)printf(" ");}printf("\n");
}

 

这篇关于【MOOC-浙大数据结构】第三周的编程作业——建树,树的遍历的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/858653

相关文章

作业提交过程之HDFSMapReduce

作业提交全过程详解 (1)作业提交 第1步:Client调用job.waitForCompletion方法,向整个集群提交MapReduce作业。 第2步:Client向RM申请一个作业id。 第3步:RM给Client返回该job资源的提交路径和作业id。 第4步:Client提交jar包、切片信息和配置文件到指定的资源提交路径。 第5步:Client提交完资源后,向RM申请运行MrAp

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

Linux 网络编程 --- 应用层

一、自定义协议和序列化反序列化 代码: 序列化反序列化实现网络版本计算器 二、HTTP协议 1、谈两个简单的预备知识 https://www.baidu.com/ --- 域名 --- 域名解析 --- IP地址 http的端口号为80端口,https的端口号为443 url为统一资源定位符。CSDNhttps://mp.csdn.net/mp_blog/creation/editor

【Python编程】Linux创建虚拟环境并配置与notebook相连接

1.创建 使用 venv 创建虚拟环境。例如,在当前目录下创建一个名为 myenv 的虚拟环境: python3 -m venv myenv 2.激活 激活虚拟环境使其成为当前终端会话的活动环境。运行: source myenv/bin/activate 3.与notebook连接 在虚拟环境中,使用 pip 安装 Jupyter 和 ipykernel: pip instal

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)

【编程底层思考】垃圾收集机制,GC算法,垃圾收集器类型概述

Java的垃圾收集(Garbage Collection,GC)机制是Java语言的一大特色,它负责自动管理内存的回收,释放不再使用的对象所占用的内存。以下是对Java垃圾收集机制的详细介绍: 一、垃圾收集机制概述: 对象存活判断:垃圾收集器定期检查堆内存中的对象,判断哪些对象是“垃圾”,即不再被任何引用链直接或间接引用的对象。内存回收:将判断为垃圾的对象占用的内存进行回收,以便重新使用。

Go Playground 在线编程环境

For all examples in this and the next chapter, we will use Go Playground. Go Playground represents a web service that can run programs written in Go. It can be opened in a web browser using the follow

深入理解RxJava:响应式编程的现代方式

在当今的软件开发世界中,异步编程和事件驱动的架构变得越来越重要。RxJava,作为响应式编程(Reactive Programming)的一个流行库,为Java和Android开发者提供了一种强大的方式来处理异步任务和事件流。本文将深入探讨RxJava的核心概念、优势以及如何在实际项目中应用它。 文章目录 💯 什么是RxJava?💯 响应式编程的优势💯 RxJava的核心概念

《数据结构(C语言版)第二版》第八章-排序(8.3-交换排序、8.4-选择排序)

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多,算法平均时间性能比直接插入排序差。当初始记录无序,n较大时, 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In

函数式编程思想

我们经常会用到各种各样的编程思想,例如面向过程、面向对象。不过笔者在该博客简单介绍一下函数式编程思想. 如果对函数式编程思想进行概括,就是f(x) = na(x) , y=uf(x)…至于其他的编程思想,可能是y=a(x)+b(x)+c(x)…,也有可能是y=f(x)=f(x)/a + f(x)/b+f(x)/c… 面向过程的指令式编程 面向过程,简单理解就是y=a(x)+b(x)+c(x)