实验八 二叉树的建立及遍历应用

一、【实验目的】
1、掌握二叉树的建立方法

2、掌握二叉树遍历的基本方法（前序、中序、后序）

3、掌握递归二叉树遍历算法的应用

二、【实验内容】

1.构造一棵二叉树,树的形态如下图(亦见附件)所示，打印出先序遍历、中序遍历、后序遍历的遍历序列。

2.选择一种遍历方式计算该树中叶子结点的个数，并打印出叶子结点。

3.编写一个层序遍历算法，利用队列结构按层次（同一层自左至右）输出二叉树中所有的结点。

三、【实验源代码】

 #include<stdio.h>
#include<stdlib.h>
#define MaxQueueSize 100

typedef char ElemType;

typedef struct LBinaryTreeNode
{
	ElemType data;
	struct LBinaryTreeNode *lchild;
	struct LBinaryTreeNode *rchild;
}LPBTreeNode;

LPBTreeNode* createbintree(void)
{
	LPBTreeNode* pbnode;
	char ch;
	scanf("%c",&ch);
	if(ch=='#')
	{
		pbnode=NULL;
	}
	else
	{
		
		pbnode=(LPBTreeNode*)malloc(sizeof(LPBTreeNode));
		if(pbnode==NULL)
		{
			printf("Out of space!\n");
			return pbnode;
		}
		pbnode->data=ch;

		pbnode->lchild=createbintree();
		pbnode->rchild=createbintree();
		
	}
	//printf("1");//
	return pbnode;
}

void visit(LPBTreeNode* t)
{
	printf("%c",t->data);
	return;
}

void preorder(LPBTreeNode* t)
{
	if(t==NULL)
	{
		return;
	}
	visit(t);
	preorder(t->lchild);
	preorder(t->rchild);
}

void inorder(LPBTreeNode* t)
{
	if(t==NULL)
	{
		return;
	}
	
	inorder(t->lchild);
	visit(t);
	inorder(t->rchild);
}

void postorder(LPBTreeNode* t)
{
	if(t==NULL)
	{
		return;
	}
	
	postorder(t->lchild);
	postorder(t->rchild);
	
	visit(t);
}

int leafnum=0;//定义全局变量 

void leafcount(LPBTreeNode* t)//计算叶子结点数，采用先序遍历 
{
	
	if(t!=NULL)
	{
		if(t->lchild==NULL&&t->rchild==NULL)
		{
			leafnum++;
		}
		leafcount(t->lchild);
		
		leafcount(t->rchild);
	}
}
void getleaf(LPBTreeNode* t)//打印叶子结点 
{
	
	if(t!=NULL)
	{ 
		if(t->lchild==NULL&&t->rchild==NULL)
		{
			printf("%c ",t->data);
		}
		getleaf(t->lchild);
		
		getleaf(t->rchild);
	}
}

typedef struct
{
	ElemType queue[MaxQueueSize];
	int rear;
	int front;
	int count;
 } squeue;
 
 void QueueInitiate(squeue *q) 
 {
 	q->rear=0;
 	q->front=0;
 	q->count=0;
 }
 
void QueueAppend(squeue *q, LPBTreeNode* p)
{
	
	q->queue[q->rear] = p;
	q->rear = (q->rear + 1) % 100;
	q->count++;
}

int QueueNotEmpty(squeue* q)//队列为空返回0
{
	if (q->count == 0&& q->front== q->rear)
	{
		return 0;
	}
		
	return 1;
}
 
 int QueueTop(squeue *q,ElemType *d)
{
	if(q->count!=0)
	{
		*d=q->queue[q->front];
		return 1;
	}
	else
	{
		return 0;
	}	
 } 
 
 int  QueueDelete(squeue *q)
 {
 	if(q->count!=0)
 	{
 		q->front=(q->front+1)%MaxQueueSize;
 		q->count--;
 		return 1;
	 }
	 else
	 {
	 	return 0;
	 }
 }
 
void layorder(LPBTreeNode *root)
{
    LPBTreeNode *t;
    squeue myqueue;
    QueueInitiate(&myqueue);
    QueueAppend(&myqueue, root);  //入根节点
    while (QueueNotEmpty(&myqueue))  //队列不为空，重复出队列，入队列
    {
        QueueTop(&myqueue, (void **)&t);
        printf("%c ", t->data);
        if (t->lchild)    //入孩子
        {
            QueueAppend(&myqueue, t->lchild);
        }
        if (t->rchild)
        {
            QueueAppend(&myqueue, t->rchild);
        }
        QueueDelete(&myqueue);   //头删，出队列
    }
}

int main()
{
	LPBTreeNode *t;
	printf("请输入二叉树的元素："); 
	t=createbintree();//需要将 createbintree 的返回值赋给 t，否则 t 将是一个未初始化的指针。
	printf("先序遍历的结果为：");
	preorder(t);
	printf("\n");
	printf("中序遍历的结果为：");
	inorder(t);
	printf("\n");
	printf("后序遍历的结果为：");
	postorder(t);
	leafcount(t);
	printf("\n");
	printf("叶子结点数为：%d",leafnum);
	printf("\n");
	printf("叶子结点分别为：");
	getleaf(t);
	printf("\n");
	printf("层序遍历的结果为：");
	layorder(t);
	
	return 0;
 } 

四、【实验结果】

五、【实验心得】
1、难点一：计算叶子结点数。采用递归思想，叶子结点的特点就是不含左右孩子，所以当根节点不为空且没有左右孩子的情况下，该结点为叶子结点。
2、难点二：层序遍历输出所有结点。层序遍历，需要借助队列数据结构，先把根节点入队列，依次出队列，每次出一个数据，就带节点的孩子入队列（先入左孩子，后入右节点），直到全部节点出过队列，队列为空，循坏结束，层序遍历完成。