二叉树先序遍历非递归

与中序遍历类似

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<stack>
#include<queue>
using namespace std;

typedef int DATA_TYPE;

typedef struct node
{
    DATA_TYPE data;
    node *lch, *rch;
    node()
    {
        data = 0;
        lch = rch = 0;
    }
} Node;

Node nodeList[100];

void print(Node *r)
{
    if(r)
    {
        print(r->lch);
        printf("%d", r->data);
        print(r->rch);
    }
}

Node *buildTree(DATA_TYPE dataArray[], int len)
{
    for(int i=1; i<len; i++)
    {
        nodeList[i].data = dataArray[i];
        if(i%2)
        {
            nodeList[i/2].rch = &nodeList[i];
        }
        else
        {
            nodeList[i/2].lch = &nodeList[i];
        }
    }
    return &nodeList[1];
}

/**
* 先序遍历的非递归算法
*/
void preOrderTraversal(Node *r)
{
    Node *p;
    stack<Node*> s;
    while(!s.empty() || r)
    {
        while(r)
        {
            s.push(r);
            printf("%d", r->data);
            r=r->lch;
        }
        p = s.top();
        s.pop();
        r=p->rch;
    }
}

int main()
{
    DATA_TYPE dataArray[] = {0,1,2,3,4,5,6,7};
    Node *root = buildTree(dataArray, sizeof(dataArray)/sizeof(DATA_TYPE));
    //  print(root);
    preOrderTraversal(root);
    return 0;
}