二叉树非递归遍历解决思路

2012-04-26

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

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

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;}/**************将栈清空*****************/Status clearStack(SqStack &S){    S.top = S.base;    return OK;}/**********销毁一个栈**********/Status destroyStack(SqStack &S){     free(S.base);     return  OK; }/**************压栈，压入的值为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;}/**************得到栈长度******************/int getLength(SqStack S){    int length = 0;    if(S.base == S.top)        return 0;    for(pTREE_NODE  i = S.base; i != S.top; i++){        ++length;    }    return length; }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;}

------解决方案--------------------

void iterativePreorder(SqStack stack, pTREE_NODE ptr)
{
if(ptr != NULL)//if 改为 while
{
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);
}
}
}
}

[解决办法]
没看懂你压栈的逻辑...
这是我写的遍历的代码，但是在Ａ的右子树押栈时出现了问题。

C/C++ code

if(ptr != NULL)    {        push(stack, ptr);        while(!stackEmpty(stack))        {            ptr = pop(stack);            //printf("%c", ptr->data);            while (ptr != NULL)            {                printf("%c", ptr->data);                if (ptr->pRChild != NULL)                {                    push(stack, ptr->pRChild);                 }                ptr = ptr->pLChild;            }                    }     }
[解决办法]
一贴两发啊，这个问题昨天就解决了的。
[解决办法]
自己写个栈来递归，你累不累啊！

热点排行

C语言

二叉树非递归遍历解决思路