二叉樹遍歷反推python

A. 關於python中一個遞歸二叉樹遍歷的問題

if subsetWork+s[WORK]>maxWork:中，
s[WORK]是否應該改為s[WORK][2]

B. python編寫歐式二叉樹的問題

所以我就遇到了一下幾個問題：
1、該怎麼把二叉樹各個節點連起來？
2、怎麼定義內部數據成員？
3、如何實例化左右孩子？

在網上也沒找到比較簡單比較通用的Python二叉樹類實現，所以我花了點時間自己寫一個。
[python] view plain 在CODE上查看代碼片派生到我的代碼片
class Tree:
def __init__(self, val = '#', left = None, right = None):
self.val = val
self.left = left
self.right = right

#前序構建二叉樹
def FrontBuildTree(self):
temp = input('Please Input: ')
node = Tree(temp)
if(temp != '#'):
node.left = self.FrontBuildTree()
node.right = self.FrontBuildTree()
return node#因為沒有引用也沒有指針，所以就把新的節點給返回回去

#前序遍歷二叉樹
def VisitNode(self):
print(self.val)
if(self.val != '#'):
self.left.VisitNode()
self.right.VisitNode()

if __name__ == '__main__':
root = Tree()
root = root.FrontBuildTree()
root.VisitNode()

C. python 如何將一段字元串用二叉樹的後序遍歷列印出來

# -*- coding:utf-8 -*-def fromFMtoL( mid ): global las #全局後序遍歷 global fir #先序遍歷 root = fir[0] #取出當前樹根 fir = fir[1:] #取出樹根後 先序遍歷把根拿出來 下面一個元素做樹根 root_po = mid.find( root ) #在中序遍歷當中樹根的位置 left = mid[0:root_po] #左子樹 right = mid[root_po+1:len(mid)] #右子樹 ''' 後序遍歷： 左 右 根 先左子樹 再右子樹 最後跟 ''' #有左子樹的時候 if len(left) > 0: fromFMtoL( left ) #有右子樹的時候 if len(right) > 0: fromFMtoL( right ) #樹根寫進結果 las += rootif __name__ == "__main__" : # fir = input("請輸入先序遍歷：") #前序遍歷的結果 # mid = input("請輸入中序遍歷：") #中序遍歷的結果 fir = "DBACEGF" mid = "ABCDEFG" # fir = "ABC" # mid = "BAC" las = "" fromFMtoL( mid ) print(las)

D. python怎麼做二叉查找樹

可以的，和C++中類的設計差不多，以下是二叉樹的遍歷
class BTree:
def __init__(self,value):
self.left=None
self.data=value
self.right=None

def insertLeft(self,value):
self.left=BTree(value)
return self.left
#return BTree(value)

def insertRight(self,value):
self.right=BTree(value)
return self.right

def show(self):
print self.data

def preOrder(node):
node.show()
if node.left:
preOrder(node.left)
if node.right:
preOrder(node.right)

def inOrder(node):
if node:
if node.left:
inOrder(node.left)
node.show()
if node.right:
inOrder(node.right)

if __name__=='__main__':
Root=BTree('root')
A=Root.insertLeft('A')
C=A.insertLeft('C')
D=A.insertRight('D')
F=D.insertLeft('F')
G=D.insertRight('G')
B=Root.insertRight('B')
E=B.insertRight('E')

preOrder(Root)
print 'This is binary tree in-traversal'
inOrder(Root)

E. python 二叉樹是怎麼實現的

#coding:utf-8
#author:Elvis

classTreeNode(object):
def__init__(self):
self.data='#'
self.l_child=None
self.r_child=None

classTree(TreeNode):
#createatree
defcreate_tree(self,tree):
data=raw_input('->')
ifdata=='#':
tree=None
else:
tree.data=data
tree.l_child=TreeNode()
self.create_tree(tree.l_child)
tree.r_child=TreeNode()
self.create_tree(tree.r_child)

#visitatreenode
defvisit(self,tree):
#輸入#號代表空樹
iftree.dataisnot'#':
printstr(tree.data)+'	',
#先序遍歷
defpre_order(self,tree):
iftreeisnotNone:
self.visit(tree)
self.pre_order(tree.l_child)
self.pre_order(tree.r_child)

#中序遍歷
defin_order(self,tree):
iftreeisnotNone:
self.in_order(tree.l_child)
self.visit(tree)
self.in_order(tree.r_child)

#後序遍歷
defpost_order(self,tree):
iftreeisnotNone:
self.post_order(tree.l_child)
self.post_order(tree.r_child)
self.visit(tree)

t=TreeNode()
tree=Tree()
tree.create_tree(t)
tree.pre_order(t)
print'
'
tree.in_order(t)
print'
'
tree.post_order(t)

F. 數據結構，已知遍歷反推二叉樹

先序遍歷：GFKDAIEBCHJ
中序遍歷：DIAEKFCJHBG

由前序知，g為root，f為左root，又根據中序知道，g沒右支。
看f，由中序知，DIAEK為f左支，CJHB為f右支
由前序知，k為f左root，d為k左root，k無右支
又由中序知，d沒左支。
那麼iae為d右支，又由前序知，a為d右root，而i、e為其左右葉子
同樣的道理計算出f右支cjhb的順序，很容易就求出來啦

G. 二叉樹，如何從兩種遍歷的結果推出另一種遍歷方法簡單詳細一點。注意不是編程求解

這個問題呢其實很簡單，去年考試我們就考到了
1．中序遍歷的遞歸演算法定義：
若二叉樹非空，則依次執行如下操作：
(1)遍歷左子樹；
(2)訪問根結點；
(3)遍歷右子樹。
2．先序遍歷的遞歸演算法定義：
若二叉樹非空，則依次執行如下操作：
(1) 訪問根結點；
(2) 遍歷左子樹；
(3) 遍歷右子樹。
3．後序遍歷得遞歸演算法定義：
若二叉樹非空，則依次執行如下操作：
(1)遍歷左子樹；
(2)遍歷右子樹；
(3)訪問根結點。
比如你知道一個程序的先序遍歷是ABCDEFG 中序遍歷是CBDAEGF讓你推算出後序遍歷
因為先序遍歷的順序是根-左-右 那麼我們看先序遍歷ABCDEFG，那麼A就是根
再看中序遍歷CBDAEGF，根據中序遍歷的左-根-右 看出A左邊CBD的都是左子樹，右邊的EGF是左子樹
然後對先序遍歷劃分 A/BCD/EFG
對左子樹CBD 由先序遍歷中的A/BCD/EFG可以看出BCD中B在前面 則B是左子樹的根 C是下一行的左子樹
同理可對EFG分析
那麼畫出圖 A
/ \
B E
/\ \
C D F
/
G
那麼後序遍歷CDBGFEA
我當初也學了一段時間，比較繞是吧
我在這寫了半天 不知道你能看懂不
不行的加我Q

H. python 二叉樹先序遍歷什麼意思

先序遍歷簡單說就是碰到啥就輸出啥，不過二叉樹有根節點，左右子節點的結構關系，所以先序遍歷更准確的說，是先遍歷根節點，然後左節點，右節點，在遍歷左節點的時候，也是先遍歷左節點的跟節點，然後左節點的左節點，左節點的右節點，依此類推。。。詳細的信息可以看看計算機中的數據結構

I. 怎麼根據先序遍歷和中序遍歷來還原二叉樹

反過來，從樹末端往樹根逆推。

J. 遍歷結果逆推二叉樹

由兩種遍歷所得的順序能唯一確定一棵二叉樹，比如給定了一顆二叉樹的先序序列是:ABDECFG,中序序列是：DBEAFCG，由先序序列可以確定該二叉樹根為A,因為先序遍歷的順序是從根到左子樹再到右子樹，然後從中序序列中，可以得知DBE在A的左子樹，而FCG在A的右子樹，由於在先序序列中B緊跟在A後，所以B肯定是A左子樹的樹根，再看中序序列里，A的左子樹是DBE，由中序序列遍歷的順序為：左子樹，雙親，右子樹，可知D為B的左子樹，E為B的右子樹，同樣可以分析樹根A的右子樹，先序序列中ABDE已經將樹根和左子樹遍歷完成，所以剩下的CFG是右子樹的先序遍歷序列，可知C為右子樹的樹根，F為C的左子樹，G為C的右子樹，所以該二叉樹按層序遍歷的順序應該是ABCDEFG。