#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#define MaxSize 100
typedef int DataType;
DataType all[19]={8,3,1,0,0,6,4,0,0,7,0,0,19,14,13,0,0,0,0};
int u=0;
typedef struct BiTNode
{
DataType data;
struct BiTNode *lchild;
struct BiTNode *rchild;
} *BiTree,BitNode;
typedef struct Queue{
int first;
BitNode*data[MaxSize];
int final;
}Queue;
void CreateBitTree(BiTree *T);
void PreOrderTraverse(BiTree T);
void InOrderTraverse(BiTree T);
void PostOrderTraverse(BiTree T);
void PreOrderTraverse2(BiTree T);
void InOrderTraverse2(BiTree T);
void PostOrderTraverse2(BiTree T);
void BinaryTreeLeveLOrder(BiTree T);
bool enQueue(Queue*& q,BitNode*& T);
bool deQueue(Queue*& q,BitNode*& T);
bool emptyQueue(Queue*& q);
int height(BiTree T);
int main()
{
BiTree T;
T=NULL;
int i=0;
printf("按先序序列输入二叉树中结点的值(一个整型)各数字用空格分开,整型0表示空树\n");
for(i=0;i<sizeof(all)/sizeof(int);i++)
printf("%d ",all[i]);
printf("\n");
CreateBitTree(&T);
printf("二叉树的递归先序序列:\n");
PreOrderTraverse(T);
printf("\n");
printf("二叉树的递归中序序列:\n");
InOrderTraverse(T);
printf("\n");
printf("二叉树的递归后序序列:\n");
PostOrderTraverse(T);
printf("\n");
printf("二叉树的非递归先序序列:\n");
PreOrderTraverse2(T);
printf("\n");
printf("二叉树的非递归中序序列:\n");
InOrderTraverse2(T);
printf("\n");
printf("二叉树的非递归后序序列:\n");
PostOrderTraverse2(T);
printf("\n");
printf("二叉树的层次遍历:\n");
BinaryTreeLeveLOrder(T);
printf("\n");
printf("二叉树的高度为:\n");
printf("%d\n",height(T));
}
void CreateBitTree(BiTree *T)
{
DataType ch;
ch=all[u];
u++;
if(ch==0)
*T=NULL;
else
{
*T=(BiTree)malloc(sizeof(BitNode));
if(!(*T))
exit(-1);
(*T)->data=ch;
CreateBitTree(&((*T)->lchild));
CreateBitTree(&((*T)->rchild));
}
}
void PreOrderTraverse(BiTree T)
{
if(T)
{
printf("%d ",T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}
void InOrderTraverse(BiTree T)
{
if(T)
{
InOrderTraverse(T->lchild);
printf("%d ",T->data);
InOrderTraverse(T->rchild);
}
}
void PostOrderTraverse(BiTree T)
{
if(T)
{
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
printf("%d ",T->data);
}
}
void PreOrderTraverse2(BiTree T)
{
BiTree stack[MaxSize];
int top=0;
BitNode *p;
p=T;
while(p!=NULL||top>0)
{
while(p!=NULL)
{
stack[top++]=p;
printf("%d ",p->data);
p=p->lchild;
}
if(top>0)
{
top--;
p=stack[top];
p=p->rchild;
}
}
}
void InOrderTraverse2(BiTree T)
{
BiTree stack[MaxSize];
int top=0;
BitNode *p;
p=T;
while(p!=NULL||top>0)
{
while(p!=NULL)
{
stack[top++]=p;
p=p->lchild;
}
if(top>0)
{
top--;
p=stack[top];
printf("%d ",p->data);
p=p->rchild;
}
}
}
void PostOrderTraverse2(BiTree T)
{
BiTree stack[MaxSize];
int top=0;
BitNode *p,*q;
p=T;
q=NULL;
while(p!=NULL||top>0)
{
while(p!=NULL)
{
stack[top++]=p;
p=p->lchild;
}
if(top>0)
{
p=stack[top-1];
if(p->rchild==NULL||p->rchild==q)
{
printf("%d ",p->data);
q=p;
p=NULL;
top--;
}
else
p=p->rchild;
}
}
}
bool enQueue(Queue*& q,BitNode*& T){
if(q->final==MaxSize-1){
return false;
}
q->final++;
q->data[q->final]=T;
return true;
}
bool deQueue(Queue*& q,BitNode*& T){
if(q->first==q->final){
return false;
}
q->first++;
T=q->data[q->first];
return true;
}
bool emptyQueue(Queue*& q){
if(q->first==q->final){
return true;
}
else{
return false;
}
}
void BinaryTreeLeveLOrder(BiTree T)
{
Queue *q;
int num;
q=(Queue*)malloc(sizeof(Queue));
q->first=q->final=-1;
if(T!=NULL){
enQueue(q,T);
}
while(emptyQueue(q)!=true){
deQueue(q,T);
printf("%d ",T->data);
if(T->lchild!=NULL){
enQueue(q,T->lchild);
}
if(T->rchild!=NULL){
enQueue(q,T->rchild);
}
}
}
int height(BiTree T)
{
BitNode *p;
p=T;
if(p==NULL)
return 0;
else
{
int lheight=height(p->lchild);
int rheight=height(p->rchild);
if(lheight>rheight)
return(lheight+1);
else return(rheight+1);
}
}