#include<stdio.h>
#include<malloc.h>
#define  MAXSIZE 20
typedef char TEelemtype;
typedef struct BiTNode{
TEelemtype data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

//队列的方式
typedef struct queueelem
{
BiTNode* b[MAXSIZE];
int front,rear;
}Queue;

//栈的方式
//栈的结构体表示形式
typedef struct stackelem
{
BiTNode* a[MAXSIZE];
int top;
}BtStack;

BiTree CreateBiTree()
{
char ch;
scanf("%c",&ch);
getchar();
if(ch!=‘#‘){

printf("输出当前节点的值：");
printf("%c\n",ch);
BiTree tree=(BiTree)malloc(sizeof(BiTNode));
tree->data=http://www.mamicode.com/ch;
tree->lchild=CreateBiTree();
tree->rchild=CreateBiTree();
return tree;
}else
return NULL;

}
//前序遍历二叉树
void PreOrderTraverse(BiTree T)
{

if(T)
{

printf("%c",T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}
//前序遍历非递归形式
void PreOrder(BiTree T)
{
BtStack bt;
bt.top=0;
if(T==NULL)
{
printf("此二叉树为空！");
}else
{
bt.a[bt.top++]=T;
while(bt.top>0)
{
printf("%c",bt.a[bt.top-1]->data);
BiTNode *bnode=bt.a[bt.top-1];
//   printf("  输出数值：%d",bt.top);
bt.top--;
//printf("右孩子节点的值：%c",bnode->rchild->data);
if(bnode->rchild!=NULL)
{
bt.a[bt.top]=bnode->rchild;
bt.top++;
//   printf("右孩子节点的值：%c",bnode->rchild->data);

}
if(bnode->lchild!=NULL)
{
bt.a[bt.top]=bnode->lchild;
//    printf("左孩子节点的值：%c",bnode->lchild->data);
bt.top++;

}

}

}

}

//中序遍历
void InOrderTraverse(BiTree T)
{
if(T)
{
InOrderTraverse(T->lchild);
printf("%c",T->data);
InOrderTraverse(T->rchild);
}

}

//中序遍历非递归的方式
void InOrder(BiTree T)
{
BtStack bt;
bt.top=0;
if(T==NULL)
{
printf("此二叉树为空！\n");

}else{
BiTNode *bnode=T;
//将首节点也放进去
bt.a[bt.top]=T;
bt.top++;
//先遍历完最左边子树的节点
while(bnode->lchild!=NULL)
{
bt.a[bt.top]=bnode->lchild;
bt.top++;
bnode=bnode->lchild;
}
//依次输出子树的节点
while(bt.top>0)
{
//输出节点
printf("%c",bt.a[bt.top-1]->data);
bnode=bt.a[bt.top-1];
bt.top--;
while(bnode->rchild!=NULL)
{
bt.a[bt.top]=bnode->rchild;
bt.top++;
bnode=bnode->rchild;
while(bnode->lchild!=NULL)
{
bt.a[bt.top]=bnode->lchild;
bt.top++;

}

}

}

}

}

//后序遍历
void  PostOrderTraverse(BiTree T)
{
if(T)
{
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
printf("%c",T->data);
}

}
//后序遍历非递归实现

void PostOrder(BiTree bt)
{
BtStack st;
st.top=-1;
BiTree t;
int flag;
do
{
while (bt!=NULL)
{
st.top++;
st.a[st.top]=bt;
bt=bt->lchild;
}
t=NULL;
flag=1;
while (st.top!=-1 && flag)
{
bt=st.a[st.top];
if (bt->rchild==t)  //t:表示为null，或者右子节点被访问过了。
{
printf("%c",bt->data);
st.top--;
t=bt;  //t记录下刚刚访问的节点
}
else
{
bt=bt->rchild;
flag=0;
}
}
} while (st.top!=-1);
}

//层序遍历
void LevelOrderTraverse(BiTree T)
{
Queue queue;
queue.front=queue.rear=0;

if(T==NULL)
{
printf("二叉树为空!\n");
}else{
queue.b[queue.rear] =T;
queue.rear=queue.rear+1;
while(queue.b[queue.front]!=NULL&&queue.rear!=queue.front)
{
printf("%c",queue.b[queue.front]->data);

//如果左孩子节点不为空，加入到队列中
if(queue.b[queue.front]->lchild!=NULL)
{

queue.rear=(queue.rear+1)%MAXSIZE;
queue.b[queue.rear]=queue.b[queue.front]->lchild;
}
if(queue.b[queue.front]->rchild!=NULL)
{

queue.rear=(queue.rear+1)%MAXSIZE;
queue.b[queue.rear]=queue.b[queue.front]->rchild;

}
queue.front=(queue.front+1)%MAXSIZE;//当前节点的队列加1

}
printf("%c",queue.b[queue.front]->data);

}

}
//获取二叉树的高度
int Height(BiTree T)
{
int dept1,dept2;
if(!T)
{
return 0;
}else{
dept1=Height(T->lchild);
dept2=Height(T->rchild);
if(dept1>dept2)
{
return dept1+1;
}else{
return dept2+1;
}
}
}

int main()
{

//创建二叉树
BiTree T=CreateBiTree();

//插入节点

//删除节点

//前序遍历
printf("前序遍历：\n");
PreOrderTraverse(T);
printf("\n");
//中序遍历
printf("中序遍历：\n");
InOrderTraverse(T);
printf("\n");

//后续遍历
printf("后序遍历：\n");
PostOrderTraverse(T);
printf("\n");

//获取二叉树的高度
printf("二叉树的高度：\n");
int hight=Height(T);
printf("%d\n",hight);

//层序遍历
printf("输出层序遍历的结果：");
LevelOrderTraverse(T);
printf("\n");

//前序遍历非递归方式
printf("按照前序非递归的方式进行遍历：");
PreOrder(T);
printf("\n");

//中序遍历非递归方式
printf("按照中序非递归的方式进行遍历：");
InOrder(T);
printf("\n");

//后序遍历非递归方式
printf("按照后序非递归的方式进行遍历：");
PostOrder(T);
printf("\n");

system("pause");
return 0;
}