【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

相关文章

揭秘Python Socket网络编程的7种硬核用法

《揭秘PythonSocket网络编程的7种硬核用法》Socket不仅能做聊天室,还能干一大堆硬核操作,这篇文章就带大家看看Python网络编程的7种超实用玩法,感兴趣的小伙伴可以跟随小编一起... 目录1.端口扫描器:探测开放端口2.简易 HTTP 服务器:10 秒搭个网页3.局域网游戏:多人联机对战4.

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘

Java并发编程必备之Synchronized关键字深入解析

《Java并发编程必备之Synchronized关键字深入解析》本文我们深入探索了Java中的Synchronized关键字,包括其互斥性和可重入性的特性,文章详细介绍了Synchronized的三种... 目录一、前言二、Synchronized关键字2.1 Synchronized的特性1. 互斥2.

Python异步编程中asyncio.gather的并发控制详解

《Python异步编程中asyncio.gather的并发控制详解》在Python异步编程生态中,asyncio.gather是并发任务调度的核心工具,本文将通过实际场景和代码示例,展示如何结合信号量... 目录一、asyncio.gather的原始行为解析二、信号量控制法:给并发装上"节流阀"三、进阶控制

Go语言中三种容器类型的数据结构详解

《Go语言中三种容器类型的数据结构详解》在Go语言中,有三种主要的容器类型用于存储和操作集合数据:本文主要介绍三者的使用与区别,感兴趣的小伙伴可以跟随小编一起学习一下... 目录基本概念1. 数组(Array)2. 切片(Slice)3. 映射(Map)对比总结注意事项基本概念在 Go 语言中,有三种主要

C#多线程编程中导致死锁的常见陷阱和避免方法

《C#多线程编程中导致死锁的常见陷阱和避免方法》在C#多线程编程中,死锁(Deadlock)是一种常见的、令人头疼的错误,死锁通常发生在多个线程试图获取多个资源的锁时,导致相互等待对方释放资源,最终形... 目录引言1. 什么是死锁?死锁的典型条件:2. 导致死锁的常见原因2.1 锁的顺序问题错误示例:不同

C++中使用vector存储并遍历数据的基本步骤

《C++中使用vector存储并遍历数据的基本步骤》C++标准模板库(STL)提供了多种容器类型,包括顺序容器、关联容器、无序关联容器和容器适配器,每种容器都有其特定的用途和特性,:本文主要介绍C... 目录(1)容器及简要描述‌php顺序容器‌‌关联容器‌‌无序关联容器‌(基于哈希表):‌容器适配器‌:(

PyCharm接入DeepSeek实现AI编程的操作流程

《PyCharm接入DeepSeek实现AI编程的操作流程》DeepSeek是一家专注于人工智能技术研发的公司,致力于开发高性能、低成本的AI模型,接下来,我们把DeepSeek接入到PyCharm中... 目录引言效果演示创建API key在PyCharm中下载Continue插件配置Continue引言

C#反射编程之GetConstructor()方法解读

《C#反射编程之GetConstructor()方法解读》C#中Type类的GetConstructor()方法用于获取指定类型的构造函数,该方法有多个重载版本,可以根据不同的参数获取不同特性的构造函... 目录C# GetConstructor()方法有4个重载以GetConstructor(Type[]

作业提交过程之HDFSMapReduce

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