python樹的遍歷

Ⅰ python怎麼用遞歸遍歷多層目錄樹

#coding=utf-8
search_id = '69d0'
search_list = [{'id':'0337', 'name':'de', 'parent_id':'None'},
{'id':'2ddf', 'name':'se', 'parent_id':'None'},
{'id':'3010', 'name':'12', 'parent_id':'69d0'},
{'id':'3119', 'name':'121', 'parent_id':'3010'},
{'id':'3229', 'name':'1211', 'parent_id':'3119'},
{'id':'3d37', 'name':'14', 'parent_id':'69d0'},
{'id':'58c8', 'name':'11', 'parent_id':'69d0'},
{'id':'63b9', 'name':'a','parent_id':'None'},
{'id':'954c', 'name':'n', 'parent_id':'63b9'},
{'id':'69d0', 'name':'1', 'parent_id':'954c'},
{'id':'d2f9', 'name':'13', 'parent_id':'69d0'},
{'id':'defb', 'name':'test', 'parent_id':'None'}]
search_ids = []
#例如如果search_id = '69d0' search_ids=[3010,3d37,58c8,d2f9,3119,3229]

def search_pid(pid,id_list,id_results):
for id in id_list:
if id['id'] not in id_results:
if id['parent_id'] in pid:
id_results.append(id['id'])
pid.append(id['id'])
search_pid(pid,id_list,id_results)

search_pid([search_id],search_list,search_ids)
print search_ids

Ⅱ 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()

Ⅲ 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)

Ⅳ Python演算法系列—深度優先遍歷演算法

一、什麼是深度優先遍歷
深度優先遍歷演算法是經典的圖論演算法。從某個節點v出發開始進行搜索。不斷搜索直到該節點所有的邊都被遍歷完，當節點v所有的邊都被遍歷完以後，深度優先遍歷演算法則需要回溯到v以前驅節點來繼續搜索這個節點。
注意：深度優先遍歷問題一定要按照規則嘗試所有的可能才行。

二、二叉樹

2.二叉樹類型
二叉樹類型：空二叉樹、滿二叉樹、完全二叉樹、完美二叉樹、平衡二叉樹。

空二叉樹：有零個節點
完美二叉樹：每一層節點都是滿的二叉樹（如1中舉例的圖）
滿二叉樹：每一個節點都有零個或者兩個子節點
完全二叉樹：出最後一層外，每一層節點都是滿的，並且最後一層節點全部從左排列
平衡二叉樹：每個節點的兩個子樹的深度相差不超過1.

註：國內對完美二叉樹和滿二叉樹定義相同
3.二叉樹相關術語
術語 解釋
度 節點的度為節點的子樹個數
葉子節點 度為零的節點
分支節點 度不為零的節點
孩子節點 節點下的兩個子節點
雙親節點 節點上一層的源節點
兄弟節點 擁有同一雙親節點的節點
根 二叉樹的源頭節點
深度 二叉樹中節點的層的數量

DLR（先序）：
LDR（中序）：
LRD(後序）：
注意：L代表左子樹R代表右子樹；D代表根

6.深度優先遍歷和廣度優先遍歷
深度優先遍歷：前序、中序和後序都是深度優先遍歷
從根節點出發直奔最遠節點，
廣度優先遍歷：首先訪問舉例根節點最近的節點，按層次遞進，以廣度優先遍歷上圖的順序為：1-2-3-4-5-6-7
三、面試題+勵志
企鵝運維面試題：
1.二叉樹遍歷順序：看上文
2.用你熟悉的語言說說怎麼創建二叉樹？ python看上文

Ⅳ 求一個python的三叉樹演算法

這是網路上的一個版本，我自己做了一點修改，這是一個n叉樹，希望對你有所幫助

#!/usr/bin/python
#-*-coding:utf-8-*-
'''
Createdon2014-3-26

@author:qcq
'''

#==============================================================================
#tree.py:
#==============================================================================
#--
#$Revision:1.7$
#$Date:2000/03/2922:36:12$
#modifiedbyqcqin2014/3/27
#modifiedbyqcqin2014/4/23增加了遍歷樹的非遞歸版本的廣度優先和深度優先
#--

#================================================================
#Contents
#----------------------------------------------------------------
#classTree:Genericn-arytreenodeobject
#classNodeId:Representsthepathtoanodeinann-arytree
#----------------------------------------------------------------

#importstring


classTree:
"""Genericn-arytreenodeobject

Childrenareadditive;noprovisionfordeletingthem.
:0forthefirst
childadded,1forthesecond,andsoon.

modifiedbyqcqin2014/3/27.

Exports:
Tree(parent,value=None)Constructor
.parentIfthisistherootnode,None,otherwise
theparent'sTreeobject.
.childListListofchildren,zeroormoreTreeobjects.
.valueValuepassedtoconstructor;canbeanytype.
.birthOrderIfthisistherootnode,0,otherwisethe
indexofthischildintheparent's.childList
.nChildren()Returnsthenumberofself'schildren.
.nthChild(n)Returnsthenthchild;raisesIndexErrorif
nisnotavalidchildnumber.
.fullPath():.
.nodeId():ReturnspathtoselfasaNodeId.
"""


#---Tree.__init__---

def__init__(self,parent,value=None):
"""ConstructorforaTreeobject.

[if(parentisNoneoraTreeobject)->
if(parentisNone)->
,nochildren,
andvalue(value)
else->

ofparent(parent)andnochildren,andvalue(value)
]
"""
#--1--
self.parent=parent
self.value=value
self.childList=[]

#--2--
#-[if(parentisNone)->
#self.birthOrder:=0
#else->
#parent:=
#self.birthOrder:=sizeofparent's.childList
#-]
ifparentisNone:
self.birthOrder=0
else:
self.birthOrder=len(parent.childList)
parent.childList.append(self)


#---Tree.nChildren---

defnChildren(self):
"""[
]
"""
returnlen(self.childList)


#---Tree.nthChild---

defnthChild(self,n):
"""[if(nisaninteger)->
if(0<=n<(numberofself'schildren)->
returnself's(n)thchild,countingfrom0
else->
raiseIndexError
]
"""
returnself.childList[n]


#---Tree.fullPath---

deffullPath(self):
""".

[returnasequence[c0,c1,...,ci]suchthatselfis
root.nthChild(c0).nthChild(c1).....nthChild(ci),or
anemptylistifselfistheroot]
"""

#--1--
result=[]
parent=self.parent
kid=self

#--2--
#[result+:=childnumbersfromparenttoroot,in
#reverseorder]
whileparent:
result.insert(0,kid.birthOrder)
parent,kid=parent.parent,parent

#--3--
returnresult


#---Tree.nodeId---

defnodeId(self):
""".
"""
#--1--
#[fullPath:=sequence[c0,c1,...,ci]suchthatselfis
#root.nthChild(c0).nthChild(c1).....nthChild(ci),or
#anemptylistifselfistheroot]
fullPath=self.fullPath()

#--2--
returnNodeId(fullPath)

defequals(self,node):
'''
'''
returnself.value==node.value

#===========================================================================
#deletethenodefromthetree
#===========================================================================
defdelete(self):
ifself.parentisNone:
return
else:
#temp=self.birthOrder
'''
ifdeletethemiddletreeobject,
.
'''
self.parent.childList.remove(self.parent.childList[self.birthOrder])
fori,jinzip(range(self.birthOrder+1,self.parent.nChildren()),self.parent.childList[self.birthOrder+1:]):
j.birthOrder=j.birthOrder-1


defupdate(self,value):
'''

'''
self.value=value

def__str__(self):
return"The%dchildwithvalue%d"%(self.birthOrder,self.value)#-----classNodeId-----

classNodeId:
""".

Exports:
NodeId(path):
[->
-id]
.path:[aspassedtoconstructor]
.__str__():[returnselfasastring]
.find(root):
[ifrootisaTreeobject->

treerootedat(root)->
returnthe.valueofthatnode
else->
returnNone]
.isOnPath(node):
[ifnodeisaTreeobject->
->
return1
else->
return0]
"""

#---NodeId.__init__---

def__init__(self,path):
"""ConstructorfortheNodeIdobject
"""
self.path=path


#---NodeId.__str__---

def__str__(self):
"""Returnselfindisplayableform
"""

#--1--
#[L:=alistoftheelementsofself.pathconvertedtostrings]
L=map(str,self.path)

#--2--
#["/"]
returnstring.join(L,"/")


#---NodeId.find---

deffind(self,node):
"""
"""
returnself.__reFind(node,0)


#---NodeId.__reFind---

def__reFind(self,node,i):
"""Recursivenodefindingroutine.Startsatself.path[i:].

[if(nodeisaTreeobject)
and(0<=i<=len(self.path))->
ifi==len(self.path)->
returnnode'svalue
elseifself.path[i:]describesapathfromnode
tosometreeobjectT->
returnT
else->
returnNone]
"""

#--1--
ifi>=len(self.path):
returnnode.value#We'rethere!
else:
childNo=self.path[i]

#--2--
#[->
#child:=thatchildnode
#else->
#returnNone]
try:
child=node.nthChild(childNo)
exceptIndexError:
returnNone

#--3--
#[if(i+1)==len(self.path)->
#returnchild
#elseifself.path[i+1:]describesapathfromnodeto
#sometreeobjectT->
#returnT
#else->
#returnNone]
returnself.__reFind(child,i+1)


#---NodeId.isOnPath---

defisOnPath(self,node):
"""Isself'spathtoorthroughthegivennode?
"""

#--1--
#[nodePath:=pathlistfornode]
nodePath=node.fullPath()

#--2--
#[ifnodePathisaprefixof,oridenticaltoself.path->
#return1
#else->
#return0]
iflen(nodePath)>len(self.path):
return0#Nodeisdeeperthanself.path

foriinrange(len(nodePath)):
ifnodePath[i]!=self.path[i]:
return0#Nodeisadifferentroutethanself.path

return1

Ⅵ 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)

Ⅶ python遍歷目錄就是這么簡單

有時我們有列出目錄下都有哪些文件和子目錄的需求，這種情況是有現成命令可用的，比如windows下的dir命令，linux下的ls命令都可以，那我們用python代碼怎麼實現呢？

我們利用python豐富的庫很容易就能實現一個簡易版本，下面我們就用4種方法來實現它。

一、使用os.popen

os.popen工作原理是新建一個子進程，然後用這個子進程執行命令，父進程與子進程間通過管道進行通信。

根據調用popen時的傳參，我們可以通過管道讀取子進程的輸出也可以向子進程寫數據，默認是讀取子進程的輸出。

從以上描述可以看出popen是非常通用的，不是只能用於我們這個例子哦。

那我們開始用它實現我們的需求吧，代碼如下：

哈哈，是不是很簡單，這種方式雖然能達到目的但其實並不是我們想要的，我們本來就是要實現ls的，結果調用了ls，所以嚴格意義上來說我們並沒有實現ls，那讓我們繼續往下看其它方法吧，嘿嘿。

二、使用glob.glob

glob可以根據你使用的通配符對文件進行匹配，利用這個特性我們可以列出當前目錄下都有哪些文件和子目錄，如下代碼：

三、使用os.listdir

os.listdir同樣可以列出某個目錄下都有哪些文件和子目錄，如下代碼：

四、使用os.walk

os.walk在遍歷目錄方面非常強大，它不但可以遍歷你需要的目錄，也可以遞歸遍歷子目錄且遞歸的深度可以用代碼控制，下面讓我們分別看下怎麼遍歷整個目錄樹以及怎麼控制深度吧。

os.walk默認是遍歷整個目錄樹的，如下代碼就會遞歸列印出當前目錄下所有文件：

那我們怎麼控制遍歷的深度，比如只遍歷n層呢？其實很簡單，只需要定義一個深度變數，然後到達n後跳出循環即可，如下代碼就只遍歷1層：

至此我們已經寫完4種方法了，如果你還有其他方法，歡迎評論交流。

Ⅷ python 遞歸函數使用裝飾器

參考一下
第一步：簡單實現裝飾器
def login(func):
print("in Login")
return func

def tv(name):
print("{name} in TV".format(name = name))

tv = login(tv)
tv('Jack')

# out:
# in Login
# Jack in TV

第二步：同上
效果相同，但是使用的是@login
def login(func):
print("in Login")
return func

@login
def tv(name):
print("{name} in TV".format(name = name))

#tv = login(tv)
tv('Jack')

# out:
# in Login
# Jack in TV

但是出現問題，注銷最後的執行語句仍有輸出，原因在於@login的調用，即@login相當於執行了tv = login(tv) 所以才有輸出。
def login(func):
print("in Login")
return func

@login
def tv(name):
print("{name} in TV".format(name = name))

#tv = login(tv)
#tv('Jack')

# out:
# in Login

如下調整可解決
def login(func):
def inner(arg):
print("in Login")
# return func
func(arg)
return inner
@login
def tv(name):
print("{name} in TV".format(name = name))

#tv = login(tv)
tv('Jack')

# out:
# in Login
# Jack in TV

簡單的遞歸函數
#!/usr/bin/env python
#遞歸函數

def calc(num):
print("Number:",num)
if num/2 > 1:
calc(num/2)
print("After Number:",num/2)
calc(10)

# Number: 10
# Number: 5.0
# Number: 2.5
# Number: 1.25
# After Number: 1.25
# After Number: 2.5
# After Number: 5.0

遞歸實現斐波那契數列
# Fibonacci sequence
# F[n]=F[n-1]+F[n-2](n>=2,F[0]=1,F[1]=1)
# 斐波那契數列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

fibList = [1,1]

def getFib(fibList):
print(fibList)
if fibList[-1] + fibList[-2] < 300:
fibList.append(fibList[-1] + fibList[-2])
getFib(fibList)
pass
pass

getFib(fibList)
print("[FINAL]:",fibList)

# [1, 1]
# [1, 1, 2]
# [1, 1, 2, 3]
# [1, 1, 2, 3, 5]
# [1, 1, 2, 3, 5, 8]
# [1, 1, 2, 3, 5, 8, 13]
# [1, 1, 2, 3, 5, 8, 13, 21]
# [1, 1, 2, 3, 5, 8, 13, 21, 34]
# [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
# [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]
# [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144]
# [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233]
# [FINAL]: [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233]