二叉树非递归遍历,该如何解决

2012-04-21

二叉树非递归遍历最近在看数据结构，学到二叉树的非递归遍历时出现很奇怪的现象，就是只能遍历根节点和左子

二叉树非递归遍历
最近在看数据结构，学到二叉树的非递归遍历时出现很奇怪的现象，就是只能遍历根节点和左子树，然后准备遍历右子树就会出错，找了很长时间都没找到原因，所以现在贴出来，请各位帮忙，谢谢先。。。

C/C++ code

#include <stdio.h>#include <malloc.h>#include <stdlib.h>#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define Status int#define ERROR 0#define OK 1 typedef struct BTreeNode{    char     data;    struct   BTreeNode  * pLChild;    struct   BTreeNode  * pRChild;}BTREE_NODE, * pTREE_NODE;typedef struct {    pTREE_NODE base;    pTREE_NODE top;    int stackSize;}SqStack; /************ 初始化一个栈，初始化后栈为空*************/Status initStack(SqStack &S){     S.base = (pTREE_NODE) malloc( sizeof(BTREE_NODE) * STACK_INIT_SIZE );    if(!S.base)        return ERROR;    S.top = S.base;    S.stackSize = STACK_INIT_SIZE;    return OK;}/**************判断栈是否为空*********************/Status stackEmpty(SqStack S){    if(S.base == S.top)        return OK;    return ERROR;}/**************压栈，压入的值为pt*******************/Status push(SqStack &S, pTREE_NODE pt){     if(S.top - S.base >= S.stackSize){        S.base = (pTREE_NODE) realloc (S.base, (S.stackSize + STACKINCREMENT) * sizeof (BTREE_NODE));        if(!S.base)            return ERROR;        S.top = S.base + S.stackSize;        S.stackSize = S.stackSize + STACKINCREMENT;    }    S.top = pt;    S.top++;    return OK;}/**************出栈，将在栈顶的值放入pt中*******************/pTREE_NODE pop(SqStack &S){    pTREE_NODE pt;    if(S.base != S.top){        --S.top;        pt = S.top;        return pt;    }    }/**************得到栈顶值，放在pt中*******************/pTREE_NODE getTop(SqStack S){    pTREE_NODE pt;    if(S.top == S.base){        printf("栈为空");        return ERROR;    }    pt = (S.top - 1);    return pt;}pTREE_NODE CreateNode(pTREE_NODE ptr, char value, char child){    pTREE_NODE ptmp = (pTREE_NODE)malloc(sizeof(BTREE_NODE));    if(ptmp == NULL)    {        printf("内存分配失败\n");        exit(-1);    }    ptmp ->data = value;    ptmp ->pLChild = NULL;    ptmp ->pRChild = NULL;    if(child == 'L')    {        ptr -> pLChild = ptmp;    }    else if(child == 'R')    {        ptr -> pRChild = ptmp;    }    return ptmp;}struct BTreeNode* initialTree(){    pTREE_NODE pRoot = (pTREE_NODE)malloc(sizeof(BTREE_NODE));    pRoot -> data = 'A';    pRoot -> pLChild = NULL;    pRoot -> pRChild = NULL;    pTREE_NODE pB = CreateNode(pRoot, 'B', 'R');    pTREE_NODE pC = CreateNode(pRoot, 'C', 'L');    pTREE_NODE pD = CreateNode(pC, 'D', 'L');    CreateNode(pD, 'E', 'R');    CreateNode(pB, 'F', 'L');    CreateNode(pB, 'G', 'R');    printf("二叉树创建完毕！\n");    return pRoot;}void iterativePreorder(SqStack stack, pTREE_NODE ptr) {    if(ptr != NULL)    {        push(stack, ptr);        while(!stackEmpty(stack))        {            ptr = pop(stack);            printf("%c", ptr ->data);            if(ptr -> pRChild != NULL)            {                push(stack, ptr ->pRChild);            }            if(ptr -> pLChild != NULL)            {                push(stack, ptr->pLChild);            }        }    }}int main(){    printf("二叉树遍历演示\n");    pTREE_NODE pRoot = initialTree();    SqStack stack;    initStack(stack);    printf("非递归先序遍历\n");    iterativePreorder(stack, pRoot);     printf("\n");    return 0;}

[解决办法]
你的栈代码是错的，根本就不能起到作用。
你看你的入栈操作：

C/C++ code

    S.top = pt;    S.top++;    return OK;
[解决办法]
栈的实现代码有问题，已经帮你修改过来了。。
C/C++ code#include <stdio.h>#include <malloc.h>#include <stdlib.h>#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define Status int#define ERROR 0#define OK 1 typedef struct BTreeNode{    char     data;    struct   BTreeNode  * pLChild;    struct   BTreeNode  * pRChild;}BTREE_NODE, * pTREE_NODE;typedef struct {    pTREE_NODE *base;   //修改了    pTREE_NODE *top;   //修改了    int stackSize;}SqStack; /************ 初始化一个栈，初始化后栈为空*************/Status initStack(SqStack &S){     S.base = (pTREE_NODE*) malloc( sizeof(BTREE_NODE) * STACK_INIT_SIZE );   //修改了    if(!S.base)        return ERROR;    S.top = S.base;    S.stackSize = STACK_INIT_SIZE;    return OK;}/**************判断栈是否为空*********************/Status stackEmpty(SqStack S){    if(S.base == S.top)        return OK;    return ERROR;}/**************压栈，压入的值为pt*******************/Status push(SqStack &S, pTREE_NODE pt){     if(S.top - S.base >= S.stackSize){        S.base = (pTREE_NODE * ) realloc (S.base, (S.stackSize + STACKINCREMENT) * sizeof (BTREE_NODE));   //修改了        if(!S.base)            return ERROR;        S.top = S.base + S.stackSize;        S.stackSize = S.stackSize + STACKINCREMENT;    }    *S.top = pt;   //修改了    S.top++;    return OK;}/**************出栈，将在栈顶的值放入pt中*******************/pTREE_NODE pop(SqStack &S){    pTREE_NODE pt;    if(S.base != S.top)    {        --S.top;        pt = *S.top;   //修改了        return pt;    }    }/**************得到栈顶值，放在pt中*******************/pTREE_NODE getTop(SqStack S){    pTREE_NODE pt;    if(S.top == S.base){        printf("栈为空");        return ERROR;    }    pt = *(S.top - 1);   //修改了    return pt;}pTREE_NODE CreateNode(pTREE_NODE ptr, char value, char child){    pTREE_NODE ptmp = (pTREE_NODE)malloc(sizeof(BTREE_NODE));    if(ptmp == NULL)    {        printf("内存分配失败\n");        exit(-1);    }    ptmp ->data = value;    ptmp ->pLChild = NULL;    ptmp ->pRChild = NULL;    if(child == 'L')    {        ptr -> pLChild = ptmp;    }    else if(child == 'R')    {        ptr -> pRChild = ptmp;    }    return ptmp;}struct BTreeNode* initialTree(){    pTREE_NODE pRoot = (pTREE_NODE)malloc(sizeof(BTREE_NODE));    pRoot -> data = 'A';    pRoot -> pLChild = NULL;    pRoot -> pRChild = NULL;    pTREE_NODE pB = CreateNode(pRoot, 'B', 'R');    pTREE_NODE pC = CreateNode(pRoot, 'C', 'L');    pTREE_NODE pD = CreateNode(pC, 'D', 'L');    CreateNode(pD, 'E', 'R');    CreateNode(pB, 'F', 'L');    CreateNode(pB, 'G', 'R');    printf("二叉树创建完毕！\n");    return pRoot;}void iterativePreorder(SqStack stack, pTREE_NODE ptr) {    if(ptr != NULL)    {        push(stack, ptr);        while(!stackEmpty(stack))        {            ptr = pop(stack);            printf("%c", ptr ->data);            if(ptr -> pRChild != NULL)            {                push(stack, ptr ->pRChild);            }            if(ptr -> pLChild != NULL)            {                push(stack, ptr->pLChild);            }        }    }}int main(){    printf("二叉树遍历演示\n");    pTREE_NODE pRoot = initialTree();    SqStack stack;    initStack(stack);    printf("非递归先序遍历\n");    iterativePreorder(stack, pRoot);     printf("\n");    return 0;}

热点排行