浙大数据结构课程总结

今天把浙大数据结构Mooc的期末考试完成了,结果还算不错。通过这个课程的学习,我从一个对数据结构一窍不通的人变成了一个对数据结构略知一二的人。如果让我再从头学一遍的话,我会先把C语言学好,并且买老师的参考书。后续时间里应该会把课程再复习一遍,用C语言把代码再实现一遍,然后去参加PAT的甲级考试。

这里把编程题贴一下,是一道中序后后续遍历推测前序遍历的问题,之前有做过类似的,还是比较简单的。

  • 习题

7-1 根据后序和中序遍历输出先序遍历(8 分)
本题要求根据给定的一棵二叉树的后序遍历和中序遍历结果,输出该树的先序遍历结果。
输入格式:
第一行给出正整数N(≤30),是树中结点的个数。随后两行,每行给出N个整数,分别对应后序遍历和中序遍历结果,数字间以空格分隔。题目保证输入正确对应一棵二叉树。
输出格式:
在一行中输出Preorder:以及该树的先序遍历结果。数字间有1个空格,行末不得有多余空格。
输入样例:
7
2 3 1 5 7 6 4
1 2 3 4 5 6 7
输出样例:
Preorder: 4 1 3 2 6 5 7

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
# -*- coding: utf-8 -*-
"""
Created on Mon Jun 4 16:04:35 2018

@author: Administrator
"""

n=int(input())

post=list(map(int,input().strip().split()))

mid=list(map(int,input().strip().split()))
'''
n=7
post=[2, 3, 1, 5, 7, 6, 4]
mid=[1, 2, 3, 4, 5, 6, 7]
'''
def f(post,mid,l):
#print(post,mid,l)
if(len(post)<=1):
return post
elif (len(post)>=2):
last=post[-1]
#print(last)
l.append(last)
#找到索引
index=mid.index(last)
mid1=mid[:index]
mid2=mid[index+1:]
length=len(mid1)
post1=post[:length]
post2=post[length:-1]
a=f(post1,mid1,[])
b=f(post2,mid2,[])
l=l+a+b
return l

result=list(map(str,f(post,mid,[])))
print("Preorder: "+" ".join(result))

本文标题:浙大数据结构课程总结

文章作者:Doraemonzzz

发布时间:2018年06月04日 - 16:54:50

最后更新:2019年02月12日 - 21:15:56

原始链接:http://doraemonzzz.com/2018/06/04/浙大数据结构课程总结/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。