前幾天忽然對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()