Morris order traversal of a binary tree

This article is purely based on the notes I have taken recently. If there is any infringement in the relevant information or documents, please contact me. Of course, if there is something wrong in the article or there is a better way, please feel free to tell me.

Morris order traversal of a binary tree

1. The process of Morris order

Refer to Zuoshen’s video screen: (starting at 14:34)

Link

2. Code

void Mid_Morris(TreeNode* root) {<!-- -->

        TreeNode* Cur = root; //Current node
        TreeNode* Right_Most = nullptr;//The rightmost node of the left tree

        //This tree is an empty binary tree
        if (root == nullptr) {<!-- -->

            return;
        }
        //The sign of the end of the loop: it is found that Cur is nullptr. If there are still nodes, the right node will be changed first. points to the previous node
        while (Cur) {<!-- -->
            //Morris order printing
            //cout << Cur->val << '\t';

            //To find the rightmost node of the left tree, you must first find the left tree
            Right_Most = Cur->left;

            //Indicates that there is a left subtree at this time
            if (Right_Most != nullptr) {<!-- -->
                //Find the rightmost node
                while ((Right_Most->right != nullptr) & amp; & amp; (Right_Most->right != Cur)) {<!-- -->
                    Right_Most = Right_Most->right;
                }
                //Case 1: Find the rightmost node and exit: you need to point the pointer to the current Cur
                if (Right_Most->right == nullptr)
                {<!-- -->
                    Right_Most->right = Cur;
                }
                //Case 2: Cur is found, indicating that the node has been changed once. The node needs to be reset to nullptr, and the current Cur = Cur->right; and use continue to end the cycle. In this way, the following sentence Cur = Cur->left will not be executed.
                else if (Right_Most->right == Cur)//The second time you come to the node
                {<!-- -->
                    Right_Most->right = nullptr;
                    Cur = Cur->right;
                    continue;
                }
                Cur = Cur->left;
            }
            //There is no left tree, directly find the right tree
            else {<!-- -->
                Cur = Cur->right;
            }
                
        }
    }

3. Morris traverses the binary tree

3.1 In-order traversal

Morris algorithm in-order traversal of a binary tree: If there is a left tree, it will appear twice in Morris order. The key to in-order traversal is that if it appears twice, print it the second time. If it only appears once, print it directly.

 void Mid_Morris(TreeNode* root) {<!-- -->

        TreeNode* Cur = root; //Current node
        TreeNode* Right_Most = nullptr;//The rightmost node of the left tree

        //This tree is an empty binary tree
        if (root == nullptr) {<!-- -->

            return;
        }
        //The sign of the end of the loop: it is found that Cur is nullptr. If there are still nodes, the right node will be changed first. points to the previous node
        while (Cur) {<!-- -->
            //Morris order printing
            //cout << Cur->val << '\t';

            //To find the rightmost node of the left tree, you must first find the left tree
            Right_Most = Cur->left;

            //Indicates that there is a left subtree at this time
            if (Right_Most != nullptr) {<!-- -->
                //Find the rightmost node
                while ((Right_Most->right != nullptr) & amp; & amp; (Right_Most->right != Cur)) {<!-- -->
                    Right_Most = Right_Most->right;
                }
                //Case 1: Find the rightmost node and exit: you need to point the pointer to the current Cur
                if (Right_Most->right == nullptr)
                {<!-- -->
                    Right_Most->right = Cur;
                }
                //Case 2: Cur is found, indicating that the node has been changed once. The node needs to be reset to nullptr, and the current Cur = Cur->right; and use continue to end the cycle. In this way, the following sentence Cur = Cur->left will not be executed.
                else if (Right_Most->right == Cur)//The second time you come to the node
                {<!-- -->
                    cout << Cur->val << '\t';
                    Right_Most->right = nullptr;
                    Cur = Cur->right;
                    continue;
                }
                Cur = Cur->left;
            }
            //There is no left tree, directly find the right tree
            else {<!-- -->

                cout << Cur->val << '\t';
                Cur = Cur->right;
                
            }
                
        }
    }

3.2 Preorder traversal

Morris algorithm pre-order traversal of a binary tree: If there is a left tree, it will appear twice in Morris order. However, the key to pre-order traversal is that if it appears twice, it will be printed directly after the first occurrence.

void Pre_Morris(TreeNode* root) {
TreeNode* Cur = root; //Current node
   TreeNode* Right_Most = nullptr;//The rightmost node of the left tree

   //This tree is an empty binary tree
   if (root == nullptr) {

       return;
   }
   //The sign of the end of the loop: it is found that Cur is nullptr. If there are still nodes, the right node will be changed first. points to the previous node
   while (Cur) {
       //Morris order printing
       //cout << Cur->val << '\t';

       //To find the rightmost node of the left tree, you must first find the left tree
       Right_Most = Cur->left;

       //Indicates that there is a left subtree at this time
       if (Right_Most != nullptr) {
           //Find the rightmost node. Attention please! ! ! You must first determine whether Right_Most is NULL before you can access its left and right nodes.
           while ((Right_Most->right != nullptr) & amp; & amp; (Right_Most->right != Cur)) {
               Right_Most = Right_Most->right;
           }
           //Case 1: Find the rightmost node and exit: you need to point the pointer to the current Cur
           if (Right_Most->right == nullptr)
           {
               cout << Cur->val << '\t';
               Right_Most->right = Cur;
           }
           //Case 2: Cur is found, indicating that the node has been changed once, and the node needs to be reset to nullptr, and the current Cur = Cur->right;\
           And use continue to end this loop. In this way, the following sentence Cur = Cur->left will not be executed.
           else if (Right_Most->right == Cur)//The second time you come to the node
           {
               Right_Most->right = nullptr;
               Cur = Cur->right;
               continue;
           }
           Cur = Cur->left;
       }
       //There is no left tree, directly find the right tree
       else {

           cout << Cur->val << '\t';
           Cur = Cur->right;

       }

   }
}

3.3 Post-order traversal

flip linked list
Why is the return value a pointer? Because, root needs to point to the head node, otherwise it will be invalid in memory. Because if there is no head node, it will not be found where the linked list is after the flip is completed. Of course, you don’t need to use it if you know the address of the last element, that is, the head node after flipping.

TreeNode* Reverse_List(TreeNode* root) {
//Record the next node address
   TreeNode* pre = root;
   //Record the address of the next node in the linked list
   TreeNode* cur = nullptr;
   //Empty linked list
   if (root == nullptr)
   {
       return NULL;
   }

   //cur grabs the address of the next node
   cur = root->right;

   //At this time, you can set pre->right to nullptr, and the first one needs to be set to nullptr.
   root->right = nullptr;
   while (cur != nullptr) {

       pre = cur->right;
       cur->right = root;
       root = cur;
       cur = pre;
   }
   return root;
}

Morris algorithm post-order traversal of a binary tree: if there is a left tree, it will appear twice in Morris order, and,
The key to post-order traversal: print the right boundary in reverse when coming for the second time. Note that the current node is not printed. Whether to print boundaries or reverse printing
The last step is to print the right border of the entire tree.

void Last_Morris(TreeNode* root) {<!-- -->

       TreeNode* Cur = root; //Current node
       TreeNode* Right_Most = nullptr;//The rightmost node of the left tree
       TreeNode* New = root; //Current node
       TreeNode* New1 = root; //Current node

       //This tree is an empty binary tree
       if (root == nullptr) {<!-- -->

           return;
       }
       //The sign of the end of the loop: it is found that Cur is nullptr. If there are still nodes, the right node will be changed first. points to the previous node
       while (Cur) {<!-- -->
           //Morris order printing
           //cout << Cur->val << '\t';

           //To find the rightmost node of the left tree, you must first find the left tree
           Right_Most = Cur->left;

           //Indicates that there is a left subtree at this time
           if (Right_Most != nullptr) {<!-- -->
               //Find the rightmost node
               while ((Right_Most->right != nullptr) & amp; & amp; (Right_Most->right != Cur)) {<!-- -->
                   Right_Most = Right_Most->right;
               }
               //Case 1: Find the rightmost node and exit: you need to point the pointer to the current Cur
               if (Right_Most->right == nullptr)
               {<!-- -->
                   Right_Most->right = Cur;
               }
               //Case 2: Cur is found, indicating that the node has been changed once, and the node needs to be reset to nullptr, and the current Cur = Cur->right;\
               And use continue to end this loop. In this way, the following sentence Cur = Cur->left will not be executed.
               else if (Right_Most->right == Cur)//The second time you come to the node
               {<!-- -->
                   Right_Most->right = nullptr;
                   //Flip the linked list at this time
                   New = Reverse_List(Cur->left);
                   New1 = New;//Save the linked list after flipping
                   while(New)
                   {<!-- -->
                       cout << New->val << '\t';
                       New = New->right;
                   }
                   //flip back
                   New1 = Reverse_List(New1);
                   Cur = Cur->right;
                   continue;
               }
               Cur = Cur->left;
           }
           //There is no left tree, directly find the right tree
           else {<!-- -->

               Cur = Cur->right;

           }

       }
       //Finally, print the right boundary of the entire tree separately.
       New = Reverse_List(root);
       New1 = New;
       while (New)
       {<!-- -->
           cout << New->val << '\t';
           New = New->right;
       }
       //flip back
       New1 = Reverse_List(New1);
}

Binary tree traversal method

1. Recursion

//In-order traversal

void Midorder(TreeNode* root)
{<!-- -->
    //Traverse to the last node
    if (NULL == root)
        return;
    Midorder(root->left);
    cout<< root->val;
    Midorder(root->right);
}

//preorder traversal

void Preorder(TreeNode* root)
{
    if (NULL == root)
        return;
    cout << root->val<<'\t';
    Preorder(root->left);
    Preorder(root->right);
}

//post-order traversal

void Lastorder(TreeNode* root)
{
    if (NULL == root)
        return;
    Lastorder(root->left);
    Lastorder(root->right);
    cout << root->val << '\t';
}

2. How to use stack

inorder traversal

vector<int> inorderTraversal(TreeNode* root) {
        
        int flag = -1; //Record how many elements there are in the current stack. In fact, there is no need to maintain such a variable in C++. You can use arr.empty() to determine whether it is empty.
        TreeNode* left = root;
        TreeNode* pMove = root;
        TreeNode* stack[10] = { root };//A stack space created manually by yourself. But there is stack<TreeNode*> stk//automatically create a stack space
        vector<int> arr = {};
        if (root == NULL)
            return arr;
        //Find the leftmost number
        do{
            while (left != NULL)//Use left instead of left->left, because if it was NULL at the beginning. Such access is invalid! ! !
            {
                stack[ + + flag] = left;
                left = left->left;
            }
            pMove = stack[flag];
            cout << pMove->val<<'\t';
            arr.push_back(pMove->val);
            flag--;
            left = pMove->right;
            if (left != NULL)//Duplicate the while statement above. Use do...while plus while. Indicates that both must be satisfied. But if you only use one while. while((left != NULL)||(flag ! =-1)) will do.
            {
                stack[ + + flag] = left;
                left = left->left;
            }
        } while (flag != -1);
        return arr;
}

Preorder traversal

vector<int> preorderTraversal(TreeNode* root) {
        int flag = -1; //Record how many elements there are in the current stack.
        TreeNode* left = root;
        TreeNode* pMove = root;
        TreeNode* stack[10] = { root };//A stack space created manually by yourself. But there is stack<TreeNode*> stk//automatically create a stack space
        vector<int> arr = {};
        if (root == NULL)
            return arr;
        //Find the leftmost number
        do {
            while (left != NULL)//Use left instead of left->left, because if it was NULL at the beginning. Such access is invalid! ! !
            {
                stack[ + + flag] = left;
                cout << left->val << '\t';
                arr.push_back(left->val);
                left = left->left;
            }
            pMove = stack[flag];
            flag--;
            left = pMove->right;
            if (left != NULL)//Duplicate the while statement above. Use do...while plus while. Indicates that both must be satisfied. But if only use. A while word. while((left != NULL)||(flag ! =-1)) will do.
            {
                stack[ + + flag] = left;
                cout << left->val << '\t';
                arr.push_back(left->val);
                left = left->left;
            }
        } while (flag != -1);
        return arr;
    }

Postorder traversal (written by myself)

Post-order traversal is slightly more difficult than pre-order and in-order. There are two main ideas that I have come across:

You can use stack stk to automatically create a stack space, but I don’t know why it should be placed on the first line. Of course, the header file #include must be included, or you can use an array to simulate a stack space.

1. Use two stacks

   • Idea: This should refer to Zuo Shen’s preorder stacking method:

     • Pre-order stack pushing method: press the head first, then pop the head out. After pressing the right node, press the left node. Then use the last-in-first-out function of the stack, pop up the left node, push the right node of the left node into the stack, and then push the left node of the left node. The cycle continues like this.

       The summary is: press the head first, then press the right, and finally press the left.

     • After referring to the preface method, you can change the order of head, right, left to:: the order of head, left, right. The results obtained at this time can be found to be post-order traversal, in reverse order. At this time, you need to use a stack to receive the reverse order. Finally, just reverse when outputting.

2. Use a stack plus a pointer variable

   • Idea: The order of printing is: left and right heads. Because it is a process of pushing the stack, it must go up. At this time, a flag bit can be used to record whether the right node of the current node has been printed, that is, the role of the variable. is the node where the trace is printed. If the current node has a right tree and is printed, the current node is printed directly. If there is a right node, but it has not been printed, the right node must be pushed into the stack at this time, and be careful not to be overwritten. If there is no right node, print directly.
   • Things to pay attention to
     • Pay attention to the overwriting of the stack space, that is, when the right tree is pushed into the stack, the current node may be overwritten. Because of the existence of flag–. At this time, you can choose to push the node back onto the stack.
     • Prevent double pushing on the stack, because the value of left is variable at any time, for example, 2 is followed by 4 and 5. When 5 is printed, left returns to 2, and 4 is pushed onto the stack. This is the cycle. It’s not right. Therefore, you can use New==left to prevent this problem. If left is New (a variable used to track printing), it means that it is pushed onto the stack twice. At this time, set the value of left to nullptr to prevent it from being pushed onto the stack.

vector<int> lastorderTraversal(TreeNode* root) {

        int flag = -1; //Record how many elements there are in the current stack.
        TreeNode* left = root;
        TreeNode* pMove = root;
        TreeNode* stack[10] = { root };//A stack space created manually by yourself.
        vector<int> arr;
        TreeNode* New = nullptr; //Record whether the right tree is printed. Keep track of printed nodes.

        if (root == NULL)
            return arr;

        do {
            //Push all the left trees into the stack. Pay attention here to prevent double pushing on the stack. Because nodes will pop up later, and nodes will be pushed onto the stack in a loop when they arrive.
            while (left != NULL)//Use left instead of left->left, because if left is NULL. Such access is invalid! ! !
            {
                stack[ + + flag] = left;
                left = left->left;
            }
            pMove = stack[flag];//Pop up the node
            flag--;
            left = pMove->right;
            //The current node has a right tree, and the right tree of the current node has not been printed yet. At this time, the node cannot be popped out, because it will not be found after it is popped up. But because of flag--, if stack[flag] = pMove is still present at this time, the current node will be overwritten. So the current node needs to be pushed back onto the stack! ! ! , only in this way it will not be overwritten. If there is no flag--, there may not be overwriting. If it is an automatically created stack, you can use stack.top() to access the top element of the stack and it will not be popped out. There are additional elements that pop up.
            if ((left != NULL) & amp; & amp; (New != pMove->right))
            {
                stack[ + + flag] = pMove;
                stack[ + + flag] = left;
                left = left->left;
            }
            //Note: pMove->right cannot be replaced with left, because the above if statement changes left. If it is changed, the result will be incorrect.
            //The current node has a right node, but it has been printed. Also print at this time
            if ((pMove->right != nullptr) & amp; & amp; (New == pMove->right))
            {
                cout << pMove->val << '\t';
                arr.push_back(pMove->val);
                New = pMove;
                //Prevent flag from going out of range. The access is illegal.
                if (flag == -1)
                    break;
                //The stack[flag] at this time is the previous node of the current node. Because printing is finished, it needs to be replaced with the right tree, otherwise it may be pushed onto the stack again.
                left = stack[flag]->right;
            }
            //There is no right node, print the current node directly
            else if(pMove->right == nullptr)
            {
                cout << pMove->val << '\t';
                arr.push_back(pMove->val);
                New = pMove;
            }
            //When performing secondary compression, it is found that the printed nodes are being pushed onto the stack again. At this time, the top while should not be continued.
            //As for what value to assign to left, as long as the conditions of while are not met. Because immediately following while is the reassignment of left.
            if (New == left)
            {
                left = nullptr;
            }
        } while (flag != -1);
        return arr;
    }

Postorder traversal (Zuo Shen code)

• The first if is to put all the left tree on the stack
• stack.peek() means taking the top element of the stack.
• The value of h can be chosen casually at the beginning, as long as it does not affect the pushing of the nodes of the left tree onto the stack. h is used to track printing nodes.
• The second if is that the current node has a right tree, and the right tree has not been processed.

Because I haven’t learned C++ for a long time, I don’t know much about vector traversal. Here is a record of the newly learned method of traversing vectors:

vector<int>::iterator it;//You can use typedef to make the name shorter
vector<int> res;

res = solution.inorderTraversal(num1);
for (it = res.begin(); it != res.end(); + + it)
{
cout << *it << '\t';
}

Refer to Zuoshen’s video screen: (non-recursive: starting at 24:23)

Link

Note: The above program is written based on my own understanding, and may be slightly different from what is shown on the video screen. However, the general idea is similar.

3. Morris traversal

As stated at the beginning.
The advantage of Morris traversal is that the time complexity and space complexity of the first two traversals are both O(n), but the time complexity of Morris traversal is O(n) and the space complexity is O(1).

Construction of binary tree

1. Node composition and creation

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    //The following is the constructor, overloaded
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left),right(right){}
};

//Create nodes, or open up space
TreeNode* AddNode(int val) {
    //C6011 warning: node->left = NULL. Because it is not judged whether node is a null pointer.
    TreeNode* node = (TreeNode*)malloc(sizeof(struct TreeNode));
    if (NULL == node)
    {
        cout << "null pointer" << endl;
    }
    else
    {
        node->left = NULL;
        node->right = NULL;
        node->val = val;
    }
    return node;
}

2. Create the structure of numbers

//Create tree
void Creat_Tree(TreeNode* root, TreeNode* left, TreeNode* right) {

    root->left = left;
    root->right = right;
}

3. Number of builds

//Create node first
 TreeNode* num1 = AddNode(1);
 TreeNode* num2 = AddNode(2);
 TreeNode* num3 = AddNode(3);
 TreeNode* num4 = AddNode(4);
 TreeNode* num5 = AddNode(5);
 TreeNode* num6 = AddNode(6);
 TreeNode* num7 = AddNode(7);
 TreeNode* num8 = AddNode(8);
 TreeNode* num9 = AddNode(9);

  Creat_Tree(num1, num2, num3);
  Creat_Tree(num2, num4, num5);
  Creat_Tree(num3, num6, num7);
  Creat_Tree(num4, num8, num9);

Code Engineering

94_BinaryTreeInorderTraversal

Additional knowledge points

1. The difference between passing by value and passing by address

Pass value

Passing by value only passes the value, and the function uses int to receive it. What is changed in the function is the value of the formal parameter, not the value of the actual parameter. Because the function will make a copy of the actual parameters, it is equivalent to opening up a space in other memory to store the copied value. At this time, changes in the function are all made for this temporarily opened space. So the two do not interfere with each other.

Address

Pass-by-address is to pass the address, and the function uses a pointer to receive it. When the pointer is dereferenced, the value is obtained. At this time, if the inside of the function is changed, the outside of the function will also be changed. Because they are all operating on the same address.

2. How to pass array into function

Of course, because the array is a continuous piece of memory, if you want to transfer the entire array, you can only transfer the address. Otherwise, how to find that piece of memory.

Several meanings of array names

1. Represents the address of the first element of the array

Basically, it represents the address of the first element of the array, except for the following two cases.

2. sizeof(arr): the size of the entire array

Indicates how many elements there are in the array

num = sizeof(arr)/sizeof(arr[0])

3. & amp;arr: takes the address of the entire array

Although the result obtained is the same as the address of the first element of the array. But note that the step sizes of the two are different, that is (& arr) + 1, which spans the length of the entire array, but arr + 1, which gets the address of the second element. There is still a slight difference between the two.

Two ways for functions to receive arrays:

1. Use pointer variables to receive.

This method is relatively common, because what is passed is the address, so it is normal to use a pointer to receive it.

If what is passed is an array of pointers, a secondary pointer should be used to receive it. Because the array is an address, and what is placed in the array is also an address.

2. Use int arr [] to receive.