如果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=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()