Python：每日一题之FBI树（深度优先遍历）
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
题目描述
我们可以把由 “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树并输出它的后序遍历序列。
输入描述
第一行是一个整数 N0 ≤ N ≤ 10。
第二行是一个长度为 2^N 的 “01” 串。
输出描述
输出一个字符串即 FBI 树的后序遍历序列。
输入输出样例
输入
3
10001011
输出
IBFBBBFIBFIIIFF参考代码
def b_FBI(p,L,R): #p为根LR 分别为左右子节点
if L==R: #左右节点相等时
if s[R]=='1': t[p]='I' #叶子
else: t[p]='B'
return
m=(L+R)//2
b_FBI(2*p,L,m) #左支范围Lm
b_FBI(2*p+1,m+1,R) #右支范围L+1,R
if t[2*p]=='B' and t[2*p+1]=='B': t[p]='B'
elif t[2*p]=='I' and t[2*p+1]=='I': t[p]='I'
else: t[p]='F'
def postorder(p): #后序遍历
if t[2*p]!='': postorder(2*p)
if t[2*p+1]!='': postorder(2*p+1)
print(t[p],end='')
n=int(input())
s=list(input())
t=['']*4400 #大于4096就行1024*4=4096创建一维数组
b_FBI(1,0,len(s)-1)
postorder(1)二叉树的深度优先遍历
1、 先根序列遍历
def postorder(p):
print(tree[p],end='')
if tree[2*p]!='': postorder(2*p)
if tree[2*p+1]!='': postorder(2*p+1)输出E B A D C G F I H
2、中根序列遍历
def postorder(p):
if tree[2*p]!='': postorder(2*p)
print(tree[p],end='')输出 A B C D E F G H I
3、后根序列遍历
def postorder(p):
if tree[2*p]!='': postorder(2*p)
if tree[2*p+1]!='': postorder(2*p+1)
print(tree[p],end='')输出A C D B F H I G E