二叉树的遍历以及 序列化和反序列化

#include <iostream>
#include <stack>
#include <deque>

using namespace std;


int my_2_power(int b)
{
    int ret = 2;
    for (int i=1; i<b; i++) {
        ret <<= 2;
    }
    return ret;
}

typedef struct tree_
{
    int data;
    struct tree_ *left;
    struct tree_ *right;
}tree;

void visitNode(tree *node)
{
    if (node != NULL ) {
        cout<<node->data<<" " ;
    }
}
tree *insert(tree *root, int data)
{
    tree *p = new tree;
    p->data = data;
    p->left = p->right = NULL;
    tree *tmp = root;
    if (tmp == NULL) {
        root = p;
    } else {
        tree *q;
        while (tmp != NULL) {
            q = tmp;
            if (data > tmp->data) {
                tmp = tmp->right;
            } else {
                tmp = tmp->left;
            }
        }
        if ( data > q->data) {
            q->right = p;
        } else {
            q->left = p;
        }
    }
    return root;
}

void preorder(tree *root)
{
    stack<tree *> s;
    while ( root || !s.empty() ) {
        if (root) {
            visitNode(root);
            s.push(root);
            root = root->left;
        } else {
            root = s.top();
            s.pop();
            root = root->right;
        }
    }
}

void inorder(tree *root)
{
    stack<tree *> s;
    while (root || !s.empty()) {
        if (root) {
            s.push(root);
            root = root->left;
        } else {
            root = s.top();
            s.pop();
            visitNode(root);
            root = root->right;
        }
    }
}

void postorder(tree *root)
{
    stack<tree *> s;
    tree *pre = NULL;
    while (root || !s.empty()) {
        if (root) {
            s.push(root);
            root = root->left;
        } else {
            root = s.top();
            if (root->right && root->right != pre) {
                root = root->right;
            } else {
                visitNode(root);
                pre = root;
                s.pop();
                root = NULL;
            }
        }
    }
}

void levelorder(tree *root)
{
    deque<tree*> now;
    now.push_back(root);
    while (!now.empty()) {
        root = now.front();
        visitNode(root);
        now.pop_front();
        if (root->left) now.push_back(root->left);
        if (root->right) now.push_back(root->right);
    }
}

void serialize(int *a, tree *root)
{
    stack< pair<tree*,int> > s;
    int i = 0;
    while (root || !s.empty() ) {
        if (root) {
            a[i] = root->data;
            s.push(make_pair<tree*,int>(root,i));
            root = root->left;
            i = 2*i + 1;
        } else {
            root = s.top().first;
            i = s.top().second;
            s.pop();
            root = root->right;
            i = 2*i+2;
        }
    }
}
tree *unserialize(int *a, int n)
{
    tree *root = NULL;
    tree *ret = NULL;
    tree *tmp;
    int i=0;
    stack< pair<tree*, int> > s;

    ret = root = new tree;
    ret->data = root->data = a[i];
    s.push(make_pair(root,i));

    while ( (root && i<n && a[i] > 0) || !s.empty()) {
         if (root && i < n && a[i] > 0 ) {
             i = 2*i + 1;
             if (i >=n || a[i] <=0 ) {
                 continue;
             }
             tmp = new tree;
             tmp->data = a[i];
             tmp->left = tmp->right = NULL;
             s.push(make_pair(tmp,i));
             root->left = tmp;
             root = tmp;
         } else {
             root = s.top().first;
             i = s.top().second;
             s.pop();
             i = 2*i+2;
             if (i<n && a[i] > 0) {
                 tmp = new tree;
                 tmp->left= tmp->right = NULL;
                 tmp->data = a[i];
                 root->right = tmp;
                 root = tmp;
                 s.push(make_pair(tmp,i));
             }
             else {
                 root = NULL;
             }
         }
    }
    return ret;
}

int main(int argc, char **argv)
{

    tree *root = NULL;
    int n;
    cout<<"input tree's nodes: ";
    cin>>n;
    cout<<"input nodes data value: ";
    int tmp;
    for (int i=0; i<n; i++) {
        cin>>tmp;
        cout<<tmp<<" ";
        root = insert(root, tmp);
    }
    cout<<endl;
    cout<<"preorder: ";
    preorder(root);
    cout<<endl<<"inorder: ";
    inorder(root);
    cout<<endl<<"postorder: ";
    postorder(root);
    cout<<endl<<"levelorder: ";
    levelorder(root);


    cout<<endl<<"================== serialize =====================\n";
    int size = my_2_power(n);
    int *a = new int[size];
    memset(a, 0, sizeof(int)*size);
    serialize(a,root);
    /*
    for (int i=0; i<size; i++) {
        cout<<a[i]<<" ";
    }
    */
    root = unserialize(a, size);
    cout<<endl;
    cout<<"preorder: ";
    preorder(root);
    cout<<endl<<"inorder: ";
    inorder(root);
    cout<<endl<<"postorder: ";
    postorder(root);
    cout<<endl<<"levelorder: ";
    levelorder(root);
    cout<<endl;
    return 0;
}