Algorithm 演算法 - 樹遍歷系列 Morris traversal 莫里斯遍歷

簡介 Intro

此演算法是由 Joseph M. Morris 在 1979 年的論文「Traversing Binary Trees Simply and Cheaply」首次提出,因此稱之為 -- Morris traversal。其核心概念是利用樹中的空閒指針,縮減空間複雜度到常數。Morris traversal 主要是中序處理,但是修改後也是可以適用於前序和後序。

中序 In-Order

  1. 先初始化 root 作為當前節點 curr
  2. 當前節點 curr 不是 NULL 的時候,就往左子樹走

    • 當沒有左子樹的時候,就 輸出 curr 並將其 curr 設定為右節點

        if curr.left is None:
            print(curr)
            curr = curr.right
      
    • 當有左子樹時,在這個左子樹中找出最右側的節點 rightmost

      • 如果其右側節點為當前節點 curr,就將右節點設定為 NULL(還原樹的結構),輸出 curr 並將 curr 設定為 curr 的右節點

          if rightmost.right == curr:
              rightmost.right = None
              print(curr)
              curr = curr.right
        
      • 如果 rightmost 沒有右節點的話,將其右節點指向為 curr,再將 curr 更新為左節點

          if rightmost.right is None:
              rightmost.right = curr
              curr = curr.left
        
  3. 重複步驟一和二直到 curr 等於 NULL

14214057-7cc645706e7741e3b5ed62b320000354.jpeg

def inorder(root):
    curr = root

    while curr:
        if curr.left:
            prev = curr.left

            while prev.right and prev.right != curr:
                prev = prev.right

            if prev.right:
                prev.right = None
                yield curr.val
                curr = curr.right
            else:
                prev.right = curr
                curr = curr.left
        else:
            yield curr.val
            curr = curr.right

前序 Pre-Order

與中序基本上相同,唯一不同的地方在於輸出的順序

  1. 先初始化 root 作為當前節點 curr
  2. 當前節點 curr 不是 NULL 的時候,就往左子樹走

    • 當沒有左子樹的時候,就 輸出 curr 並將其 curr 設定為右節點

        if curr.left is None:
            curr = curr.right
      
    • 當有左子樹時,在這個左子樹中找出最右側的節點 rightmost

      • 如果 rightmost 的右側節點為當前節點 curr,就將其設定為 NULL(還原樹的結構),將 curr 設定為 curr 的右節點

          if rightmost.right == curr:
              rightmost.right = None
              curr = curr.right
        
      • 如果 rightmost 沒有右節點的話,將其右節點指向為 curr輸出 curr,再將 curr 更新為左節點

          if rightmost.right is None:
              rightmost.right = curr
              print(curr)   # 這邊跟 inorder 不同的地方
              curr = curr.left
        
  3. 重複步驟一和二直到 curr 等於 NULL

前序是在做連結的時候(rightmost.right = curr)時輸出

中序則是在還原樹(rightmost.right = None)的時候輸出

14221458-aa5f9e92cce743ccacbc735048133058.jpeg

def preorder(root):
    curr = root

    while curr:
        if curr.left:
            prev = curr.left

            while prev.right and prev.right != curr:
                prev = prev.right

            if prev.right:
                prev.right = None
                curr = curr.right
            else:
                yield curr.val
                prev.right = curr
                curr = curr.left
        else:
            yield curr.val
            curr = curr.right

後序 Post-Order

後續則稍顯複雜,可以有兩種方式。第一種是使用多增加一個臨時節點 temp,並設定 root 為其左節點。第二種則是將原本的條件轉換成右節點

添加臨時節點

  1. temp 設定為 curr
  2. 當前節點 curr 不是 NULL 的時候,就往左子樹走

    • 當沒有左子樹的時候,將其 curr 設定為右節點

        if curr.left is None:
            curr = curr.right
      
    • 當有左子樹時,在這個左子樹中找出最右側的節點rightmost

      • 如果rightmost的右節點為當前節點 curr,就將其設定為 NULL(還原樹的結構)。倒序輸出 curr 的左子樹節點到 rightmost 的所有節點。將 curr 設定為 curr 的右節點

          if rightmost.right == curr:
              rightmost.right = None
              reverse(curr.left)
              curr = curr.right
        
      • 如果rightmost的沒有右節點,將其右節點指向為 curr後,再將 curr 更新為左節點

          if rightmost.right is None:
              rightmost.right = curr
              curr = curr.left
        
  3. 重複步驟一和二直到 curr 等於 NULL

15165951-7991525829134fb3beefed9fbf7e0536.jpeg

def reverse(node):
    tmp = []
    while node:
        tmp.append(node.val)
        node = node.right
    for val in range(reversed(tmp)):
        yield val

def postorder(root):
    curr = root

    while curr:
        if curr.left:
            prev = curr.left

            while prev.right and prev.right != curr:
                prev = prev.right

            if prev.right:
                prev.right = None
                reverse(curr.left)
            else:
                prev.right = curr
                curr = curr.left
        else:
            curr = curr.right
    reverse(root)

條件轉換

  1. 先初始化 root 作為當前節點 curr
  2. 當前節點 curr 不是 NULL 的時候,就往左子樹走

    • 當沒有右子樹的時候,就 輸出 curr 並將其 curr 設定為左節點
      curr = curr -> left

        if curr.right is None:
            print(curr)
            curr = curr.left
      
    • 當有右子樹時,在這個右子樹中找出最左側的節點 leftmost

      • 如果其 leftmost 的左節點為當前節點 curr,就將其設定為 NULL(還原樹的結構),並將 curr 設定為 curr 的左節點
        leftmost -> left = NULL, curr = curr -> left

          if leftmost.left == curr:
              leftmost.left = None
              curr = curr.left
        
      • 如果 leftmost 沒有左節點的話,將其左節點指向為 curr輸出 curr ,再將 curr 更新為右節點 leftmost -> left = curr, curr = curr -> right

          if leftmost.left is None:
              leftmost.left = curr
              print(curr)
              curr = curr.right
        
  3. 重複步驟一和二直到 curr 等於 NULL

def postorder(root):
    curr = root

    while curr:
        if curr.right:
            prev = curr.right

            while prev.left and prev.left != curr:
                prev = prev.left

            if prev.left:
                prev.left = None
                curr = curr.left
            else:
                yield curr.val
                prev.left = curr
                curr = curr.right
        else:
            yield curr.val
            curr = curr.left

Reference

Did you find this article valuable?

Support 攻城獅 by becoming a sponsor. Any amount is appreciated!