[Python] 實作BST的走訪

承襲上一回[Python] 實作Binary Tree，今天要介紹怎樣走訪在Binary tree中各個Node，俗稱Binary Tree Traversal．

一般的走訪有四種方式：

• Preorder Traversal 前序遍歷
  理論上的順序是：根、左子樹、右子樹。根排在前面。
  即是Depth-first Search。
• Inorder Traversal 中序遍歷
  理論上的順序是：左子樹、根、右子樹。根排在中間。
  實際上是採用Depth-first Search，只不過更動了節點的輸出順序。
• Postorder Traversal 後序遍歷
  理論上的順序是：左子樹、右子樹、根。根排在後面。
  實際上是採用Depth-first Search，只不過更動了節點的輸出順序。
• Level-order Traversal 層序遍歷
  即是Breath-first Search。

這篇先介紹前三種．
先建立Tree

#class TreeNode(object):
#    def __init__(self, x):
#        self.val = x
#        self.left = None
#        self.right = None
# 假設tree node 已經建立好了

root = TreeNode(1)
root.left = TreeNode(5)
root.right=TreeNode(2)
root.right.left=TreeNode(3)
root.right.right=TreeNode(4)

#形狀
     1
    / \
   5   2
      / \
     3   4

• Preorder

class preorder(object):
    def preorder(self,root):

        self.lst = list() 
        #建立最後要輸出的陣列，顯示走訪的順序
        self.travel(root)
        return self.lst

    def travel(self, root):      
        if not root:
            return
        else:
            self.lst.append(root.val) 
            #先輸出根
            self.travel(root.left)
            #先往左邊走
            self.travel(root.right)
            #再往右邊走

## output: [1, 5, 2, 3, 4]

• Inorder 這邊只需改動輸出的節點順序

class preorder(object):
    def preorder(self,root):

        self.lst = list()
        self.travel(root)
        return self.lst

    def travel(self, root):


        if not root:
            return
        else:
            self.travel(root.left) 
            #先往左走
            self.lst.append(root.val)
            #再輸出node value
            self.travel(root.right)

# output:[5, 1, 3, 2, 4]

• post order

class preorder(object):
    def preorder(self,root):

        self.lst = list()
        self.travel(root)
        return self.lst

    def travel(self, root):


        if not root:
            return
        else:
            self.travel(root.left)
            #也是只有改動順序
            self.travel(root.right)
            self.lst.append(root.val)

#output: [5, 3, 4, 2, 1]

實作上不難，只是要想一下recurisive的方式以及輸出的順序就ok了．（說是這樣說，但是第一次看還是花了五六個小時才懂orz)