#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#define MAXSIZE 50 //定义栈中元素的最大个数
typedef struct BiTree{
int data;
struct BiTree *lchild;
struct BiTree *rchild;
}BiTree;
typedef struct{
BiTree data[MAXSIZE]; // 存放栈中元素
int top; //栈顶指针
}SqStack;
//初始化栈
void Init_SqStack(SqStack &S){
S.top = -1;
return;
}
//1. Top值不能超过MaxSize
//2. 空栈的判定条件通常定为top == -1，满栈的判定条件通常为top == MaxSize - 1，栈中数据元素个数为top + 1
//判空
bool StackEmpyt(SqStack S){
if (S.top == -1) return true;
else return false;
}
//进栈
void Push(SqStack &S, BiTree x){ //&s引用，对原对象操作，s与原对象属性相同的对象
if (S.top == MAXSIZE - 1){
printf("Fulled");
return;
}
S.data[++S.top] = x;
}
//出栈
BiTree Pop(SqStack &S){ // 把出栈的值赋给x，所以引用x
if (S.top == -1){
printf("Empty");
return;
}
BiTree x = S.data[S.top--];
return x;
}
//读取栈顶元素
bool GetTop(SqStack S, BiTree &x){ // 把出栈的值赋给x，所以引用x
if (S.top == -1){
printf("Empty");
return false;
}
x = S.data[S.top];
return true;
}
//非递归先序遍历
void PreOrderTravers(BiTree *b){
SqStack S;
Init_SqStack(S);
BiTree *p = b; // 工作指针
while (p || !StackEmpyt(S)){
while (p){ // 先一路中间结点压栈直到最左边的一个结点
printf("%d ", p->data);
Push(S, *p);
p = p->lchild;
}
if (!StackEmpyt(S)){
*p = Pop(S);
p = p->rchild;
}
}
}
// 非递归中序遍历
void PreOrderTraverse(BiTree *b){
SqStack S;
Init_SqStack(S);
BiTree *p = b; // 工作指针
while (p || !StackEmpyt(S)){ // 当结点不空或者栈不空，因为一开始栈是空的，没有p这个条件执行不了
while (p){ // 中序先将结点进栈保存
Push(S, *p);
p = p->lchild;
}
// 遍历到左下角尽头再出栈访问
*p = Pop(S);
printf("%d ", p->data);
p = p->rchild;
}
}
