鱼C论坛

 找回密码
 立即注册
查看: 3809|回复: 15

小白对二叉树非递归中序遍历的若干问题

[复制链接]
发表于 2018-5-20 00:18:53 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
最近在学习二叉树非递归中序遍历,盗来的代码如下:
#include <stdio.h>
#include <stdlib.h>
#define A 100      //栈的空间初始分配大小

typedef struct BiNode{   //定义二叉链表
        char data;
        struct BiNode *lchild,*rchild;
}BiNode,*BiTree;                           //BiNode->struct BiNode      BiTree-> struct BiNode *    -> BiTree * 双重指针

typedef struct{ //定义栈
        BiTree *base;
        BiTree *top;
        int stacksize;//分配的存储空间的大小
}Sqstack;                   //Sqstack->struct

void initstack(Sqstack *S)  //初始化栈
{
        S->base=(BiTree* )malloc(sizeof(A))        ;
        S->top=S->base;
        S->stacksize=A;
}

int emptystack(Sqstack* S) //判断栈是否为空,若为空则返回1
{
        if(S->base!=S->top)
        {
                return 0;
        }
        else
        {
                return 1;
        }
}


void push(Sqstack *S,BiTree e)  //将元素进栈  这里e不用指针->因为不用返回e,而是输入e
{
        if(S->top-S->base==S->stacksize)
        {
                printf("此时栈满,不能插入啦。\n");
        }
        else
        {
                *(S->top)=e;
                (S->top)++;
        }
}


void pop(Sqstack *S,BiTree *e)  //将元素出栈    这里e要用指针->因为出栈有返回栈顶
{ 
        if(S->base==S->top)
        {
                printf("为空,不能弹出\n");
        }
        else
        {
                S->top--;
                *e=*(S->top);
        }
}

void initBitree(BiTree *T)   //初始化树,即建造一棵空树   * 用来返回值
{
        *T=NULL;
        printf("空树构造成功。\n");
}


void CreatBitree(BiTree* T) //先序建立一个二叉树   *用来返回值   *T仍然是一个指针->因为BiTree本身是一个指针类型
{
        char c;
        scanf("%c",&c);
        if(c=='*')
        {
                *T=NULL;
        }
        else
        {
                *T=(BiTree)malloc(sizeof(BiNode));
                (*T)->data=c;//生成的根节点里输入数据
                CreatBitree(&(*T)->lchild);  //递归创建左子树
                CreatBitree(&(*T)->rchild);  //递归创建右子树
        }
}

void inorderbitree(BiTree T)  //中序遍历,非递归    没有改变树的结构 没必要用指针
{
        BiTree p=T;
        Sqstack S;
        initstack(&S);//初始化栈,构造结点
        while(p||!emptystack(&S))
        {
                if(p)         //一直遍历到左子树的最下边 便遍历边入栈
                {
                        push(&S,p);
                        p=p->lchild;
                }
                else         //当p为空时,说明已经到达左子树最下边,此时需要出栈,并打印该结点
                {
                        pop(&S,&p);
                        printf("%c",p->data);
                        p=p->rchild;  //进入右子树
                }
        }
}




int main()
{
        BiTree T;
        printf("先序创建一个二叉树:\n");
        CreatBitree(&T);
        printf("该二叉树的中序遍历结果为:");
        inorderbitree(T);
        printf("\n");
        return 0;
}


上面是一个可执行的代码,我自己加了点注释,不知对否。接下来我的问题如下:

①inorderbitree函数为什么不能改为如下代码:
void inorderbitree(BiTree T)  //中序遍历,非递归    没有改变树的结构 没必要用指针
{
        BiTree p=T;
        Sqstack *S=NULL;
        initstack(S);//初始化栈,构造结点
        while(p||!emptystack(S))
        {
                if(p)         //一直遍历到左子树的最下边 便遍历边入栈
                {
                        push(S,p);
                        p=p->lchild;
                }
                else         //当p为空时,说明已经到达左子树最下边,此时需要出栈,并打印该结点
                {
                        pop(S,&p);
                        printf("%c",p->data);
                        p=p->rchild;  //进入右子树
                }
        }
}

即把S定义为Sqstack类型的指针,这样的话在调用函数的时候可以直接写S而不是&S。但是不能成功运行,为何?


②CreatBitree函数中的scanf是如何做到直接输入一行字符便可执行,而不是需要输入一个字符按一次回车?(是不是和递归有关?本人对递归不是很了解。。)


本人小白,最近因为比较忙对学习一直朝三暮四,但会尽快恢复状态。如果我的问题有蠢到各位或者有哪些知识点没有学好的地方,恳请各位指正!
在这里先谢谢各位dalao!如有更好的学习建议请各位指出!

PS:严蔚敏的数据结构太晦涩难懂了。

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-5-20 02:11:17 | 显示全部楼层
1.png
2.png
GIF.gif

PS:严蔚敏的数据结构的确太晦涩难懂了,不适合自学,推荐一个适合自学的《大话数据结构》
^_^
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2018-5-20 08:11:26 From FishC Mobile | 显示全部楼层
人造人 发表于 2018-5-20 02:11
PS:严蔚敏的数据结构的确太晦涩难懂了,不适合自学,推荐一个适合自学的《大话数据结构》
^_^

谢谢dalao,那我那个想法有错吗,如果没错的话该怎么用指针定义S呢。我是看到他报错说没有初始化,我才把他NULL。。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-5-20 13:03:58 | 显示全部楼层

回帖奖励 +1 鱼币

仓鼠爱跑圈 发表于 2018-5-20 08:11
谢谢dalao,那我那个想法有错吗,如果没错的话该怎么用指针定义S呢。我是看到他报错说没有初始化,我才把 ...

没有仔细看你的程序,这样应该可以,至少调试没有报错

360截图1872012767120110.png
#include <stdio.h>
#include <stdlib.h>
#define A 100                        // 栈的空间初始分配大小

// 定义二叉链表
typedef struct BiNode
{
        char data;
        struct BiNode *lchild, *rchild;
}BiNode, *BiTree;

// 定义栈
typedef struct
{
        BiTree *base;
        BiTree *top;
        int stacksize;                // 分配的存储空间的大小
}Sqstack;

int emptystack(Sqstack* S)        // 判断栈是否为空,若为空则返回1
{
        if(S->base != S->top)
        {
                return 0;
        }
        else
        {
                return 1;
        }
}

void push(Sqstack *S, BiTree e)                // 将元素进栈  这里e不用指针->因为不用返回e,而是输入e
{
        if(S->top - S->base == S->stacksize)
        {
                printf("此时栈满,不能插入啦。\n");
        }
        else
        {
                *(S->top) = e;
                (S->top)++;
        }
}

void pop(Sqstack *S, BiTree *e)                // 将元素出栈    这里e要用指针->因为出栈有返回栈顶
{
        if(S->base == S->top)
        {
                printf("为空,不能弹出\n");
        }
        else
        {
                S->top--;
                *e = *(S->top);
        }
}

void initBitree(BiTree *T)                // 初始化树,即建造一棵空树   * 用来返回值
{
        *T = NULL;
        printf("空树构造成功。\n");
}

void CreatBitree(BiTree* T)                // 先序建立一个二叉树   *用来返回值   *T仍然是一个指针->因为BiTree本身是一个指针类型
{
        char c;
        scanf("%c", &c);
        if(c == '*')
        {
                *T = NULL;
        }
        else
        {
                *T = (BiTree)malloc(sizeof(BiNode));
                (*T)->data = c;                                // 生成的根节点里输入数据
                CreatBitree(&(*T)->lchild);                // 递归创建左子树
                CreatBitree(&(*T)->rchild);                // 递归创建右子树
        }
}

void initstack(Sqstack *S);
void inorderbitree(BiTree T)                // 中序遍历,非递归    没有改变树的结构 没必要用指针
{
        BiTree p = T;
        Sqstack S;
        initstack(&S);                        // 初始化栈,构造结点
        while(p || !emptystack(&S))
        {
                if(p)                        // 一直遍历到左子树的最下边 便遍历边入栈
                {
                        push(&S, p);
                        p = p->lchild;
                }
                else                        // 当p为空时,说明已经到达左子树最下边,此时需要出栈,并打印该结点
                {
                        pop(&S, &p);
                        printf("%c", p->data);
                        p = p->rchild;        // 进入右子树
                }
        }
}

void initstack(Sqstack *S)        // 初始化栈
{
        S->base = (BiTree*)malloc(sizeof(A));
        S->top = S->base;
        S->stacksize = A;
}

void initstack_ptr1(Sqstack **S)        // 初始化栈
{
        (*S) = malloc(sizeof(Sqstack));

        (*S)->base = (BiTree*)malloc(sizeof(A));
        (*S)->top = (*S)->base;
        (*S)->stacksize = A;
}

Sqstack *initstack_ptr2(void)        // 初始化栈
{
        Sqstack *s = malloc(sizeof(Sqstack));

        s->base = (BiTree*)malloc(sizeof(A));
        s->top = s->base;
        s->stacksize = A;
        return s;
}
int main(void)
{
        Sqstack S;
        initstack(&S);

        Sqstack *S1;
        initstack_ptr1(&S1);
        
        Sqstack *S2 = initstack_ptr2();
        
        /*Sqstack *S1 = NULL;
        initstack(S1);*/

        
        return 0;
}
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-5-21 23:57:21 | 显示全部楼层

回帖奖励 +1 鱼币

路过看看
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-5-25 19:26:02 | 显示全部楼层

回帖奖励 +1 鱼币

很详细,不错哦
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-7-10 16:04:30 | 显示全部楼层

回帖奖励 +1 鱼币

学习了
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-7-10 16:16:22 | 显示全部楼层

回帖奖励 +1 鱼币

学习学习
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-9-14 08:46:47 | 显示全部楼层

回帖奖励 +1 鱼币

支持楼主!楼主加油!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-9-16 17:33:09 | 显示全部楼层

回帖奖励 +1 鱼币

666
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-9-26 15:33:13 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-9-26 15:34:20 | 显示全部楼层

回帖奖励 +1 鱼币

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-10-7 16:22:12 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-10-9 21:42:38 | 显示全部楼层
学习
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-10-28 23:00:45 | 显示全部楼层

回帖奖励 +1 鱼币

学习一下··
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-10-30 11:54:37 | 显示全部楼层

回帖奖励 +1 鱼币

占楼..
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-12-23 08:33

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表