创建二叉树的二叉链表存储结构_建立二叉树的二叉链表存储结构

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define MAXLEN 100

typedef char ElemType;
typedef char DataType;

//二叉链表存储结构
typedef struct BiTNode
{
	DataType data;
	struct BiTNode *lchild;
	struct BiTNode *rchild;
}BiTNode,*BiTree; //BiTNode为结点类型，BiTree为指向二叉链表结点的指针类型

//栈的数据类型
typedef BiTree QElemType;

//队列的顺序存储，循环队列的数据类型C语言描述

typedef struct
{
	int front;				//指向对头的位置
	int rear;				//指向对尾的下一个元素的位置
	int queueSize;			//队列的容量
	QElemType data[MAXLEN]; //存放对量数据元素的数组;
}SqQueue;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

//1.初始化操作
int initSqQueue(SqQueue *LQ)
{
	LQ->front=LQ->rear=0;
	LQ->queueSize=MAXLEN;
	return 1;
}

//2.判断队空
int SqQueueEmpty(SqQueue Q)
{
	if(Q.front==Q.rear)return 1;
	else return 0;
}

//4.得到队头
int SqGetHead(SqQueue Q,QElemType *e)
{
	if(Q.rear==Q.front)return 0;
	*e=Q.data[Q.front];
	return 1;
}

//5.进队列
int SqEnQueue(SqQueue *LQ,QElemType e)
{
	if((LQ->rear+1)%LQ->queueSize==LQ->front) return 0;
	LQ->data[LQ->rear]=e;
	LQ->rear=(LQ->rear+1)%LQ->queueSize;

	printf("after Enqueue %x:front %d,rear %d\n",e,LQ->front,LQ->rear);
	return 1;
}

//6.出队列
BiTree SqDeQueue(SqQueue *LQ,QElemType *e)
{
	if(LQ->front==LQ->rear) return 0;
	*e=LQ->data[LQ->front];
	LQ->front=(LQ->front+1)%LQ->queueSize;
	printf("after Dequeue %x:front %d,rear %d\n",*e,LQ->front,LQ->rear);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

//创建二叉树的二插链表存储结构，
//以左子树右子树的字符串形式读入的递归算法
//按先序遍历顺序读入每个节点值，创建二叉链表
void crt_tree(BiTree *T)
{
	char ch;
	scanf("%c",&ch);
	if(ch=='#') *T=NULL;
	else
	{
		*T=(BiTree)malloc(sizeof(BiTNode));
		(*T)->data=ch;
		crt_tree(&(*T)->lchild);
		crt_tree(&(*T)->rchild);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

//读入边创建二叉链表的非递归算法
//根据层次遍历，按从上到下，从左到右的顺序依次输入二叉树的边
//即读入边的信息(father,child,lrflag),其中father表示父结点
//child表示孩子结点，lrflag表示是左孩子还是右孩子，来建立二叉链表

//算法核心:
//1.每读入一条边，生成孩子结点，并作为叶子结点；之后
//将该结点的指针保存在队列中
//2,从对头指针找该结点的双亲结点指针。如果队头不是，出队列,
//直至队头是该结点的双亲节点。再按rlflag值建立双亲结点的左右孩子关系
void Create_BiTree(BiTree *T)
{
	SqQueue Q;
	BiTree p,s,t;
	char fa,ch,lrflag;
	initSqQueue(&Q);
	scanf("%c%c%c",&fa,&ch,&lrflag);
	while(ch!='#')
	{
		p=(BiTree)malloc(sizeof(BiTNode));
		p->data=ch;							//创建孩子结点
		p->lchild=p->rchild=NULL;			//做成叶子结点
		SqEnQueue(&Q,p);
		if(fa=='#') *T=p;					//建根结点
		else
		{
			 SqGetHead(Q,&s);				//取队列头元素
			 while(s->data!=fa)
			 {
				 SqDeQueue(&Q,&t);
				 SqGetHead(Q,&s);
			 }							//在队列中找双亲结点
			 if(lrflag=='0') s->lchild=p; //连接左孩子结点
			 else s->rchild=p;
		}
		scanf("%c%c%c",&fa,&ch,&lrflag);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

void preorder(BiTree T)
{
	if(T)
	{
		printf("%c",T->data);
		preorder(T->lchild);
		preorder(T->rchild);
	}
}
1
2
3
4
5
6
7
8
9

void layer(BiTree bt)
{
	BiTree p;
	SqQueue Q;
	initSqQueue(&Q);
	if(bt) SqEnQueue(&Q,bt);
	while(!SqQueueEmpty(Q))
	{
		SqDeQueue(&Q,&p);
		printf("%c\n",p->data);
		if(p->lchild) SqEnQueue(&Q,p->lchild);
		if(p->rchild) SqEnQueue(&Q,p->rchild);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

void main()
{
	BiTree T1=(BiTree)malloc(sizeof(BiTNode));
	BiTree T2=(BiTree)malloc(sizeof(BiTNode));
	crt_tree(&T1);
//	Create_BiTree(&T2);    //测试有问题，输入格式不知道用啥
	printf("先序遍历:");
//	preorder(T2);
	preorder(T1);printf("\n");
/*	//初始化一个二叉树，其根节点是A,没有左右孩子
	T->data='A';
	T->lchild=NULL;
	T->rchild=NULL;
//	inorder(T);
	printf("\n");

	T->lchild=(BiTree)malloc(sizeof(BiTNode));
	T->lchild->data='B';
	T->lchild->lchild=NULL;
	T->lchild->rchild=NULL;

	T->rchild=(BiTree)malloc(sizeof(BiTNode));
	T->rchild->data='C';
	T->rchild->lchild=NULL;
	T->rchild->rchild=NULL;
//	inorder(T);
	printf("\n");

	T->lchild->lchild=(BiTree)malloc(sizeof(BiTNode));
	T->lchild->lchild->data='D';
	T->lchild->lchild->lchild=NULL;
	T->lchild->lchild->rchild=(BiTree)malloc(sizeof(BiTNode));
	T->lchild->lchild->rchild->data='G';
	T->lchild->lchild->rchild->lchild=NULL;
	T->lchild->lchild->rchild->rchild=NULL;

	T->rchild->lchild=(BiTree)malloc(sizeof(BiTNode));
	T->rchild->lchild->data='E';
	T->rchild->lchild->lchild=NULL;
	T->rchild->lchild->rchild=NULL;
	T->rchild->rchild=(BiTree)malloc(sizeof(BiTNode));
	T->rchild->rchild->data='F';
	T->rchild->rchild->lchild=NULL;
	T->rchild->rchild->rchild=NULL;
*/	printf("层次遍历\n:");
	layer(T1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

运行结果

(3)由二叉树的遍历序列确定二叉树
①已知二叉树的先序序列和中序序列可唯一确定一棵二叉树，
若ABC是二叉树的先序序列，可画出5棵不同的二叉树

void CrtBT(BiTree *T,char pre[],char ino[],int ps,int is,in n)
{
	//pre为二叉树的先序序列，n是序列字符个数
	//ino是二叉树的中序序列
	//ps是先序序列的第一个字符的位置，初值为0
	//is是中序序列的第一个字符的位置，初值为0
	if(n==0) *T=NULL;
	else
	//在中序序列中查询根，k为-1，没有找到，否则k为根在中序序列中的位置
	{
		k=Search(ino,pre[ps]);
		if(k==-1)*T=NULL;
		else
		{
			if(!(*T=(BiTree)malloc(sizeof(BiTNode))))exit(0);
			(*T)->data=pre[ps];   //建立根结点
			if(k==is)(*T)->lchild=NULL;   //没有左子树
			else CrtBT(&(*T)->lchild,pre,ino,ps+1,is,k-is);//创建左子树
			if(k==is+n-1)(*T)->rchild=NULL;    //没有右子树
			else CrtBT(&(*T)->rchild,pre,ino,ps+1,k+1,n-(k-is)-1));//创建右子树
		}
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

②已知二叉树的后序序列和中序序列可唯一确定一棵二叉树，
③已知二叉树的先序序列和后序序列不能确定一棵二叉树，

（4）由原表达式创建儿叉链表
the contents is a little more,descript later…