Morris 二叉树遍历算法(C语言描述)

对于二叉树的遍历,在数据结构中介绍有三种遍历方式:前序遍历,中序遍历和后序遍历. 这三种遍历方式通常采用递归或者迭代方式实现.
递归实现或者迭代实现都是时间复杂度为O(n)的算法,并且在遍历过程中需要用到堆栈保存信息,它们的空间复杂度也都是O(n).
下面要介绍的Morris二叉树遍历算法是时间复杂度为O(n),空间复杂度为O(1)的遍历算法,它也有前序遍历,中序遍历和后续遍历三种遍历顺序

Morris 中序遍历算法

算法的简要概述如下:

• 指定cur指针 初始指向 root节点
• 1.当cur指针的左子节点为NULL时,说明在其左子树内没有前驱节点,访问cur指针中的元素,cur指针指向cur指针的右节点.
• 2.当cur指针的左子节点不为NULL时,用指针指向cur左子树的最右节点
  2.1当最右节点的右节点为NULL时,将其指向cur,cur指向cur的左节点
  2.2当最右节点的右节点不为NULL时,将其置NULL,访问cur指针中元素,cur指向cur的右节点.
• 重复 1 , 2步骤,直到cur指针为NULL

算法执行步骤如图所示

morris 中序遍历

算法实现:

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

void Morris_LDR(struct TreeNode* root) {
    struct TreeNode *cur = root;
    while (cur != NULL) {
        if (cur->left == NULL) {
           printf("now :%d \n",cur->val);
            cur = cur->right;
        } else {
            struct TreeNode *temp = cur->left;
            while (temp->right != NULL && temp->right != cur) {
                temp = temp->right;
            }
            
            if (temp->right == NULL) {
                temp->right = cur;
                cur = cur->left;
            } else {
                temp->right = NULL;
                printf("now :%d \n",cur->val);
                cur = cur->right;
            }
        }
    }
}

Morris 前序遍历算法

与递归算法相似,Morris 前序遍历与 Morris中序遍历算法在骨架上一致,只是调整了输出数据的位置.
算法描述

• 指定cur指针 初始指向 root节点
• 1.当cur指针的左子节点为NULL时,说明在其左子树内没有前驱节点,访问cur指针中的元素,cur指针指向cur指针的右节点.
• 2.当cur指针的左子节点不为NULL时,用指针指向cur左子树的最右节点
  2.1当最右节点的右节点为NULL时,将其指向cur,访问cur指针中元素,cur指向cur的左节点
  2.2当最右节点的右节点不为NULL时,将其置NULL,cur指向cur的右节点.
• 重复 1 , 2步骤,直到cur指针为NULL

算法执行图示

mirros 前序遍历

算法实现:

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

void Morris_DLR(struct TreeNode* root) {
    struct TreeNode *cur = root;
    while (cur != NULL) {
        if (cur->left == NULL) {
            printf("now :%d \n",cur->val);
            cur = cur->right;
        } else {
            struct TreeNode *temp = cur->left;
            while (temp->right != NULL && temp->right != cur) {
                temp = temp->right;
            }
            
            if (temp->right == NULL) {
                temp->right = cur;
                printf("-now :%d \n",cur->val);
                cur = cur->left;
            } else {
                temp->right = NULL;
                cur = cur->right;
            }
        }
    }
}

Mirros 后序遍历

Mirros 后序遍历比较麻烦,需要创建额外的根节点辅助遍历过程,还要有一个过程来倒序访问元素.

算法描述

• 创建head节点,使head节点是head节点的左节点指向root节点.
• 创建 cur指针,使cur指针指向head节点.
• 1.当cur指针的左节点为NULL时,使cur指针指向cur指针的右节点.
• 2.当cur指针的左节点不为NULL时,找到cur指针的左节点的最右节点(中序遍历时的前驱节点).
  2.1当最右节点的右节点为NULL时,使最右节点的右节点指向cur指针,
  使cur指针指向cur指针的左子节点.
  2.2 当最右节点的右节点不为NULL时,使最右节点的右节点指向NULL, 并倒叙访问从cur指针的左节点到最右节点的所有子节点,使cur指针指向cur指针的右子节点.
• 重复1 , 2过程,直到 cur指针指向NULL.

算法执行图示(图中的虚线框表示辅助的头结点)

mirros 后序遍历

算法实现

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

void Morris_LRD(struct TreeNode *root) {
    struct TreeNode *head = (struct TreeNode *)calloc(1, sizeof(struct TreeNode));
    struct TreeNode *cur = head;
    head->left = root;
    while (cur != NULL) {
        if (cur -> left == NULL) {
            cur = cur -> right;
        } else {
            struct TreeNode *temp = cur -> left;
            while (temp->right != NULL && temp-> right != cur) {
                temp = temp -> right;
            }
            
            if (temp -> right == NULL){
                temp -> right = cur;
                cur = cur -> left;
            } else { // (temp -> right == cur
                temp -> right = NULL;
                
                struct TreeNode *index = cur->left;
                printf("reverse ( ");
                while (index != NULL) {
                    printf("%d ",index->val);
                    index = index->right;
                }
                printf(" )\n");
                cur = cur -> right;
            }
            
        }
    }
  head->left = NULL;
  free(head);
}

---

参考链接