對(duì)于二叉樹(shù)的遍歷,在數(shù)據(jù)結(jié)構(gòu)中介紹有三種遍歷方式:前序遍歷,中序遍歷和后序遍歷. 這三種遍歷方式通常采用遞歸或者迭代方式實(shí)現(xiàn).
遞歸實(shí)現(xiàn)或者迭代實(shí)現(xiàn)都是時(shí)間復(fù)雜度為O(n)的算法,并且在遍歷過(guò)程中需要用到堆棧保存信息,它們的空間復(fù)雜度也都是O(n).
下面要介紹的Morris二叉樹(shù)遍歷算法是時(shí)間復(fù)雜度為O(n),空間復(fù)雜度為O(1)的遍歷算法,它也有前序遍歷,中序遍歷和后續(xù)遍歷三種遍歷順序
Morris 中序遍歷算法
算法的簡(jiǎn)要概述如下:
- 指定
cur指針初始指向root節(jié)點(diǎn) - 1.當(dāng)
cur指針的左子節(jié)點(diǎn)為NULL時(shí),說(shuō)明在其左子樹(shù)內(nèi)沒(méi)有前驅(qū)節(jié)點(diǎn),訪問(wèn)cur指針中的元素,cur指針指向cur指針的右節(jié)點(diǎn). - 2.當(dāng)
cur指針的左子節(jié)點(diǎn)不為NULL時(shí),用指針指向cur左子樹(shù)的最右節(jié)點(diǎn)
2.1當(dāng)最右節(jié)點(diǎn)的右節(jié)點(diǎn)為NULL時(shí),將其指向cur,cur指向cur的左節(jié)點(diǎn)
2.2當(dāng)最右節(jié)點(diǎn)的右節(jié)點(diǎn)不為NULL時(shí),將其置NULL,訪問(wèn)cur指針中元素,cur指向cur的右節(jié)點(diǎn). - 重復(fù) 1 , 2步驟,直到
cur指針為NULL
算法執(zhí)行步驟如圖所示
morris 中序遍歷
算法實(shí)現(xiàn):
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中序遍歷算法在骨架上一致,只是調(diào)整了輸出數(shù)據(jù)的位置.
算法描述
- 指定
cur指針初始指向root節(jié)點(diǎn) - 1.當(dāng)
cur指針的左子節(jié)點(diǎn)為NULL時(shí),說(shuō)明在其左子樹(shù)內(nèi)沒(méi)有前驅(qū)節(jié)點(diǎn),訪問(wèn)cur指針中的元素,cur指針指向cur指針的右節(jié)點(diǎn). - 2.當(dāng)
cur指針的左子節(jié)點(diǎn)不為NULL時(shí),用指針指向cur左子樹(shù)的最右節(jié)點(diǎn)
2.1當(dāng)最右節(jié)點(diǎn)的右節(jié)點(diǎn)為NULL時(shí),將其指向cur,訪問(wèn)cur指針中元素,cur指向cur的左節(jié)點(diǎn)
2.2當(dāng)最右節(jié)點(diǎn)的右節(jié)點(diǎn)不為NULL時(shí),將其置NULL,cur指向cur的右節(jié)點(diǎn). - 重復(fù) 1 , 2步驟,直到
cur指針為NULL
算法執(zhí)行圖示
mirros 前序遍歷
算法實(shí)現(xiàn):
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 后序遍歷比較麻煩,需要?jiǎng)?chuàng)建額外的根節(jié)點(diǎn)輔助遍歷過(guò)程,還要有一個(gè)過(guò)程來(lái)倒序訪問(wèn)元素.
算法描述
- 創(chuàng)建
head節(jié)點(diǎn),使head節(jié)點(diǎn)是head節(jié)點(diǎn)的左節(jié)點(diǎn)指向root節(jié)點(diǎn). - 創(chuàng)建
cur指針,使cur指針指向head節(jié)點(diǎn). - 1.當(dāng)
cur指針的左節(jié)點(diǎn)為NULL時(shí),使cur指針指向cur指針的右節(jié)點(diǎn). - 2.當(dāng)
cur指針的左節(jié)點(diǎn)不為NULL時(shí),找到cur指針的左節(jié)點(diǎn)的最右節(jié)點(diǎn)(中序遍歷時(shí)的前驅(qū)節(jié)點(diǎn)).
2.1當(dāng)最右節(jié)點(diǎn)的右節(jié)點(diǎn)為NULL時(shí),使最右節(jié)點(diǎn)的右節(jié)點(diǎn)指向cur指針,
使cur指針指向cur指針的左子節(jié)點(diǎn).
2.2 當(dāng)最右節(jié)點(diǎn)的右節(jié)點(diǎn)不為NULL時(shí),使最右節(jié)點(diǎn)的右節(jié)點(diǎn)指向NULL, 并倒敘訪問(wèn)從cur指針的左節(jié)點(diǎn)到最右節(jié)點(diǎn)的所有子節(jié)點(diǎn),使cur指針指向cur指針的右子節(jié)點(diǎn). - 重復(fù)1 , 2過(guò)程,直到
cur指針指向NULL.
算法執(zhí)行圖示(圖中的虛線框表示輔助的頭結(jié)點(diǎn))
mirros 后序遍歷
算法實(shí)現(xiàn)
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);
}
