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

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

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

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

相关推荐