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]