binarytree.c

#include"stack.h"
#include<stdlib.h>
#include<stdio.h>
void CreateBiTree(BiTree **bitree,int i)//初始的时候输入i=0;
{
    //i++;
    //if(i==3||i==4||i==8||i==10||i==11||i==13||i==14||i==15)
    //bitree=NULL;

    //先序建树
    int num;
    printf("input");
    scanf("%d",&num);
    if(num==0)
    *bitree=NULL;
    else
    {
        (*bitree)=(BiTree *)malloc(sizeof(BiTree));
        (*bitree)->e=num;
        CreateBiTree(&((*bitree)->lchild),i);
        CreateBiTree(&((*bitree)->rchild),i);
    }

    
}
void InOrderTraverse(BiTree *bitree)
{
    SeqStack *stack=(SeqStack *)malloc(sizeof(SeqStack));
    InitSeqStack(stack);
    //BiTree *bitreeTemp=bitree;
    //BiTree *bitreeEmpty=(BiTree *)malloc(sizeof(BiTree));
    while(bitree||stack->size!=0)
    {
        if(bitree)
        {
           // *bitreeTemp;
           // *stack;
           stack->bitree[stack->size++]=*bitree;
           bitree=bitree->lchild;
        }
        else
        {
            //SeqStackPush(stack,*bitreeTemp);
            //SeqStackTop(stack,bitree);
            bitree=&(stack->bitree[stack->size-1]);
            //SeqStackPop(stack);
            stack->size--;
            printf("%d|",bitree->e);
            bitree=bitree->rchild;
        }
    }
    //free(bitreeEmpty);
}

binarytree.h

typedef struct BiTree
{
    struct BiTree *lchild;
    struct BiTree *rchild;
    int e;   
}BiTree;

void CreateBiTree(BiTree **bitree,int i);
void InOrderTraverse(BiTree *bitree);

main.c

#include"stack.h"
#include<stdlib.h>
#include<stdio.h>
int main()
{
    BiTree *bitree=(BiTree *)malloc(sizeof(BiTree));
    //BiTree *bitree=NULL;
    CreateBiTree(&bitree,0);
    InOrderTraverse(bitree);
    printf("完成");
}

stack.c

#include"stack.h"
#include<stdlib.h>
//顺序栈，没有实际的删东西，只是通过改变栈顶位置size
void InitSeqStack(SeqStack *stack)//通过size来判断栈顶
{
    if(stack==NULL)
    {
        return;
    }

    stack->size=0;
    stack->capacity=1000;
    stack->bitree=(BiTree *)malloc(sizeof(BiTree)*(stack->capacity));//一次分配1000个位置
    //连续空间，之后通过下标（size)直接访问栈顶
}
void SeqStackPush(SeqStack *stack,BiTree bitree)//尾插入栈
{
    if(stack==NULL)
    {
        return;
    }
    if(stack->size>=stack->capacity)
    {
        return;
    }
    stack->bitree[stack->size++]= bitree;
    return;
}
void SeqStackPop(SeqStack * stack)
{
    if(stack==NULL)
    {
        return;
    }
    if(stack->size==0)
    {
        return;
    }
    --stack->size;
}
int SeqStackTop(SeqStack *stack,BiTree *bitree)
{
    if(stack==NULL||bitree==NULL)
    {
        return -1;
    }

    if(stack->size==0)
    {
        return -1;
    }

    *bitree=stack->bitree[stack->size-1];
    return 0;
}

stack.h

#include"binarytree.h"
typedef struct SeqStack
{
    BiTree * bitree;
    int size;
    int capacity;
}SeqStack;
void InitSeqStack(SeqStack *stack);
void SeqStackPush(SeqStack *stack,BiTree bitree);//尾插入栈;
void SeqStackPop(SeqStack * stack);
int SeqStackTop(SeqStack *stack,BiTree *bitree);