二叉樹遍歷的非遞歸實現

二叉樹的非遞歸實現需要使用到下推棧，下面給出前序遍歷的完整代碼：

#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);
    }
}

二叉樹的常見問題及其解決程序 http://www.linuxidc.com/Linux/2013-04/83661.htm

【遞歸】二叉樹的先序建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75608.htm

在JAVA中實現的二叉樹結構 http://www.linuxidc.com/Linux/2008-12/17690.htm

【非遞歸】二叉樹的建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75607.htm

二叉樹遞歸實現與二重指針 http://www.linuxidc.com/Linux/2013-07/87373.htm

二叉樹先序中序非遞歸算法 http://www.linuxidc.com/Linux/2014-06/102935.htm

輕松搞定面試中的二叉樹題目 http://www.linuxidc.com/linux/2014-07/104857.htm