首页 > 代码库 > 如果Google面试让你用python写一个树的遍历程序
如果Google面试让你用python写一个树的遍历程序
前几天忽然对python很感兴趣，学了几天也感觉它非常的简洁实用。打破了我这么长时间对java C# C 和vb的审美疲劳，让我眼前一亮。“就像读英文一样简单”这句话评价python说的很合理。
我对python的好感很大部分是因为听说google很多程序用python，而且在google app engine里面和支持python。如果你去google面试或者笔试，很可能就会考到这个题：用python实现树的遍历。
自己试着写了一下，不过毕竟是菜鸟，有问题请多多指教。
运行效果如下：
源程序如下：
#!user/bin/python
#树的实体（包括 Id, value, fatherId）
class treeModel:
‘‘‘tree view‘‘‘
def __init__(self,Id,value,fatherId):
self.Id=Id
self.value=http://www.mamicode.com/value
self.fatherId=fatherId
def show(self):
return self.value
# 树的遍历和展示
class treeShow:
‘‘‘tree show‘‘‘
logList = [treeModel(0,‘addTree‘,0)] #记录已经遍历过的节点
writtenList = [treeModel(0,‘addTree‘,0)] #记录已经打印出的节点
def __init__(self,rootId,list):
self.rootId = rootId
self.list=list
#通过Id获取节点
def getModelById(self,Id):
for t in self.list:
if t.Id == Id:
return t
return None
#判断是否有子节点
def haveChild(self,t):
for t1 in self.list:
if t1.fatherId == t.Id and not self.IsInLogList(t1):
return True
return False
#获取第一个没有遍历的子节点
def getFirstChild(self,t):
for t1 in self.list:
if t1.fatherId == t.Id and not self.IsInLogList(t1):
return t1
return None
#判断某节点是否已经被遍历
def IsInLogList(self,t):
for t1 in self.logList:
if t1.Id == t.Id:
return True
return False
#判断某节点是否已经打印
def IsInWrittenList(self,t):
for t1 in self.writtenList:
if t1.Id == t.Id:
return True
return False
#获取父节点
def getFatherTree(self,t):
for t1 in self.list:
if t1.Id == t.fatherId:
return t1
return None
#遍历打印
def show(self):
currentTree = self.getModelById(self.rootId)
s = ‘ ‘
strNum = 1
while(True):
if self.haveChild(currentTree):
if not self.IsInWrittenList(currentTree):
print s*strNum,currentTree.show()
self.writtenList.append(currentTree)
currentTree = self.getFirstChild(currentTree)
strNum += 1
continue
else:
if(currentTree.Id == self.rootId):
break
else:
if not self.IsInWrittenList(currentTree):
print s*strNum,currentTree.show()
self.logList.append(currentTree)
currentTree = self.getFatherTree(currentTree)
strNum -= 1
continue
#初始化一些节点实例
t1 = treeModel(1,‘A-1‘,0)
t2 = treeModel(2,‘B-1‘,1)
t3 = treeModel(3,‘B-2‘,1)
t4 = treeModel(4,‘C-1‘,2)
t5 = treeModel(5,‘C-2‘,2)
t6 = treeModel(6,‘C-3‘,3)
t7 = treeModel(7,‘C-4‘,3)
t8 = treeModel(8,‘D-1‘,4)
t9 = treeModel(9,‘E-1‘,8)
t10 = treeModel(10,‘E-2‘,8)
#将这些节点实例链式存储起来（就像数据库里存储一样）
list = [t1,t2,t3,t4,t5,t6,t7,t8,t9,t10]
#调用展示
ts = treeShow(1,list)
ts.show()
如果Google面试让你用python写一个树的遍历程序