注册 登录
编程论坛 数据结构与算法

关于二叉树非递归遍历是指针调用的问题

qq8801103 发布于 2010-05-21 20:00, 722 次点击
#define STACK_INIT_SIZE 100
#define STACKINCREMENT  10
#include <stdio.h>
#include <stdlib.h>
typedef char TElemType;
typedef struct BiTNode
{
    TElemType data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
typedef struct
{
    BiTree *base;
    BiTree *top;
    int stacksize;
}SqStack;
void initialStack(SqStack *s)
{
    s->base=(BiTree *)malloc(STACK_INIT_SIZE*sizeof(BiTree));
    if(!s->base) exit(0);
    s->top=s->base;
    s->stacksize=STACK_INIT_SIZE;
}
void Push(SqStack *s,BiTNode *e)
{
    if(s->top-s->base>=s->stacksize)
    {
        s->base=(BiTree *)realloc(s->base,(STACK_INIT_SIZE+STACKINCREMENT)*sizeof(BiTree));
        if(!s->base) exit(0);
        s->top=s->base+s->stacksize;
        s->stacksize+=STACKINCREMENT;
    }
    *(s->top)++=e;
}
void Pop(SqStack *s,BiTree *e)
{
    if(s->top==s->base) exit(0);
    *e=*--(s->top);
}
int GetTop(SqStack *s,BiTree *e)
{
    if(s->top==s->base) return(0);
    *e=*(s->top-1);
    return(1);
}
int StackEmpty(SqStack *s)
{
    if(s->base==s->top)
        return(1);
    else
        return(0);
}

void CreatBiTree(BiTree *T)
{
    TElemType ch;
    scanf("%c",&ch);  fflush(stdin);
    if(ch=='#')
    *T=NULL;
    else
    {
    *T=(BiTNode *)malloc(sizeof(BiTNode));
    if(!*T)
            exit(0);
    (*T)->data=ch;
    CreatBiTree(&(*T)->lchild);
    CreatBiTree(&(*T)->rchild);
    }

}

void Visit(char p)
{
    printf("%c",p);
}
void InOrderTraverse(BiTree T)
{
    SqStack S;
    BiTree p;
    initialStack(&S);
    p=T;
    while(p||!StackEmpty(&S))
    {
        if(p)
        {
            Push(&S,p);
            p=p->lchild;
        }
        else
        {
            Pop(&S,&p);
        Visit(p->data);
            p=p->rchild;
        }
    }
}
void main()
{
    BiTree *t;
    printf("jianlishu:\n");
    printf("shurijieidian:");
    CreatBiTree(t);
    printf("zhongshubianlidejieguowei:");
    InOrderTraverse(*t);
    printf("\n");
}

不理解在构建二叉树中和遍历的时候,请解释一下 详细一点
3 回复
#2
寒风中的细雨2010-05-22 12:15

void main()
{
    BiTree t;
    printf("jianlishu:\n");
    printf("shurijieidian:");
    CreatBiTree(&t);
    printf("zhongshubianlidejieguowei:");
    InOrderTraverse(t);
    printf("\n");
}
只有本站会员才能查看附件,请 登录

#3
xichong2010-05-22 18:25
建树返回的结果是根节点的指针,要让根节点的指针发生改变,就必须将指向树这种数据类型的指针变量BiTree t的地址即(&t传过去(此时函数中的形式参数类型为二级指针BiTree *T),即才能达到预期效果;也可以不传递参数,让建树函数void CreatBiTree()最后返回根节点的指针。
#4
qq88011032010-05-24 14:00
谢谢了  问一下2楼的那个  你的编程工具是什么  可以传上来吗
1