二叉树遍历的非递归实现

二叉树的非递归实现需要使用到下推栈，下面给出前序遍历的完整代码：

#include <stdio.h>
#include <stdlib.h>
#define MAX  10

//二叉树存储结构定义
typedef char Item;
typedef struct node *link;
struct node {Item item; link l, r;};

int  Create(link *tp);
void show(link h);
void tranverse(link h, void (*visit)(link));

//下推栈存储结构定义
typedef link SItem;
static SItem *s;
static int    N;

void  STACKinit(int maxN);
int  STACKempty();
void  STACKpush(SItem item);
SItem STACKpop();

int main()
{
    link tree;

Create(&tree);
    tranverse(tree, show);

return 0;
}

void STACKinit(int maxN)
{
    s = (SItem *)malloc(maxN * sizeof(SItem));
    if (!s) return;
    N = 0;
}

int STACKempty()
{
    return N==0;
}

void STACKpush(SItem item)
{
    s[N++] = item;
}

SItem STACKpop()
{
    return s[--N];
}

int Create(link *tp)
{
    //构造方法，或者说构造顺序：中序遍历构造
    char x;
    scanf("%c",&x);
    if(x=='#')
    {
        *tp=NULL;//指针为空，树节点中的某个指针为空
        return 0;
    }
    *tp=(link)malloc(sizeof(**tp));//将树节点中指针指向该地址空间
    if(*tp==NULL)
        return 0;
    (*tp)->item=x;
    Create(&((*tp)->l));
    Create(&((*tp)->r));
    return 1;
}

void show(link h)
{
    printf(" %c ", h->item);
}

//前序遍历
void tranverse(link h, void (*visit)(link))
{
    STACKinit(MAX);
    STACKpush(h);
    while (!STACKempty()){
        (*visit)(h = STACKpop());
        if (h->r != NULL) STACKpush(h->r);
        if (h->l != NULL) STACKpush(h->l);
    }
}

二叉树的常见问题及其解决程序

【递归】二叉树的先序建立及遍历

在Java中实现的二叉树结构

【非递归】二叉树的建立及遍历

二叉树递归实现与二重指针

二叉树先序中序非递归算法

轻松搞定面试中的二叉树题目