MyException - 我的异常网
当前位置:我的异常网» C++ » 二叉树非递归遍历,该如何解决

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

www.MyException.Cn  网友分享于:2013-04-22  浏览:8次
二叉树非递归遍历
最近在看数据结构,学到二叉树的非递归遍历时出现很奇怪的现象,就是只能遍历根节点和左子树,然后准备遍历右子树就会出错,找了很长时间都没找到原因,所以现在贴出来,请各位帮忙,谢谢先。。。
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;
}

文章评论

Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
那些争议最大的编程观点
那些争议最大的编程观点
我是如何打败拖延症的
我是如何打败拖延症的
程序员应该关注的一些事儿
程序员应该关注的一些事儿
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
每天工作4小时的程序员
每天工作4小时的程序员
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
如何成为一名黑客
如何成为一名黑客
为什么程序员都是夜猫子
为什么程序员都是夜猫子
Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
漫画:程序员的工作
漫画:程序员的工作
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
鲜为人知的编程真相
鲜为人知的编程真相
看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
 程序员的样子
程序员的样子
老程序员的下场
老程序员的下场
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
程序员的鄙视链
程序员的鄙视链
中美印日四国程序员比较
中美印日四国程序员比较
做程序猿的老婆应该注意的一些事情
做程序猿的老婆应该注意的一些事情
一个程序员的时间管理
一个程序员的时间管理
旅行,写作,编程
旅行,写作,编程
什么才是优秀的用户界面设计
什么才是优秀的用户界面设计
程序员必看的十大电影
程序员必看的十大电影
程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
“懒”出效率是程序员的美德
“懒”出效率是程序员的美德
编程语言是女人
编程语言是女人
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
10个调试和排错的小建议
10个调试和排错的小建议
程序员和编码员之间的区别
程序员和编码员之间的区别
写给自己也写给你 自己到底该何去何从
写给自己也写给你 自己到底该何去何从
总结2014中国互联网十大段子
总结2014中国互联网十大段子
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
代码女神横空出世
代码女神横空出世
如何区分一个程序员是“老手“还是“新手“?
如何区分一个程序员是“老手“还是“新手“?
Java程序员必看电影
Java程序员必看电影
10个帮程序员减压放松的网站
10个帮程序员减压放松的网站
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
科技史上最臭名昭著的13大罪犯
科技史上最臭名昭著的13大罪犯
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有