当前位置:网站首页>Preorder, inorder, follow-up of binary tree (non recursive version)

Preorder, inorder, follow-up of binary tree (non recursive version)

2022-07-01 15:38:00 Try to be better zz

Tips : When the article is finished , Directories can be generated automatically , How to generate it, please refer to the help document on the right


Preface

The pre order, middle order and post order of the non recursive version of the binary tree are also often tested in the interview , Must be proficient in !
Next, we will talk about how to print the first, middle and last sequence of binary tree non recursively .

One 、 Before the order

Ideas : Data structure stack is generally used to change recursion to non recursion , Print when the current node is out of the stack , And a right node is added to the right node first ,
Then add the left node , Because the antecedent root is about , The stack is in reverse order , So first enter the node .

void Print(TreeNode* root)
{
    
    // Before the order 
    stack<TreeNode*> s = stack<TreeNode*>();// Create a stack 
    s.push(root);// Head node stack 
      The order of stacking is right pressing right , There is left pressure left 
    while (!s.empty())
    {
    
        TreeNode* cur = s.top();
        s.pop();
        cout << to_string(cur->val)+"" ;
        if (cur->right)
        {
    
            s.push(cur->right);
        }
        if (cur->left)
        {
    
            s.push(cur->left);
        }

    }
}

Two 、 In the following order

Ideas : Different from the previous sequence , In the following sequence, we need two stacks to exchange , The result order of the first stack is root right left , Because the stack is in reverse order , We will s1 Put the data in the stack s2 You get left and right , Subsequent operations are similar to those in the previous sequence .

 In the following order 
    stack<TreeNode*> s1 = stack<TreeNode*>();
    stack<TreeNode*> s2 = stack<TreeNode*>();
    s1.push(root);
    while (!s1.empty())
    {
    
        TreeNode* cur = s1.top();
        s1.pop();
        s2.push(cur);
        if (cur->left)
        {
    
            s1.push(cur->left);
        }
        if (cur->right)
        {
    
            s1.push(cur->right);
        }
    }
    while (!s2.empty())
    {
    
        TreeNode* cur = s2.top();
        s2.pop();
        cout << cur->val << endl;
    }

3、 ... and 、 Middle preface

The code is as follows :

 Middle preface 
    stack<TreeNode*> t = stack<TreeNode*>();
    TreeNode* cur = root;
    while (!t.empty() || cur!=nullptr)
    {
    

        if (cur!= nullptr)
        {
    
            t.push(cur);
            cur = cur->left;
        }
        else
        {
    
            cur = t.top();
            t.pop();
            cout << cur->val << endl;
            cur = cur->right;
        }
    }

summary

原网站

版权声明
本文为[Try to be better zz]所创,转载请带上原文链接,感谢
https://yzsam.com/2022/182/202207011535530576.html