二叉树的遍历-先序遍历，中序遍历，后序遍历

二叉树的建立以及基本的遍历方式： 

本文的非递归遍历方式的内容参考了

1. C++实现二叉树 前、中、后序遍历（递归与非递归）非递归实现过程最简洁版本
2. 更简单的非递归遍历二叉树的方法

• 先序遍历：根左右

void PreOrder(BTtree &T)
{
    if(T)
    {
        cout<< T->val << ' ';
        PreOrder(T->left);
        PreOrder(T->right);
    }
}

• 中序遍历：左根右

void InOrder(BTtree &T)
{
    if(T)
    {
        InOrder(T->left);
        cout<<T->val<<' ';
        InOrder(T->right);
    }
}

• 后序遍历：左右根

void PostOrder(BTtree &T)
{
    if(T)
    {
        PostOrder(T->left);
        PostOrder(T->right);
        cout<<T->val<<' ';
    }
}

更简单的非递归遍历二叉树的方法

统一的实现思路和代码风格的方法，完成对二叉树的三种非递归遍历。 参考了上面给出的博客内容。没有在具体事例中验证代码的准确性了。

 
//更简单的非递归前序遍历
void preorderTraversalNew(TreeNode *root, vector<int> &path)
{
    stack< pair<TreeNode *, bool> > s;
    s.push(make_pair(root, false));
    bool visited;
    while(!s.empty())
    {
        root = s.top().first;
        visited = s.top().second;
        s.pop();
        if(root == NULL)
            continue;
        if(visited)
        {
            path.push_back(root->val);
        }
        else
        {
            s.push(make_pair(root->right, false));
            s.push(make_pair(root->left, false));
            s.push(make_pair(root, true));
        }
    }
}

 
//更简单的非递归中序遍历
void inorderTraversalNew(TreeNode *root, vector<int> &path)
{
    stack< pair<TreeNode *, bool> > s;
    s.push(make_pair(root, false));
    bool visited;
    while(!s.empty())
    {
        root = s.top().first;
        visited = s.top().second;
        s.pop();
        if(root == NULL)
            continue;
        if(visited)
        {
            path.push_back(root->val);
        }
        else
        {
            s.push(make_pair(root->right, false));
            s.push(make_pair(root, true));
            s.push(make_pair(root->left, false));
        }
    }
}

 
//更简单的非递归后序遍历
void postorderTraversalNew(TreeNode *root, vector<int> &path)
{
    stack< pair<TreeNode *, bool> > s;
    s.push(make_pair(root, false));
    bool visited;
    while(!s.empty())
    {
        root = s.top().first;
        visited = s.top().second;
        s.pop();
        if(root == NULL)
            continue;
        if(visited)
        {
            path.push_back(root->val);
        }
        else
        {
            s.push(make_pair(root, true));
            s.push(make_pair(root->right, false));
            s.push(make_pair(root->left, false));
        }
    }
}

 

•  先序遍历更简洁的非递归代码

void preorderTraversalNew(TreeNode *root, vector<int> &path)
{
    stack<TreeNode *> s;
    s.push(root);
    while(!s.empty())
    {
        root = s.top();
        s.pop();
        if(root == NULL)
        {
            continue;
        }
        else
        {
            path.push_back(root->val);
            s.push(root->right);
            s.push(root->left);
        }
    }
}

 程序示例代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <bits/stdc++.h>
using namespace std;


typedef struct node
{
    struct node *left;
    struct node *right;
    char val;
}BTnode, *BTtree;

void CreateTree(BTtree &T)
{
    char ch;
    cin >> ch;
    if(ch == '#') // 空节点以 ‘#’ 表示, 结束递归
        T = NULL;
    else
    {
        T = new BTnode; //新申请一个节点空间
        T->val = ch;
        CreateTree(T->left); //递归建立左子树
        CreateTree(T->right); // 递归建立右子树
    }
}

void PreOrder(BTtree &T)
{
    if(T)
    {
        cout<< T->val << ' ';
        PreOrder(T->left);
        PreOrder(T->right);
    }
}

void InOrder(BTtree &T)
{
    if(T)
    {
        InOrder(T->left);
        cout<<T->val<<' ';
        InOrder(T->right);
    }
}

void PostOrder(BTtree &T)
{
    if(T)
    {
        PostOrder(T->left);
        PostOrder(T->right);
        cout<<T->val<<' ';
    }
}

//教材上的非递归先序遍历写法
void PreOrderTraversal(BTtree &T)
{
    stack<BTtree>st;
    BTnode *p = T;
    while(p!=NULL || !st.empty())
    {
        while(p!=NULL)
        {
            cout<<p->val<<' ';
            st.push(p);
            p = p->left;
        }
        if(!st.empty())
        {
            p = st.top();
            st.pop();
            p = p->right;
        }
    }
}

//教材上的非递归先序遍历写法
void InOrderTraversal(BTtree &T)
{
    stack<BTtree>st;
    BTnode *p = T;
    while(!st.empty() || p!=NULL)
    {
        while(p)
        {
            st.push(p);
            p = p->left;
        }

        p = st.top();
        cout<< p->val<<' ';
        st.pop();
        p = p->right;
    }
}




int main()
{
    BTtree T;
    CreateTree(T); //建立二叉树

    cout << "先序遍历二叉树（递归版）：";
    PreOrder(T);
    cout<<endl;

    cout << "先序遍历二叉树（非递归版）：";
    PreOrderTraversal(T);
    cout<<endl;

    cout << "中序遍历二叉树（递归版）：";
    InOrder(T);
    cout<<endl;

    cout << "中序遍历二叉树非递归版）：";
    InOrderTraversal(T);
    cout<<endl;

    cout << "后序遍历二叉树（递归版）：";
    PostOrder(T);
    cout<<endl;
    return 0;
}

 

应用：

1. 剑指offer-面试题54：二叉搜索树的第K大节点