Morris Traversal遍歷二叉樹

本文轉(zhuǎn)載自http://www.cnblogs.com/AnnieKim/archive/2013/06/15/MorrisTraversal.html

本文主要解決一個問題，如何實現(xiàn)二叉樹的前中后序遍歷，有兩個要求：

  1. O(1) 空間復(fù)雜度，即只能使用常數(shù)空間；

  2. 二叉樹的形狀不能被破壞（中間過程允許改變其形狀）。

通常，實現(xiàn)二叉樹的前序（preorder）、中序（inorder）、后序（postorder）遍歷有兩個常用的方法：一是遞歸(recursive)，二是使用棧實現(xiàn)的迭代版本(stack+iterative)。這兩種方法都是 O(n) 的空間復(fù)雜度（遞歸本身占用stack空間或者用戶自定義的stack），所以不滿足要求。

Morris Traversal 方法可以做到這兩點，與前兩種方法的不同在于該方法只需要 O(1) 空間，而且同樣可以在 O(n) 時間內(nèi)完成。

要使用 O(1) 空間進(jìn)行遍歷，最大的難點在于，遍歷到子節(jié)點的時候怎樣重新返回到父節(jié)點（假設(shè)節(jié)點中沒有指向父節(jié)點的p指針），由于不能用棧作為輔助空間。為了解決這個問題， Morris 方法用到了線索二叉樹（threaded binary tree）的概念。在Morris方法中不需要為每個節(jié)點額外分配指針指向其前驅(qū)（predecessor）和后繼節(jié)點（successor），只需要利用葉子節(jié)點中的左右空指針指向某種順序遍歷下的前驅(qū)節(jié)點或后繼節(jié)點就可以了。

Morris 只提供了中序遍歷的方法，在中序遍歷的基礎(chǔ)上稍加修改可以實現(xiàn)前序，而后續(xù)就要再費點心思了。所以先從中序開始介紹。

首先定義在這篇文章中使用的二叉樹節(jié)點結(jié)構(gòu)，即由 elem， left 和 right 組成：

typedef int elem_t;

/**
 * @struct
 * @brief 二叉樹節(jié)點.
 */
typedef struct bt_node_t {
    elem_t elem;
    struct bt_node_t *left;
    struct bt_node_t *right;
};

一.中序遍歷

步驟：

  1. 初始化當(dāng)前節(jié)點 cur 為 root 節(jié)點.

  2. 如果 cur 沒有左孩子，則輸出當(dāng)前節(jié)點并將其右孩子作為當(dāng)前節(jié)點,即 cur = cur->right。

  3. 如果 cur 有左孩子，在當(dāng)前節(jié)點 cur 的左子樹中找到當(dāng)前節(jié)點 cur 在中序遍歷下的前驅(qū)節(jié)點。

    a) 如果前驅(qū)節(jié)點的右孩子為空，將它的右孩子設(shè)置為當(dāng)前節(jié)點。當(dāng)前節(jié)點更新為當(dāng)前節(jié)點的左孩子。

    b) 如果前驅(qū)節(jié)點的右孩子為當(dāng)前節(jié)點，將它的右孩子重新設(shè)為空（恢復(fù)樹的形狀）。輸出當(dāng)前節(jié)點。當(dāng)前節(jié)點更新為當(dāng)前節(jié)點的右孩子。

  4. 重復(fù)以上2、3直到當(dāng)前節(jié)點為空。

下圖為每一步迭代的結(jié)果（從左至右，從上到下）， cur 代表當(dāng)前節(jié)點，深色節(jié)點表示該節(jié)點已輸出。

中序遍歷
/**
 * @brief 使用Morrris算法進(jìn)行中序遍歷.
 * @param[in] root 根節(jié)點
 * @param[in] visit 訪問函數(shù)
 */
void 
in_order_mirrors(bt_node_t *root, int(*visit)(bt_node_t *))
{
    bt_node_t *cur;
    cur = root;
    while (cur != NULL) {
        if (cur->left == NULL) {
            visit(cur);
            cur = cur->right;   /* 將右孩子作為當(dāng)前節(jié)點 */
        }
        else {
            /* 查找cur節(jié)點的前驅(qū)節(jié)點 */
            bt_node_t *node = cur->left;
            while (node->right != NULL && node->right != cur)
                node = node->right;

            if (node->right == NULL) { /* 還沒有線索化，則建立線索 */
                node->right = cur;
                cur = cur->left;
            }
            else { /* 如果已經(jīng)線索化了，則訪問節(jié)點，并刪除線索 */
                visit(cur);
                node->right = NULL;
                cur = cur->right;
            }
        }
    }
}

復(fù)雜度分析：

空間復(fù)雜度： O(1) ，因為只用了兩個輔助指針。

時間復(fù)雜度： O(n) 。證明時間復(fù)雜度為 O(n)，最大的疑惑在于尋找中序遍歷下二叉樹中所有節(jié)點的前驅(qū)節(jié)點的時間復(fù)雜度是多少，即以下兩行代碼：

while (prev->right != NULL && prev->right != cur)

    prev = prev->right;

直覺上，認(rèn)為它的復(fù)雜度是 O(nlgn) ，因為找單個節(jié)點的前驅(qū)節(jié)點與樹的高度有關(guān)。但事實上，尋找所有節(jié)點的前驅(qū)節(jié)點只需要 O(n) 時間。n個節(jié)點的二叉樹中一共有n-1條邊，整個過程中每條邊最多只走2次，一次是為了定位到某個節(jié)點，另一次是為了尋找上面某個節(jié)點的前驅(qū)節(jié)點，如下圖所示，其中紅色是為了定位到某個節(jié)點，黑色線是為了找到前驅(qū)節(jié)點。所以復(fù)雜度為 O(n) 。

復(fù)雜度分析

二.先序遍歷

先序遍歷與中序遍歷相似，代碼上只有一行不同，不同就在于輸出的順序。

步驟：

  1. 初始化當(dāng)前節(jié)點 cur 為 root 節(jié)點.

  2. 如果 cur 沒有左孩子，則輸出當(dāng)前節(jié)點并將其右孩子作為當(dāng)前節(jié)點,即 cur = cur->right 。

  3. 如果 cur 有左孩子，在當(dāng)前節(jié)點 cur 的左子樹中找到當(dāng)前節(jié)點 cur在 中序遍歷下的前驅(qū)節(jié)點 。

    a) 如果前驅(qū)節(jié)點的右孩子為空，將它的右孩子設(shè)置為當(dāng)前節(jié)點。輸出當(dāng)前節(jié)點（在這里輸出，這是與中序遍歷唯一一點不同）。當(dāng)前節(jié)點更新為當(dāng)前節(jié)點的左孩子。

    b) 如果前驅(qū)節(jié)點的右孩子為當(dāng)前節(jié)點，將它的右孩子重新設(shè)為空。當(dāng)前節(jié)點更新為當(dāng)前節(jié)點的右孩子。

  4. 重復(fù)以上2、3直到 cur 為空。

先序遍歷
/**
 * @brief 使用Morrris算法先序遍歷
 * @param[in] root 根節(jié)點
 * @param[in] visit 訪問函數(shù)
 */
void
pre_order_morris(bt_node_t *root, int(*visit)(bt_node_t *))
{
 bt_node_t *cur;

 cur = root;
 while (cur != NULL) {
     if (cur->left == NULL) {
         visit(cur);
         cur = cur->right;
     }
     else {
         /* 查找前驅(qū) */
         bt_node_t *node = cur->left;
         while (node->right != NULL && node->right != cur)
             node = node->right;

         if (node->right == NULL) {
             visit(cur);
             node->right = cur;
             cur = cur->left;
         }
         else { /* 已經(jīng)線索化了，則刪除線索 */
             node->right = NULL;
             cur = cur->right;
         }
     }
 }
}

復(fù)雜度分析

時間復(fù)雜度與空間復(fù)雜度都與中序遍歷時的情況相同。

三.后序遍歷

后續(xù)遍歷稍顯復(fù)雜，需要建立一個臨時節(jié)點 dump ，令其左孩子是 root。并且還需要一個子過程，就是倒序輸出某兩個節(jié)點之間路徑上的各個節(jié)點。

步驟：

當(dāng)前節(jié)點設(shè)置為臨時節(jié)點 dump。

  1. 初始化當(dāng)前節(jié)點 cur 為 root 節(jié)點.

  2. 如果 cur 沒有左孩子，則將其右孩子作為當(dāng)前節(jié)點,即 cur = cur->right 。

  3. 如果 cur 有左孩子，在當(dāng)前節(jié)點 cur 的左子樹中找到當(dāng)前節(jié)點 cur 在中序遍歷下的前驅(qū)節(jié)點。

    a) 如果前驅(qū)節(jié)點的右孩子為空，將它的右孩子設(shè)置為當(dāng)前節(jié)點。當(dāng)前節(jié)點更新為當(dāng)前節(jié)點的左孩子。

    b) 如果前驅(qū)節(jié)點的右孩子為當(dāng)前節(jié)點，將它的右孩子重新設(shè)為空。 倒序輸出從當(dāng)前節(jié)點的左孩子到該前驅(qū)節(jié)點這條路徑上的所有節(jié)點 。當(dāng)前節(jié)點更新為當(dāng)前節(jié)點的右孩子。

  4. 重復(fù)以上2、3直到當(dāng)前節(jié)點為空。

后序遍歷
/**
 * @brief 將指針反轉(zhuǎn)
 * @param[in] from 反轉(zhuǎn)路徑的起點.
 * @param[in] to 反轉(zhuǎn)路徑的終點。
 */
static void 
reverse(bt_node_t *from, bt_node_t *to) 
{
 bt_node_t *x = from, *y = from->right, *z;
 if (from == to) return;
 /* 需要注意的是,這里并不是完全的路徑反轉(zhuǎn),但是用在這里足夠了.所以這里只是一個局部函數(shù). */
 while (x != to) {
     z = y->right;
     y->right = x;
     x = y;
     y = z;
 }
}

/**
 * @brief 訪問逆轉(zhuǎn)后的路徑上的所有節(jié)點.
 * @param[in] from 需要訪問路徑的起點,也就是應(yīng)該最后一個訪問的節(jié)點.
 * @param[in] to 需要訪問路徑的終點,也是第一個應(yīng)該被訪問的節(jié)點.
 */
static void
visit_reverse(bt_node_t* from, bt_node_t *to, int (*visit)(bt_node_t *))
{
 bt_node_t *p = to;
 reverse(from, to);
 while (1) {
     visit(p);
     if (p == from)
         break;
     p = p->right;
 }
 reverse(to, from);
}

/**
 * @brief 使用Morrris算法進(jìn)行后序遍歷.
 * @param[in] root 根節(jié)點
 * @param[in] visit 訪問函數(shù)
 */
void
post_order_morris(bt_node_t *root, int(*visit)(bt_node_t *))
{
 bt_node_t dummy = { 0, NULL, NULL };
 bt_node_t *cur, *prev = NULL;

 dummy.left = root;
 cur = &dummy;
 while (cur != NULL) {
     if (cur->left == NULL) {
         prev = cur;
         cur = cur->right;
     }
     else {
         bt_node_t *node = cur->left;
         while (node->right != NULL && node->right != cur)
             node = node->right;

         if (node->right == NULL) { /* 尚未線索化,立即線索化 */
             node->right = cur;
             prev = cur;
             cur = cur->left;
         }
         else {
             /* visit_reverse其實有一個小問題,那就是prev->right在訪問的時候會別修改 */
             visit_reverse(cur->left, prev, visit); 
             prev->right = NULL;
             prev = cur;
             cur = cur->right;
         }
     }
 }
}

復(fù)雜度分析

空間復(fù)雜度同樣是 O(1) ；時間復(fù)雜度也是 O(n) ，倒序輸出過程只不過是加大了常數(shù)系數(shù)。

四. 代碼

#include <stdio.h>
#include <stdlib.h>

typedef int elem_t;

/**
 * @struct
 * @brief 二叉樹節(jié)點.
 */
typedef struct bt_node_t {
 elem_t elem;
 struct bt_node_t *left;
 struct bt_node_t *right;
};

/**
 * @brief 使用Morrris算法進(jìn)行中序遍歷.
 * @param[in] root 根節(jié)點
 * @param[in] visit 訪問函數(shù)
 */
void 
in_order_mirrors(bt_node_t *root, int(*visit)(bt_node_t *))
{
 bt_node_t *cur;
 cur = root;
 while (cur != NULL) {
     if (cur->left == NULL) {
         visit(cur);
         cur = cur->right;   /* 將右孩子作為當(dāng)前節(jié)點 */
     }
     else {
         /* 查找cur節(jié)點的前驅(qū)節(jié)點 */
         bt_node_t *node = cur->left;
         while (node->right != NULL && node->right != cur)
             node = node->right;

         if (node->right == NULL) { /* 還沒有線索化，則建立線索 */
             node->right = cur;
             cur = cur->left;
         }
         else { /* 如果已經(jīng)線索化了，則訪問節(jié)點，并刪除線索 */
             visit(cur);
             node->right = NULL;
             cur = cur->right;
         }
     }
 }
}

/**
 * @brief 使用Morrris算法先序遍歷
 * @param[in] root 根節(jié)點
 * @param[in] visit 訪問函數(shù)
 */
void
pre_order_morris(bt_node_t *root, int(*visit)(bt_node_t *))
{
 bt_node_t *cur;

 cur = root;
 while (cur != NULL) {
     if (cur->left == NULL) {
         visit(cur);
         cur = cur->right;
     }
     else {
         /* 查找前驅(qū) */
         bt_node_t *node = cur->left;
         while (node->right != NULL && node->right != cur)
             node = node->right;

         if (node->right == NULL) {
             visit(cur);
             node->right = cur;
             cur = cur->left;
         }
         else { /* 已經(jīng)線索化了，則刪除線索 */
             node->right = NULL;
             cur = cur->right;
         }
     }
 }
}

/**
 * @brief 將指針反轉(zhuǎn)
 * @param[in] from 反轉(zhuǎn)路徑的起點.
 * @param[in] to 反轉(zhuǎn)路徑的終點。
 */
static void 
reverse(bt_node_t *from, bt_node_t *to) 
{
 bt_node_t *x = from, *y = from->right, *z;
 if (from == to) return;
 /* 需要注意的是,這里并不是完全的路徑反轉(zhuǎn),但是用在這里足夠了.所以這里只是一個局部函數(shù). */
 while (x != to) {
     z = y->right;
     y->right = x;
     x = y;
     y = z;
 }
}

/**
 * @brief 訪問逆轉(zhuǎn)后的路徑上的所有節(jié)點.
 * @param[in] from 需要訪問路徑的起點,也就是應(yīng)該最后一個訪問的節(jié)點.
 * @param[in] to 需要訪問路徑的終點,也是第一個應(yīng)該被訪問的節(jié)點.
 */
static void
visit_reverse(bt_node_t* from, bt_node_t *to, int (*visit)(bt_node_t *))
{
 bt_node_t *p = to;
 reverse(from, to);
 while (1) {
     visit(p);
     if (p == from)
         break;
     p = p->right;
 }
 reverse(to, from);
}

/**
 * @brief 使用Morrris算法進(jìn)行后序遍歷.
 * @param[in] root 根節(jié)點
 * @param[in] visit 訪問函數(shù)
 */
void
post_order_morris(bt_node_t *root, int(*visit)(bt_node_t *))
{
 bt_node_t dummy = { 0, NULL, NULL };
 bt_node_t *cur, *prev = NULL;

 dummy.left = root;
 cur = &dummy;
 while (cur != NULL) {
     if (cur->left == NULL) {
         prev = cur;
         cur = cur->right;
     }
     else {
         bt_node_t *node = cur->left;
         while (node->right != NULL && node->right != cur)
             node = node->right;

         if (node->right == NULL) { /* 尚未線索化,立即線索化 */
             node->right = cur;
             prev = cur;
             cur = cur->left;
         }
         else {
             /* visit_reverse其實有一個小問題,那就是prev->right在訪問的時候會別修改 */
             visit_reverse(cur->left, prev, visit); 
             prev->right = NULL;
             prev = cur;
             cur = cur->right;
         }
     }
 }
}

/**
 * @breif 分配一個新節(jié)點.
 * @param[in] e 新節(jié)點的數(shù)據(jù)
 */
bt_node_t* new_node(int e)
{
 bt_node_t* node = (bt_node_t *)malloc(sizeof(bt_node_t));
 node->elem = e;
 node->left = NULL;
 node->right = NULL;
 return node;
}

static int
print(bt_node_t *node)
{
 printf(" %d", node->elem);
 return 0;
}

void 
test_01()
{
 bt_node_t n1, n2, n3, n4;
 n1.elem = 1, n1.left = NULL, n1.right = &n2;
 n2.elem = 2, n2.left = NULL, n2.right = &n3;
 n3.elem = 3, n3.left = NULL, n3.right = &n4;
 n4.elem = 4, n4.left = NULL, n4.right = NULL;
 reverse(&n1, &n4);
 reverse(&n4, &n1);
}

int main()
{
 bt_node_t *n1 = new_node(1);
 bt_node_t *n2 = new_node(2);
 bt_node_t *n3 = new_node(3);
 bt_node_t *n4 = new_node(4);
 bt_node_t *n5 = new_node(5);
 bt_node_t *n6 = new_node(6);
 bt_node_t *n7 = new_node(7);
 bt_node_t *n8 = new_node(8);
 bt_node_t *n9 = new_node(9);

 n6->left = n2; n6->right = n7;
 n2->left = n1; n2->right = n4;
 n1->left = NULL; n1->right = NULL;
 n4->left = n3; n4->right = n5;
 n3->left = n3->right = NULL;
 n5->left = n5->right = NULL;
 n7->left = NULL; n7->right = n9;
 n9->left = n8; n9->right = NULL;
 n8->left = n8->right = NULL;
 
 pre_order_morris(n6, print);
 printf("\n");
 
 in_order_mirrors(n6, print);
 printf("\n");
 
 post_order_morris(n6, print);
 printf("\n");
 getchar();
}

?

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容