簡介 Intro

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

中序 In-Order

先初始化 root 作為當前節點 curr
當前節點 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
```
重複步驟一和二直到 curr 等於 NULL

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

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

先初始化 root 作為當前節點 curr
當前節點 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
```
重複步驟一和二直到 curr 等於 NULL

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

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

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 為其左節點。第二種則是將原本的條件轉換成右節點

添加臨時節點

將 temp 設定為 curr
當前節點 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
```
重複步驟一和二直到 curr 等於 NULL

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)

條件轉換

先初始化 root 作為當前節點 curr
當前節點 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
```
重複步驟一和二直到 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

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

Comments

Software development

Debounce 防彈跳 & Throttle 節流

More from this blog

如何開始入門軟體工程領域 - 名詞解釋（長期更新）

我的 MacBook Pro (Apple Silicon) 設定

ChatGPT 下的發展預想

一些覺得有用的工具蒐藏

LeetCode Solution, Medium, 607. Sales Person

簡介 Intro

中序 In-Order

前序 Pre-Order

後序 Post-Order

添加臨時節點

條件轉換

Reference

Command Palette

Comments

Software development

Debounce 防彈跳 & Throttle 節流

More from this blog

簡介 Intro

中序 In-Order

前序 Pre-Order

後序 Post-Order

添加臨時節點

條件轉換

Reference