论坛 › 数据结构与算法 › 小白对二叉树非递归中序遍历的若干问题

仓鼠爱跑圈 发表于 2018-5-20 00:18:53

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

最近在学习二叉树非递归中序遍历，盗来的代码如下：
#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：严蔚敏的数据结构太晦涩难懂了。

在校大学生交流会

人造人 发表于 2018-5-20 02:11:17

PS：严蔚敏的数据结构的确太晦涩难懂了，不适合自学，推荐一个适合自学的《大话数据结构》
^_^

仓鼠爱跑圈 发表于 2018-5-20 08:11:26

人造人 发表于 2018-5-20 02:11
PS：严蔚敏的数据结构的确太晦涩难懂了，不适合自学，推荐一个适合自学的《大话数据结构》
^_^

谢谢dalao，那我那个想法有错吗，如果没错的话该怎么用指针定义S呢。我是看到他报错说没有初始化，我才把他NULL。。

人造人 发表于 2018-5-20 13:03:58

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

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



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

刘亮 发表于 2018-5-21 23:57:21

路过看看

qq171256018 发表于 2018-5-25 19:26:02

很详细，不错哦

独吟月上 发表于 2018-7-10 16:04:30

{:10_297:}学习了

xy123963 发表于 2018-7-10 16:16:22

学习学习

常德水鱼村 发表于 2018-9-14 08:46:47

支持楼主！楼主加油！

钱闻韬 发表于 2018-9-16 17:33:09

666

whdd 发表于 2018-9-26 15:33:13

{:9_226:}

whdd 发表于 2018-9-26 15:34:20

{:9_235:}

whdd 发表于 2018-10-7 16:22:12

{:9_226:}

余生愿你常欢笑 发表于 2018-10-9 21:42:38

学习

考拉熊 发表于 2018-10-28 23:00:45

学习一下··

helloconan 发表于 2018-10-30 11:54:37

占楼..

查看完整版本: 小白对二叉树非递归中序遍历的若干问题