蓝桥杯备赛（Day5）——二叉树
二叉树存储
普通做法，二叉树一个节点包括结点的数值以及指向左右子节点的指针
在class Node中
def __init__(self,s,l=None,r=None):self.val=Noneself.l=lself.r=r在竞赛中，我们往往使用静态数组实现二叉树，定义一个大小为N的静态结构体数组，使用其来存储一棵二叉树。
#定义静态数组
tree=['']*10000
#根节点
tree[1]
#结点tree[p]的左子节点
tree[2*p]
#结点tree[p]的右子节点
tree[2*p+1]使用静态数组时，对应的tree假如不是满二叉树，则应该使用-1或者0填补空缺，这样tree对应的静态数组即可使用于任何一个二叉树。
三种遍历方式
先序遍历
EBADCGFIH
def preorder(p):print(tree[p],end='')if tree[2*p]!='':postorder(2*p)if tree[2*p+1]!='':postorder(2*p+1)按照父、左儿子、右儿子的顺序进行访问
中序遍历
ABCDEFGHI
def inorder(p):if tree[2*p]!='': inorder(2*p)print(tree[p],end='')if tree[2*p+1]!='': inorder(2*p+1)按照左儿子 、父、右儿子的顺序进行访问
后序遍历
ACDBFHIGE
def postorder(p):if tree[2*p] != '': postorder(2*p)if tree[2*p+1] !='': postorder(2*p+1)print(tree[p],end='')按照左儿子、右儿子、父的顺序访问。
根据中序遍历和后序遍历可以确定一棵树。
由先序遍历和后序遍历不能确定一棵树。
FBI树
题目描述
我们可以把由 “0” 和 “1” 组成的字符串分为三类：全 “0” 串称为 B 串，全 “1” 串称为 I 串，既含 “0” 又含 “1” 的串则称为 F 串。
FBI树是一种二叉树，它的结点类型也包括 F 结点，B 结点和 I 结点三种。由一个长度为 2^N 的 “01” 串 S 可以构造出一棵 FBI 树 T，递归的构造方法如下：
-
T 的根结点为 R，其类型与串 S 的类型相同；
-
若串 S 的长度大于 1，将串 S 从中间分开，分为等长的左右子串 S1 和 S2 ；由左子串 S1 构造 R 的左子树 T1，由右子串 S2 构造 R 的右子树 T2。
现在给定一个长度为 2^N 的 “01” 串，请用上述构造方法构造出一棵FBI树，并输出它的后序遍历序列。
输入描述
第一行是一个整数 N（0≤N≤10）N（0≤N≤10）。
第二行是一个长度为 2^N 的 “01” 串。
输出描述
输出一个字符串，即 FBI 树的后序遍历序列。
输入输出样例
示例 1
3
10001011
输出
IBFBBBFIBFIIIFF错误做法
class node:def __init__(self,s,l=None,r=None):self.val=Noneself.l=l;self.r=rif '0' in s and 'l' in s:self.val='F'elif '0' in s:self.val='B'else:self.val='I'def build(s):if len(s)==1:return node(s)if len(s)==0:return Noneroot=node(s,build(s[:len(s)//2]),build(s[len(s)//2:]))return rootdef postorder(root):if root:postorder(root.l)postorder(root.r)print(root.val,end='')else:returnn=int(input())
s=input()
root=build(s)
postorder(root)
此外，可以使用一维数组存储二叉树.
def build(p,L,R):if L==R:if s[R]=='1':tree[p]='I'else:tree[p]='B'returnmid=(L+R)//2build(2*p,L,mid)build(2*p+1,mid+1,R)if tree[2*p]=='B' and tree[2*p+1]=='B':tree[p]='B'elif tree[2*p]=='I' and tree[2*p+1]=='I':tree[p]='I'else:tree[p]='F'def postorder(p):if tree[2*p]!='':postorder(2*p)if tree[2*p+1]!='':postorder(2*p+1)print(tree[p],end='')n=int(input())
s=[0]+list(input())
tree=['']*4400
build(1,1,len(s)-1)
postorder(1)