先序，中序，后序用循环和递归的实现

本文主要是介绍先序，中序，后序用循环和递归的实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

先序，中序，后序用循环和递归的实现

#include<iostream>

#include<vector>

#include<stack>

using namespace std;

struct binaryTreeNode

{

    int m_data;

    binaryTreeNode *m_left;

    binaryTreeNode *m_right;

};

vector<int> result;

//递归先序遍历

void preOderTraversal(binaryTreeNode *root)

{

    if(root!=NULL)

    {

        result.push_back(root->m_data);

        if(root->m_left!=NULL)

            inOderTraversal(root->m_left);

        if(root->m_right!=NULL)

            inOderTraversal(root->m_right);

    }

}

//先实现循环先序遍历

vector<int> preOderTraversal1(binaryTreeNode *root)

{

    stack<binaryTreeNode *> stack1;

    vector<int> v;

    binaryTreeNode *k;

    if(root!=NULL)

    {

        stack1.push(root);

    }

    while(stack1.size()>0)

    {

        k=stack1.top();

        v.push_back(k->m_data);

        stack1.pop();

        if(k->m_right!=NULL)

        {

            stack1.push(k->m_right);

        }

        if(k->m_left!=NULL)

        {

            stack1.push(k->m_left);

        }

    }

    return v;

}

//递归中序遍历

void inOderTraversal(binaryTreeNode *root)

{

    if(root!=null)

    {

        if(root->m_left!=NULL)

        {

            inOderTraversal(root->m_left);

        }

        result.push_back(root->m_data);

        if(root->m_right!=NULL)

        {

            inOderTraversal(root->m_right);

        }

    }

}

//循环中序遍历

vector<int> inOdertraversal1(binaryTreeNode *root)

{

    stack<binaryTreeNode *> stack1;

    vector<int> v;

    binaryTreeNode * k;

    while(stack1.size()||root!=NULL)

    {

        if(root!=NULL)

        {

            stack1.push(root);

            root=root->m_left;

        }

        else

        {

            root=stack1.top();

            stack1.pop();

            v.push_back(k->m_data);

            root=root->m_right;

        }

 

    }

    return v;

}

//递归后序遍历

void postOderTraversal(binaryTreeNode *root)

{

    if(root!=NULL)

    {

        if(root->m_left!=NULL)

        {

            postOderTraversal(root->m_left);

        }

        if(root->m_right!=NULL)

        {

            postOderTraversal(root->m_right);

        }

        result.push_back(root->m_data);

    }

}

 

//循环后序遍历

vector<int> postOderTraversal1(binaryTreeNode *root)

{

    stack<binaryTreeNode *> stack1;

    vector<int> v;

    //binaryTreeNode * k;

    if(root!=NULL)

    {

        stack1.push(root);

    }

    while(stack1.size()>0)

    {

        root=stack1.top();

        stack1.pop();

        v.push_back(root->m_data);

        if(root->m_left!=NULL)

        {

            stack1.push(root->m_left);

        }

        if(root->m_right!=NULL)

        {

            stack1.push(root->m_right);

        }

    }

    std::reverse(v.begin(),v.end());

    return v;

}

分析：在用循环实现先序遍历时（中左右的访问方式），先访问root->m_data,然后在进栈stack1.push(root->m_right),最后在stack1.push(root->m_left).

栈的操作为：进栈root，出栈root(进动态数组vector)，进栈root->right,进栈root->left,出栈root->left(进动态数组vector，root=root->left)，进栈root->right,进栈root->left,出栈root->left

(进动态数组vector，root=root->left),就这样一直循环下去，实现了先序遍历。

而在用循环实现后序遍历时（左右中的访问方式），先访问root->m_data,然后在进栈stack1.push(root->m_left),最后在stack1.push(root->m_right);

左右中的倒过来为中右左，只要把中左右稍微改一下就可以实现。

在用循环实现中序遍历时（左右中的访问方式），首先它用的if..else..这个分叉，来实现二叉树的分叉，进栈root，进栈root->left(root=root->left),进栈root->left,直到为空，然后出栈（root=出栈，）并且进动态数组（vector），（root=root->right）,继续循环。

 

这篇关于先序，中序，后序用循环和递归的实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---