浙大数据结构Week3
课程地址：https://www.icourse163.org/course/ZJU-93001
笔记中图片均来自此mooc中讲义。
第三周的内容是讲树，现在来回顾下。
Part1:回顾
1.树的定义
光看定义还挺抽象，但是看下示意图还是比较好理解的，注意这里互不相交这个特点很关键，可以据此来判断一个结构是否为树，例如一下三个例子均不是树。
再来看一些常用术语，这里只列几个最常用的。
- 节点的度：节点的子树个数
- 树的度：树的所有节点中最大的度数
- 叶节点：度为0的节点
- 根节点：没有父节点的节点
- 父节点：有子树的节点是其子树的根节点的父节点
- 子节点：若A是B的父节点，那么B是A的子节点
- 兄弟节点：具有同一父节点的各个节点彼此是兄弟节点
现在有了抽象数据结构，那么在计算机中如何表示呢？
课程中老师给了一种通用方法，适用于任何树，称为儿子兄弟表示法，即每个节点由三个元素构成，分别为节点的值，指向兄弟节点的指针，指向子节点的指针。
树的集合称为森林，可以看出森林也可以使用儿子兄弟表示法表出，只要将每个根节点指向下一颗数即可。
2.二叉树
现在来看一种特殊的树，二叉树。
二叉树的特点为每个节点有0到2个子节点，来看几个特殊的二叉树。
这里介绍几个二叉树特有的性质：
- 第i层的最大节点数为：$2^{i-1}$。
- 这个很好理解解，每一层最多是上一层的2倍
- 深度为k的二叉树有最大节点总数为:$2^{k}-1$。
- 这是因为第i层最多有$2^{i-1}$个，一共有k层，所以最多有$2^{0}+2^{1}+…+2^{k-1}=2^{k}-1$个节点
对任何非空二叉树，$n_{i}$表示度为$i$的节点数量($i=0,1,2$)。那么满足$n_{0}=n_{2}+1$
- 利用两种方式来计算边的数量。由树的定义可知，除了根节点外，每个节点有且只有一个父节点，所以边的数量为$n_{0}+n_{1}+n_{2}-1$。再来换一种思路，度为$i$的节点数量为$n_{i}$，所以边的数量为$0\times n_{0}+1\times n_{1}+2\times n_{2}$
- 综上，$n_{0}+n_{1}+n_{2}-1=0\times n_{0}+1\times n_{1}+2\times n_{2}$，即$n_{0}=n_{2}+1$
最后一个结论还可以推广为k叉树，$n_{i}$表示度为$i$的节点数量($i=0,1,2…k$)。那么$n_{0}=\sum_{i=1}^{k}(i-1)n_{i}+1$。思路和之前的证明一样。
再来看一下二叉树的抽象数据类型定义及存储结构：
二叉树的存储结构有两种，一种是顺序存储，另一种是链表存储。
先来看一下顺序存储。顺序存储的含义是将二叉树存储在数组中，从上到下，从左到右存储，这里来看一下完全二叉树利用顺序存储的特点。
这给我们一种启发，一个非完全二叉树可以将其补成完全二叉树，在补的地方令值为空即可。这样虽然操作起来方便，但是会对空间有很大浪费。
再来看一下链表存储，链表存储的思想和兄弟儿子存储很相似，每个节点也由三个元素构成，分别为节点的值，指向左儿子的指针，指向右儿子的指针。
3.二叉树的遍历
一般分为4种，先序，中序，后续，层序。这部分理解起来比较简单，主要是代码的实现，后续的习题中会有相关练习，这里从略。
Part2:作业
这部分我使用字典来存储树,思路依旧是记录值，左指针，右指针。
- 作业1
03-树1 树的同构（25 分）
给定两棵树T1和T2。如果T1可以通过若干次左右孩子互换就变成T2，则我们称两棵树是“同构”的。例如图1给出的两棵树就是同构的，因为我们把其中一棵树的结点A、B、G的左右孩子互换后，就得到另外一棵树。而图2就不是同构的。
图1
图2
现给定两棵树，请你判断它们是否是同构的。
输入格式:
输入给出2棵二叉树树的信息。对于每棵树，首先在一行中给出一个非负整数N (≤10)，即该树的结点数（此时假设结点从0到N−1编号）；随后N行，第i行对应编号第i个结点，给出该结点中存储的1个英文大写字母、其左孩子结点的编号、右孩子结点的编号。如果孩子结点为空，则在相应位置上给出“-”。给出的数据间用一个空格分隔。注意：题目保证每个结点中存储的字母是不同的。
输出格式:
如果两棵树是同构的，输出“Yes”，否则输出“No”。
输入样例1（对应图1）：
8
A 1 2
B 3 4
C 5 -
D - -
E 6 -
G 7 -
F - -
H - -
8
G - 4
B 7 6
F - -
A 5 1
H - -
C 0 -
D - -
E 2 -
输出样例1:
Yes
输入样例2（对应图2）：
8
B 5 7
F - -
A 0 3
C 6 -
H - -
D - -
G 4 -
E 1 -
8
D 6 -
B 5 -
E - -
H - -
C 0 2
G - 3
F - -
A 1 4
输出样例2:
No
这题的关键就是把各种情形全部列出。
# -*- coding: utf-8 -*-
"""
Created on Mon Mar 26 12:05:53 2018
@author: 715073608
"""
#定义读取函数
def read():
#记录输入的个数
num=int(raw_input())
#非空树
if num>0:
#利用字典存储二叉树
tree={}
#此数字用来做标记，用来找出根节点
check=[0]*num
for i in range(num):
temp1=raw_input().split(' ')
temp2={}
temp2['v']=temp1[0]
temp2['l']=temp1[1]
temp2['r']=temp1[2]
tree[str(i)]=temp2
if temp1[1]!='-':
check[int(temp1[1])]=1
if temp1[2]!='-':
check[int(temp1[2])]=1
#找到根节点
num=check.index(0)
return tree,str(num)
#空树
else:
return {'0': {'l': '-', 'r': '-', 'v': 'A'}},'0'
#读入数据
tree1,num1=read()
tree2,num2=read()
#判别函数
def f(treea,starta,treeb,startb):
#两个都为空
if (flag(treea,starta)==0 and flag(treeb,startb)==0):
return 1
#一个为空
elif ((flag(treea,starta)==0 and flag(treeb,startb)>0) or (flag(treeb,startb)==0 and flag(treea,starta)>0)):
return 0
#对应值不相同
elif treea[starta]['v']!=treeb[startb]['v']:
return 0
#无左子节点
elif treea[starta]['l']=='-'and treeb[startb]['l']=='-':
return f(treea,treea[starta]['r'],treeb,treeb[startb]['r'])
#左子节点为相同
elif treea[starta]['l']!='-'and treeb[startb]['l']!='-' and treea[treea[starta]['l']]['v']==treeb[treeb[startb]['l']]['v']:
return f(treea,treea[starta]['l'],treeb,treeb[startb]['l'])*f(treea,treea[starta]['r'],treeb,treeb[startb]['r'])
#交换左右节点
else:
return f(treea,treea[starta]['l'],treeb,treeb[startb]['r'])*f(treea,treea[starta]['r'],treeb,treeb[startb]['l'])
def flag(tree,start):
if start=='-':
return 0
else:
return 1
if f(tree1,num1,tree2,num2):
print 'Yes'
else:
print 'No'- 作业2
03-树2 List Leaves（25 分）
Given a tree, you are supposed to list all the leaves in the order of top down, and left to right.
Input Specification:
Each input file contains one test case. For each case, the first line gives a positive integer N (≤10) which is the total number of nodes in the tree — and hence the nodes are numbered from 0 to N−1. Then N lines follow, each corresponds to a node, and gives the indices of the left and right children of the node. If the child does not exist, a “-“ will be put at the position. Any pair of children are separated by a space.
Output Specification:
For each test case, print in one line all the leaves’ indices in the order of top down, and left to right. There must be exactly one space between any adjacent numbers, and no extra space at the end of the line.
这题的思路是根据输入，将数据入读成树的结构，再层序遍历，这题写的不是很好。
# -*- coding: utf-8 -*-
"""
Created on Mon Mar 26 20:33:45 2018
@author: Administrator
"""
#定义读取函数
def read():
#记录输入的个数
num=int(raw_input())
#非空树
if num>0:
#利用字典存储二叉树
tree={}
#此数字用来做标记，用来找出根节点
check=[0]*num
for i in range(num):
temp1=raw_input().split(' ')
temp2={}
temp2['l']=temp1[0]
temp2['r']=temp1[1]
tree[str(i)]=temp2
if temp1[0]!='-':
check[int(temp1[0])]=1
if temp1[1]!='-':
check[int(temp1[1])]=1
#找到根节点
num=check.index(0)
return tree,str(num)
#空树
else:
return {'0': {'l': '-', 'r': '-', 'v': 'A'}},'0'
#判断树是否为空
def flag(tree,start):
if start=='-':
return 0
else:
return 1
#判断是否为叶节点
def isleaf(x):
if x['l']=='-' and x['r']=='-':
return 1
else:
return 0
#n记录层数,m记录叶节点及其层数
def show(tree,start,n,m):
if flag(tree,start):
n+=1
if isleaf(tree[start]):
m.append([start,n])
else:
show(tree,tree[start]['l'],n,m)
show(tree,tree[start]['r'],n,m)
return m
b=show(tree1,num1,0,[])
c=set()
d=[]
#找出不同的层数
for i in b:
c.add(i[-1])
#按照层数排序
for j in c:
d.append(j)
d.sort()
#按照层数递增的顺序输出
ans=''
for i in d:
for j in b:
if j[-1]==i:
ans+=(j[0]+' ')
print ans.strip(' ')
- 作业3
03-树3 Tree Traversals Again（25 分）
An inorder binary tree traversal can be implemented in a non-recursive way with a stack. For example, suppose that when a 6-node binary tree (with the keys numbered from 1 to 6) is traversed, the stack operations are: push(1); push(2); push(3); pop(); pop(); push(4); pop(); pop(); push(5); push(6); pop(); pop(). Then a unique binary tree (shown in Figure 1) can be generated from this sequence of operations. Your task is to give the postorder traversal sequence of this tree.
Figure 1
Input Specification:
Each input file contains one test case. For each case, the first line contains a positive integer N (≤30) which is the total number of nodes in a tree (and hence the nodes are numbered from 1 to N). Then 2N lines follow, each describes a stack operation in the format: “Push X” where X is the index of the node being pushed onto the stack; or “Pop” meaning to pop one node from the stack.
Output Specification:
For each test case, print the postorder traversal sequence of the corresponding tree in one line. A solution is guaranteed to exist. All the numbers must be separated by exactly one space, and there must be no extra space at the end of the line.
Sample Input:
6
Push 1
Push 2
Push 3
Pop
Pop
Push 4
Pop
Pop
Push 5
Push 6
Pop
Pop
Sample Output:
3 4 2 6 5 1
可以看出，Push元素的顺序为先序遍历的顺序，Pop元素的顺序为中序遍历的顺序，所以这题即为已知先序和中序，求后序遍历的顺序。我的思路是先恢复二叉树，再后续遍历，核心思路见下图。
# -*- coding: utf-8 -*-
"""
Created on Mon Mar 26 21:43:05 2018
@author: Administrator
"""
#读取数据
a=int(raw_input(''))
b=[]
c=[]
stack=[]
for i in range(2*a):
temp=raw_input('').split(' ')
if temp[0]=='Push':
b.append(temp[1])
stack.append(temp[1])
else:
t=stack.pop()
c.append(t)
#恢复二叉树
def f(b,c,dic,n):
if len(dic)<n and len(b)>0 and len(c)>0:
#print b,c
temp=b[0]
tempindex=c.index(temp)
B=len(b)
#print b,c
#print B,dic,tempindex
#print temp,tempindex,dic
if B>=2 and B>=tempindex+2:
if tempindex>0 and tempindex<B-1:
dic[temp]={'l':b[1],'r':b[tempindex+1]}
elif tempindex>0:
dic[temp]={'l':b[1],'r':'-'}
else:
dic[temp]={'l':'-','r':b[tempindex+1]}
elif B>=2:
dic[temp]={'l':b[1],'r':'-'}
elif B>=tempindex+2:
dic[temp]={'l':'-','r':b[tempindex+1]}
else:
dic[temp]={'l':'-','r':'-'}
f(b[1:tempindex+1],c[:tempindex],dic,n)
f(b[tempindex+1:],c[tempindex+1:],dic,n)
return dic
ans=f(b,c,{},a)
#判断树是否为空
def flag(tree,start):
if start=='-':
return 0
else:
return 1
def show(tree,start):
if flag(tree,start):
show(tree,tree[start]['l'])
show(tree,tree[start]['r'])
print start,
show(ans,b[0])