二叉树链表

[c++]代码库

#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##