2015年10月25日 星期日

[Python] 實作BST的走訪

enter image description here
承襲上一回[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)