二叉樹存儲

普通做法，二叉樹一個節(jié)點包括結(jié)點的數(shù)值以及指向左右子節(jié)點的指針

在class Node中

def __init__(self,s,l=None,r=None):self.val=Noneself.l=lself.r=r

在競賽中，我們往往使用靜態(tài)數(shù)組實現(xiàn)二叉樹，定義一個大小為N的靜態(tài)結(jié)構(gòu)體數(shù)組，使用其來存儲一棵二叉樹。

#定義靜態(tài)數(shù)組
tree=['']*10000
#根節(jié)點
tree[1]
#結(jié)點tree[p]的左子節(jié)點
tree[2*p]
#結(jié)點tree[p]的右子節(jié)點
tree[2*p+1]

使用靜態(tài)數(shù)組時，對應(yīng)的tree假如不是滿二叉樹，則應(yīng)該使用-1或者0填補(bǔ)空缺，這樣tree對應(yīng)的靜態(tài)數(shù)組即可使用于任何一個二叉樹。?

三種遍歷方式

先序遍歷

EBADCGFIH

def preorder(p):print(tree[p],end='')if tree[2*p]!='':postorder(2*p)if tree[2*p+1]!='':postorder(2*p+1)

按照父、左兒子、右兒子的順序進(jìn)行訪問

中序遍歷

ABCDEFGHI

def inorder(p):if tree[2*p]!='': inorder(2*p)print(tree[p],end='')if tree[2*p+1]!='': inorder(2*p+1)

按照左兒子 、父、右兒子的順序進(jìn)行訪問

后序遍歷

ACDBFHIGE

def postorder(p):if tree[2*p] != '':    postorder(2*p)if tree[2*p+1] !='':   postorder(2*p+1)print(tree[p],end='')

按照左兒子、右兒子、父的順序訪問。

根據(jù)中序遍歷和后序遍歷可以確定一棵樹。

由先序遍歷和后序遍歷不能確定一棵樹。

FBI樹

題目描述

我們可以把由 “0” 和 “1” 組成的字符串分為三類：全 “0” 串稱為 B 串，全 “1” 串稱為 I 串，既含 “0” 又含 “1” 的串則稱為 F 串。

FBI樹是一種二叉樹，它的結(jié)點類型也包括 F 結(jié)點，B 結(jié)點和 I 結(jié)點三種。由一個長度為?2^N?的 “01” 串 S 可以構(gòu)造出一棵 FBI 樹 T，遞歸的構(gòu)造方法如下：

1. T 的根結(jié)點為 R，其類型與串 S 的類型相同；

2. 若串 S 的長度大于 1，將串 S 從中間分開，分為等長的左右子串 S1 和 S2 ；由左子串 S1 構(gòu)造 R 的左子樹 T1，由右子串 S2 構(gòu)造 R 的右子樹 T2。

現(xiàn)在給定一個長度為?2^N?的 “01” 串，請用上述構(gòu)造方法構(gòu)造出一棵FBI樹，并輸出它的后序遍歷序列。

輸入描述

第一行是一個整數(shù)?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)

此外，可以使用一維數(shù)組存儲二叉樹.

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)