二叉树递归和非递归遍历-蒲公英云

二叉树递归和非递归遍历

在这里插入图片描述
源码：

#include<queue>
#include<stack>
#include<vector>
#include<iostream>
using namespace std;
//假设空节点的值为-1
//const int arrrlens = 18;
//char arr[arrrlens] = { 'A', 'B', 'D' , '#', 'H', '#', '#', 'E', '#', '#',\
           'C', 'F' , '#', '#', 'G', '#', '#'};
//A B D # H # # E # # C F # # G # #
class Node {
public:
    Node(int el = 0, Node * l = NULL, Node * r = NULL) {
        data = el;
        mark = 0;
        left = l;
        right = r;
    }
    char data;
    int mark;
    Node* left, * right;
};
class Tree {
public:
    Tree() { root = NULL; }
    ~Tree() { delete root; }
    int create(Node* &);
    int preOrder();
    int infxOrder();
    int postOrder();
    int print_preOrder(Node*);
    int print_infixOrder(Node*);
    int print_postOrder(Node*);
public:
    Node* root;
};
int Tree::print_preOrder(Node* root)
{
    //递归先序遍历
    if (root != NULL)
    {
        cout << root->data << " ";
        print_preOrder(root->left);
        print_preOrder(root->right);
    }
    return 0;
}
int Tree::print_infixOrder(Node* root)
{
    //递归中序遍历
    if (root != NULL)
    {
        print_infixOrder(root->left);
        cout << root->data << " ";
        print_infixOrder(root->right);
    }
    return 0;
}
int Tree::print_postOrder(Node* root)
{
    //递归后序遍历
    if (root != NULL)
    {
        print_postOrder(root->left);
        print_postOrder(root->right);
        cout << root->data << " ";
    }
    return 0;
}
int Tree::preOrder()
{
    /*先序遍历，采用非递归的方法*/
    cout << endl << "先序遍历，采用非递归的方法" << endl;
    Node* p = root;
    stack<Node*> S;
    while (p != NULL || !S.empty())
    {
        if (p != NULL)
        { 
            cout << p->data << " ";
            S.push(p);
            p = p->left;
        }
        else
        {
            p = S.top();
            S.pop();
            p = p->right;
        }
    }
    return 0;
}
int Tree::infxOrder()
{
    /*中序遍历，采用非递归的方法*/
    cout << endl << "中序遍历，采用非递归的方法" << endl;
    Node* p = root;
    stack<Node*> S;
    while (p != NULL || !S.empty())
    {
        if (p != NULL)
        { 
            S.push(p);
            p = p->left;
        }
        else {
            p = S.top();
            S.pop();
            cout << p->data << " ";
            p = p->right;
        }
    }
    return 0;
}
int Tree::postOrder()
{
    /*后序遍历，采用非递归的方法*/
    cout << endl << "后序遍历，采用非递归的方法" << endl;
    Node* p = root;
    vector<Node*> S;
    vector<char> res;
    while (p != NULL || !S.empty())
    {
        if (p != NULL)
        {
            S.push_back(p);
            res.push_back(p->data);
            p = p->right;
        }
        else
        {
            p = S.back();
            S.pop_back();
            p = p->left;
        }
    }
    reverse(res.begin(), res.end());
    vector<char>::iterator ite = res.begin();
    for (; ite != res.end(); ite++) {
        cout << *ite <<" ";
    }
    cout << endl;
    return 0;
}
int Tree::create(Node*& root)
{
    // input: A B D # H # # E # # C F # # G # #
    char val;
    cin >> val;
    if (val != '#')
    {
        root = new Node(val);
        create(root->left);
        create(root->right);
    }
    else
        root = NULL;
    return 0;
}
int main()
{
    Tree tree;
    //intpu: A B D # H # # E # # C F # # G # #
    tree.create(tree.root);
    cout << " 递归先序遍历" << endl;
    tree.print_preOrder(tree.root);
    cout << endl << " 递归中序遍历" << endl;
    tree.print_infixOrder(tree.root);
    cout << endl << " 递归后序遍历" << endl;
    tree.print_postOrder(tree.root);
    tree.preOrder();
    tree.infxOrder();
    tree.postOrder();
    return 0;
}