二叉樹(shù)存儲(chǔ)

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

在class Node中

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

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

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

使用靜態(tài)數(shù)組時(shí)，對(duì)應(yīng)的tree假如不是滿(mǎn)二叉樹(shù)，則應(yīng)該使用-1或者0填補(bǔ)空缺，這樣tree對(duì)應(yīng)的靜態(tài)數(shù)組即可使用于任何一個(gè)二叉樹(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)行訪(fǎng)問(wè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)行訪(fǎng)問(wè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='')

按照左兒子、右兒子、父的順序訪(fǎng)問(wèn)。

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

由先序遍歷和后序遍歷不能確定一棵樹(shù)。

FBI樹(shù)

題目描述

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

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

1. T 的根結(jié)點(diǎn)為 R，其類(lèi)型與串 S 的類(lèi)型相同；

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

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

輸入描述

第一行是一個(gè)整數(shù)?N（0≤N≤10）N（0≤N≤10）。

第二行是一個(gè)長(zhǎng)度為?2^N?的 “01” 串。

輸出描述

輸出一個(gè)字符串，即 FBI 樹(shù)的后序遍歷序列。

輸入輸出樣例

示例 1

3 ?

10001011

輸出

IBFBBBFIBFIIIFF

?錯(cuò)誤做法

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ù)組存儲(chǔ)二叉樹(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)