4.1.c

来自「自己写的数据结构课程程序」· C语言 代码 · 共 81 行

#define NULL 0
#include<stdio.h>
struct BiTNode
{char data;
 struct BiTNode *lchild,*rchild;
};
struct Node
{struct BiTNode *bitnode;
 struct Node *next;
};
struct Stack
{struct Node *base,*top;
};
struct BiTNode *p;
struct Stack S;
struct BiTNode *CreatBitree(struct BiTNode *T)
{char c;
 scanf("%c",&c);
 if(c==' ')
   T=NULL;
 else
   {T=(struct BiTNode*)malloc(sizeof(struct BiTNode));
    T->data=c;
    T->lchild=CreatBitree(T->lchild);
    T->rchild=CreatBitree(T->rchild);
   }
 return T;
}
void Visit(int elem)
{printf("%c",elem);
}
void InitStack()
{S.base=S.top=NULL;
}
void Push(struct BiTNode *t)
{struct Node *p;
 p=(struct Node *)malloc(sizeof(struct Node));
 p->next=NULL;
 S.top->bitnode=t;
 S.top->next=p;
 S.top++;
}
int StackEmpty()
{if(S.top==S.base)
   return 1;
 else
   return 0;
}
int GetTop()
{if(S.top==S.base)
   return 0;
 else
   {p=(S.top-1)->bitnode;
    return 1;
   }
}
void Pop()
{p=(--S.top)->bitnode;
}
void InOrderTraverse(struct BiTNode *T)
{InitStack();
 Push(T);
 while(!StackEmpty())
  {while(GetTop()&&p)
     Push(p->lchild);
   Pop();
   if(!StackEmpty())
   {Pop();
    Visit(p->data);
    Push(p->rchild);
   }
  }
}
void main(void)
{struct BiTNode *T;
 T=CreatBitree(T);
 InOrderTraverse(T);
 getchar();
 getchar();
}