#include<stdio.h>
#include<stdlib.h>
//二叉树结点
typedef struct Bitnode{
char data;
struct Bitnode *lchild,*rchild;
}*Bitree;
//链表结点
typedef struct Node{
char data;
int lchild;
int rchild;
}node;
node Array[100];
static int length=0;
const int MaxLength=100;
//创建二叉树
void CreateBitree(Bitree &t)
{
char ch;
scanf("%c",&ch);
if(ch=='#')
t=NULL;
else
{
t=(Bitnode *)malloc(sizeof(Bitnode));
t->data=ch;
CreateBitree(t->lchild);
CreateBitree(t->rchild);
}
}
//前序遍历
void inordertraverse(Bitree t)
{
if(t)
{
printf("%c",t->data);
length++;
Array[length].data=t->data;
inordertraverse(t->lchild);
inordertraverse(t->rchild);
}
}
//后序遍历
void postordertraverse(Bitree t)
{
if(t)
{
inordertraverse(t->lchild);
inordertraverse(t->rchild);
printf("%c",t->data);
}
}
//层次遍历
void Leveltaverse(Bitree t)
{
Bitree Q[MaxLength];
int front=0,rear=0;
Bitree p;
if(t){
Q[rear]=t;
rear=(rear+1)%MaxLength;
}
while(front!=rear){
p=Q[front];
front=(front+1)%MaxLength;
printf("%c",p->data);
if(p->lchild){
Q[rear]=p->lchild;
rear=(rear+1)%MaxLength;
}
if(p->rchild){
Q[rear]=p->rchild;
rear=(rear+1)%MaxLength;
}
}
}
//二叉树链表
void Bitreelist(Bitree t)
{
int i,j;
if(t)
{
j=1;
while(t->data!=Array[j].data)
j++;
if(t->lchild!=NULL)
{
i=1;
while(t->lchild->data!=Array[i].data)
i++;
Array[j].lchild=i;
}
else
Array[j].lchild=0;
if(t->rchild!=NULL)
{
i=1;
while(t->rchild->data!=Array[i].data)
i++;
Array[j].rchild=i;
}
else
Array[j].rchild=0;
Bitreelist(t->lchild);
Bitreelist(t->rchild);
}
}
int main()
{
Bitree t1;
printf("请输入二叉树结点值：");
CreateBitree(t1);
printf("\n");
printf("二叉树先序遍历：");
inordertraverse(t1);
printf("\n");
printf("二叉树后序遍历：");
postordertraverse(t1);
printf("\n");
printf("二叉树层次遍历：");
Leveltaverse(t1);
printf("\n");
printf("\n");
Bitreelist(t1);
printf("二叉树的静态二叉链表为：\n");
printf("下标\tlchil\tdata\trchild\n");
for(int j=1;j<=length;j++)
{
printf("%d\t%d\t%c\t%d\n", j,Array[j].lchild, Array[j].data, Array[j].rchild);
}
return 0;
}
//ABD##E##CFH###G##