对于二叉树的遍历,在数据结构中介绍有三种遍历方式:前序遍历,中序遍历和后序遍历. 这三种遍历方式通常采用递归或者迭代方式实现.
递归实现或者迭代实现都是时间复杂度为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);
}
