厦门市建设执业资格管理中心网站,比较顺口的公司名字,深圳网站设计建设,郑州手机网站制作公司二叉树存储
普通做法#xff0c;二叉树一个节点包括结点的数值以及指向左右子节点的指针
在class Node中
def __init__(self,s,lNone,rNone):self.valNoneself.llself.rr
在竞赛中#xff0c;我们往往使用静态数组实现二叉树#xff0c;定义一个大小为N的静态结构体数组…二叉树存储
普通做法二叉树一个节点包括结点的数值以及指向左右子节点的指针
在class Node中
def __init__(self,s,lNone,rNone):self.valNoneself.llself.rr
在竞赛中我们往往使用静态数组实现二叉树定义一个大小为N的静态结构体数组使用其来存储一棵二叉树。
#定义静态数组
tree[]*10000
#根节点
tree[1]
#结点tree[p]的左子节点
tree[2*p]
#结点tree[p]的右子节点
tree[2*p1]
使用静态数组时对应的tree假如不是满二叉树则应该使用-1或者0填补空缺这样tree对应的静态数组即可使用于任何一个二叉树。
三种遍历方式
先序遍历 EBADCGFIH
def preorder(p):print(tree[p],end)if tree[2*p]!:postorder(2*p)if tree[2*p1]!:postorder(2*p1)
按照父、左儿子、右儿子的顺序进行访问 中序遍历 ABCDEFGHI
def inorder(p):if tree[2*p]!: inorder(2*p)print(tree[p],end)if tree[2*p1]!: inorder(2*p1)
按照左儿子 、父、右儿子的顺序进行访问 后序遍历 ACDBFHIGE
def postorder(p):if tree[2*p] ! : postorder(2*p)if tree[2*p1] !: postorder(2*p1)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树并输出它的后序遍历序列。
输入描述
第一行是一个整数 N0≤N≤10N0≤N≤10。
第二行是一个长度为 2^N 的 “01” 串。
输出描述
输出一个字符串即 FBI 树的后序遍历序列。
输入输出样例
示例 1
3 10001011 输出 IBFBBBFIBFIIIFF 错误做法
class node:def __init__(self,s,lNone,rNone):self.valNoneself.ll;self.rrif 0 in s and l in s:self.valFelif 0 in s:self.valBelse:self.valIdef build(s):if len(s)1:return node(s)if len(s)0:return Nonerootnode(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:returnnint(input())
sinput()
rootbuild(s)
postorder(root)此外可以使用一维数组存储二叉树.
def build(p,L,R):if LR:if s[R]1:tree[p]Ielse:tree[p]Breturnmid(LR)//2build(2*p,L,mid)build(2*p1,mid1,R)if tree[2*p]B and tree[2*p1]B:tree[p]Belif tree[2*p]I and tree[2*p1]I:tree[p]Ielse:tree[p]Fdef postorder(p):if tree[2*p]!:postorder(2*p)if tree[2*p1]!:postorder(2*p1)print(tree[p],end)nint(input())
s[0]list(input())
tree[]*4400
build(1,1,len(s)-1)
postorder(1)
