蓝桥杯备赛（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，递归的构造方法如下：

1. T 的根结点为 R，其类型与串 S 的类型相同；

2. 若串 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)