二叉樹的深度優先周遊與廣度優先周遊

先說說為什麼要周遊，二叉樹不是已經排好序了麼？如果大于目前節點值，搜尋右子樹，小于目前值，繼續搜尋左子樹。

參考兩個sql：

select id,name,grade from student where id=1

select id,name,grade from student where name='李四'

• 按id查找，id是主鍵，已經建立索引，用二叉樹存儲，id就是二叉樹節點的key，可以按照二分查找法搜尋。
• 按name搜尋，隻能采用周遊的方法，必須保證檢查到樹上的每一個節點，不能有遺漏。

資料庫建立索引，可以加快搜尋速度，但要維護額外空間。

深度優先周遊

先周遊子節點，再周遊兄弟節點。

從根節點開始遞歸，如果存在子節點，繼續周遊子節點。

def traverse_d(self):
        self._traverse_d(self.root)
        
    ##深度優先周遊
    def _traverse_d(self,node):
        if(node == None):
            return
        self._traverse_d(node.lnode)
        self._traverse_d(node.rnode)
        print("key:%d==>value:%d"% (node.key,node.value))
           

廣度優先周遊

先周遊兄弟節點，在周遊子節點。

采用隊列實作，出隊時添加子節點。

def traverse_w(self):
        self._traverse_w(self.root)
    ## 廣度優先周遊
    def _traverse_w(self,node):
        q = Queue()
        q.put(node)
        while(not q.empty()):
            node = q.get()
            if(node.lnode!=None):
                q.put(node.lnode)
            if(node.rnode!=None):
                q.put(node.rnode)
            print("key:%d==>value:%d"% (node.key,node.value))
           

總結:

以作者的自身經曆，二叉樹的深度周遊比較好記，總是忘如何實作廣度優先，後來記住一個訣竅，廣度優先要有一個隊列，就記住了。放個圖，加深一下記憶。

隊列