二叉树的各种遍历方法

binary_tree.cpp

/*************************************************************************
	> File Name: binary_tree.cpp
	> Author: 
	> Mail: 
	> Created Time: 2016年11月03日 星期四 21时50分39秒
 ************************************************************************/

#include<iostream>
using namespace std;
#include <stack>
#include <queue>

typedef int tree_node_elem_t;

typedef struct binary_tree_node_t {
    binary_tree_node_t *left;
    binary_tree_node_t *right;
    tree_node_elem_t elem;
} binary_tree_node_t;


void pre_order_recursive(const binary_tree_node_t *root) {
    if (root == NULL)
        return;
    cout << root->elem << endl;
    pre_order_recursive(root->left);
    pre_order_recursive(root->right);
}

void pre_order(const binary_tree_node_t *root) {
    const binary_tree_node_t *p;
    stack<const binary_tree_node_t *> s;

    p = root;
    if (p !=NULL)
        s.push(p);
    while(! s.empty()) {
        p = s.top();
        s.pop();
        cout << p->elem << endl;
        if( p->right != NULL )
            s.push(p->right);
        if( p->left != NULL )
            s.push(p->left);
    }   
}

void in_order_recursive(const binary_tree_node_t *root) {
    if (root == NULL)
        return;
    in_order_recursive(root->left);
    cout << root->elem << endl;
    in_order_recursive(root->right);
}

void in_order(const binary_tree_node_t *root) {
    const binary_tree_node_t *p;
    stack<const binary_tree_node_t *> s;
    p = root;
    while (! s.empty() || p != NULL) {
        if (p != NULL) {
            s.push(p);
            p = p->left;
        } else {
            p = s.top();
            s.pop();
            cout << p->elem << endl;
            p = p->right;
        }
    }        
}

void post_order_recursive(const binary_tree_node_t *root) {
    if (root == NULL)
        return;
    post_order_recursive(root->left);
    post_order_recursive(root->right);
    cout << root->elem << endl;
}

void post_order(const binary_tree_node_t *root) {
    const binary_tree_node_t *p, *q;
    stack<const binary_tree_node_t *> s;
    p = root;

    do {
        while (p != NULL) {
            s.push(p);
            p = p->left;
        }
        q = NULL;
        while( !s.empty() ) {
            p = s.top();
            s.pop();
            if ( p->right == q ) {
                cout << p->elem << endl;
                q = p;
            } else {
                s.push(p);
                p = p->right;
                break;
            }
        }
    } while (! s.empty())
}

void level_order(const binary_tree_node_t * root) {
    const binary_tree_node_t *p;
    queue<const binary_tree_node_t *> q;
    p = root;
    if (p != NULL)
        q.push(p);
    while( !q.empty() ) {
        p = q.front();
        q.pop();
        cout << p->elem << endl;
        if (p->left != NULL)
            q.push(p->left);
        if (p->right != NULL)
            q.push(p->right);
    }
}