Binary tree god level traversal: Morris traversal

---

1. Create a binary tree

typedef struct BiTNode{
    
    int data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

// Create a binary tree in the previous order 
void createBiTree(BiTree *T){
    
    int value;
    cin>>value;
    if (value == 0)
        *T = NULL;
    else{
    
        *T = (BiTree)malloc(sizeof(BiTNode));
        if(!*T)
            exit(OVERFLOW);
        (*T)->data = value;
        createBiTree(&(*T)->lchild);
        createBiTree(&(*T)->rchild);
    }
}

1 2 4 0 0 5 0 0 3 6 0 0 7 0 0 Building a binary tree

---

2. Regular traversal

// The former sequence traversal 
void PreOrderTraverse(BiTree T){
    
    if(T==NULL)
        return;
    cout<<T->data<<" ";
    PreOrderTraverse(T->lchild);
    PreOrderTraverse(T->rchild);
}

// In the sequence traversal 
void InOrderTraverse(BiTree T){
    
    if(T==NULL)
        return;
    InOrderTraverse(T->lchild);
    cout<<T->data<<" ";
    InOrderTraverse(T->rchild);
}

// After the sequence traversal 
void PostOrderTraverse(BiTree T){
    
    if(T==NULL)
        return;
    PostOrderTraverse(T->lchild);
    PostOrderTraverse(T->rchild);
    cout<<T->data<<" ";
}

// test

int main(){
    
    BiTree T;
    createBiTree(&T);
    PreOrderTraverse(T); // 1 2 4 5 3 6 7
    cout<<endl;
    InOrderTraverse(T); // 4 2 5 1 6 3 7
    cout<<endl;
    PostOrderTraverse(T); // 4 5 2 6 7 3 1
    return 0;
}

---

3. Morris Traverse

• get Morris The process of executing a sequence ：
  1. Remember that the current node is current（ initial current = head）, If current There is no left subtree （current.left = null）, be current To the right （current = current.right）,
  2. When current There's a Zuozi tree （current.left != null）, find current The rightmost node of the left subtree （ Write it down as mostRight）,
     • If mostRight.right = null, Will mostRight Of right Pointer to current, namely mostRight.right = current, here current Move to the left ,
     • If mostRight.right = current, Will mostRight Of right Pointer to a null, namely mostRight.right = null, here current To the right ,
  3. current = null when , Run terminated .
  4. Record every time current The node of finally gets Morris order .

Example demonstration ：

---

// obtain Morris Sequence

void morris(BiTree T){
    
    if(T==NULL)
        return;
    BiTree cur = T; //  initialization cur=T Head node 
    BiTree mostRight = NULL; //  initialization mostRight=NULL
    while(cur != NULL){
    
        mostRight = cur->lchild; //mostRight=cur The left child 
        cout<<cur->data<<" "; //  Print Morris Sequence 
        if(mostRight!=NULL){
    
            while(mostRight->rchild!=NULL && mostRight->rchild!=cur){
    
                mostRight = mostRight->rchild; //  take mostRight Move to cur The rightmost node of the left child 
            }
            if(mostRight->rchild == NULL){
     // mostRight The right node of NULL
                mostRight->rchild = cur; //  Point to cur
                cur = cur->lchild; // cur Move left   turn to continue Go straight to the next cycle 
                continue;
            } else {
    
                mostRight->rchild = NULL; //  otherwise mostRight Set up NULL
            }
        }
        cur = cur->rchild; //  There is no left subtree or execution mostRight->rchild=NULL After execution 
    }
}

• Morris The characteristics of order ：
  1. Node has no left subtree , It's in Morris There is only one occurrence in the sequence ,
  2. The node has a left subtree , It's in Morris There are two times in the sequence .

• below , According to what you get Morris First order 、 Middle preface 、 After the sequence traversal ：
  1. The first sequence traversal ： stay Morris Print the first occurrence in the sequence , Don't print the second time ,
  2. In the sequence traversal ： stay Morris Print once in the sequence , Appear twice in the second print ,
  3. After the sequence traversal ： stay Morris Nodes that appear twice in the sequence and appear the second time are processed ： Print the right boundary of the left subtree of the node in reverse order , Finally, print the right boundary of the binary tree in reverse order .

//Morris The first sequence traversal ：

void morrisPre(BiTree T){
    
    if(T==NULL)
        return;
    BiTree cur = T;
    BiTree mostRight = NULL;
    while(cur != NULL){
    
        mostRight = cur->lchild;
        if(mostRight!=NULL){
     //  The left subtree is not NULL, necessarily Morris There are two nodes in the sequence 
            while(mostRight->rchild!=NULL && mostRight->rchild!=cur){
    
                mostRight = mostRight->rchild;
            }
            if(mostRight->rchild == NULL){
     // Morris The first occurrence of two nodes in the sequence data Print 
                cout<<cur->data<<" ";
                mostRight->rchild = cur;
                cur = cur->lchild;
                continue;
            } else {
    
                mostRight->rchild = NULL;
            }
        } else{
     // Morris There can only be one case in the sequence data Print 
            cout<<cur->data<<" ";
        }
        cur = cur->rchild;
    }
}

//Morris In the sequence traversal ：

void morrisIn(BiTree T){
    
    if(T==NULL)
        return;
    BiTree cur = T;
    BiTree mostRight = NULL;
    while(cur != NULL){
    
        mostRight = cur->lchild;
        if(mostRight!=NULL){
     //  The left subtree is not NULL, necessarily Morris There are two nodes in the sequence 
            while(mostRight->rchild!=NULL && mostRight->rchild!=cur){
    
                mostRight = mostRight->rchild;
            }
            if(mostRight->rchild == NULL){
     // Morris Two nodes in the sequence appear for the first time 
                mostRight->rchild = cur;
                cur = cur->lchild;
                continue;
            } else {
     //  The second time 
                mostRight->rchild = NULL;
            }
        }
        cout<<cur->data<<" "; //  Print the middle order sequence node 
        cur = cur->rchild;
    }
}

---

//Morris After the sequence traversal ：

• Morris order ：1 2 4 2 5 1 3 6 3 7
• In the second occurrence 2 When printing in reverse order 2 The right boundary of the left subtree of is 4,
• In the second occurrence 1 When printing in reverse order 1 The right boundary of the left subtree of is 5,2,
• In the second occurrence 2 When printing in reverse order 3 The right boundary of the left subtree of is 6,
• Finally, the right boundary of the binary tree is printed in reverse order 7,3,1.
• The result of post order traversal is ：4,5,2,6,7,3,1.

To ensure that the space complexity is O(1), When printing the right boundary in reverse order , The right pointer of the boundary node must be adjusted .

//  from now Start , Consider only the right pointer , Use it as a single linked list next, Reverse the single linked list , Returns the last node 
BiTree reverseEdge(BiTree T){
    
    BiTree pre = NULL;
    BiTree next = NULL;
    while(T!=NULL){
    
        next = T->rchild;
        T->rchild = pre;
        pre = T;
        T = next;
    }
    return pre;
}

//  With T Node headed tree , Print the right boundary of the tree in reverse order 
void printEdge(BiTree T){
    
    BiTree tail = reverseEdge(T);
    BiTree cur = tail;
    while(cur!=NULL){
    
        cout<<cur->data<<" ";
        cur = cur->rchild;
    }
    reverseEdge(tail);
}

// Subsequent sequence 
void morrisPost(BiTree T){
    
    if(T==NULL)
        return;
    BiTree cur = T;
    BiTree mostRight = NULL;
    while(cur != NULL){
    
        mostRight = cur->lchild;
        if(mostRight!=NULL){
     //  The left subtree is not NULL, necessarily Morris There are two nodes in the sequence 
            while(mostRight->rchild!=NULL && mostRight->rchild!=cur){
    
                mostRight = mostRight->rchild;
            }
            if(mostRight->rchild == NULL){
     // Morris Two nodes in the sequence appear for the first time 
                mostRight->rchild = cur;
                cur = cur->lchild;
                continue;
            } else {
     //  Two times and the second time 
                mostRight->rchild = NULL;
                printEdge(cur->lchild); //  To deal with 
            }
        }
        cur = cur->rchild;
    }
    //  After the end , Print the right boundary of the binary tree in reverse order 
    printEdge(T);
}

---

4. Complexity of time and space

---

Time complexity ：O(n)
Spatial complexity ：O(1)

---

——————END-2022-06-26——————