实验五：二叉树存储结构的实现原创

累行的博客 2020.01.05 06:49:14 阅读数：65

二叉树存储结构的实现

一、实验目的
1. 了解二叉树的基本结构，能够理解创建二叉树，添加、删除节点的操作。
2. 先读懂源程序，范例程序为完整地实现了相关功能的链表存储的二叉树。
3. 在已有算法的基础上设计函数，修改程序，1、求二叉树的根节点，2、按中序遍历二叉树，3、统计二叉树的叶子结点数量。

代码:

LinkBTree.h

#define TRUE 1                 
#define FALSE 0
#define LChild 1	//左儿子
#define RChild 2	//右儿子
#define isRootNode 1		//根结点
#define isNode 2			//一般结点
#define isLeafNode 3		//叶结点
#define isLeafAndRootNode 4	//既是根结点也是叶结点

struct Elem;
typedef struct Elem ElemType;   	//定义数据元素的数据类型
struct Elem
{	int KeyWord;	//关键字
	char ch;	    //数据域的定义，本实验设置了数据域只有一个字符数据
};

struct Node;
typedef struct Node *PNode;   	//定义结点指针类型，指向结点空间
typedef struct Node *PBTree;   	//定义二叉树指针类型
struct Node
{	ElemType DData;	    //结点数据
	PNode LLink;		//指向左儿子
	PNode RLink;		//指向左儿子
};



void Initiate(PBTree *PB);			//初始化为一棵空二叉树
void Destory(PBTree *PB);			//销毁一棵二叉树
int IsEmpty(PBTree PB);				//判断一棵二叉树是否是空
void Parent(PBTree PB,int KWord);   //求二叉树中关键字对应结点的父节点
void Clear(PBTree *PB);				//清除操作。将二叉树置为空树
void BeforeTraverse(PBTree PB);		//前序遍历，按广义表形式输出
int CountTreeHeight(PBTree PB);		//求树的高度

LinkBTree.c

#include "LinkBTree.h"
#include "stdio.h"
#include "stdlib.h"
int isHaveLeftChild(PNode pn);  //求二叉树中NodeNo结点是否有左儿子节点
int isHaveRightChild(PNode pn);  //求二叉树中NodeNo结点是否有右儿子节点
void OutNode(PNode pn);  //输出结点
PNode GetNodeFromKWord(PBTree PB,int KWord);  //根据关键字找结点
int NodeIs(PBTree PB,PNode pn); //判断结点类型

//判断结点类型
int NodeIs(PBTree PB,PNode pn) 
{	int isHaveLChild,isHaveRChild;
	
	isHaveLChild=isHaveLeftChild(pn);
	isHaveRChild=isHaveRightChild(pn);
	if(PB=pn)
	{	if(isHaveLChild==TRUE || isHaveRChild==TRUE)
			return isRootNode;
		else
			return isLeafAndRootNode;
	}

	if(isHaveLChild==TRUE || isHaveRChild==TRUE)
		return isNode;
	else
		return isLeafNode;
}

//根据关键字找结点
PNode GetNodeFromKWord(PBTree PB,int KWord)  
{//按前序遍历算法找结点
	PNode pn;
	pn=PB;
	if(pn==NULL)
		return NULL;
	else
	{	if(pn->DData.KeyWord==KWord)
			return pn;
		else
		{	pn=GetNodeFromKWord(pn->LLink,KWord);
			if(pn==NULL)
				pn=GetNodeFromKWord(pn->RLink,KWord);
			return pn;
		}
	}
}

//判断指定的关键字是否存在
int KWordIsExist(PNode pn,int KWord)
{//按前序遍历思路找关键字
	int isExist;
	if(pn==NULL)
	{	isExist=FALSE;
	}
	else
	{	if(pn->DData.KeyWord==KWord)
		{	isExist=TRUE;
		}
		else
		{	isExist=KWordIsExist(pn->LLink,KWord);
			if(isExist==FALSE)
				isExist=KWordIsExist(pn->RLink,KWord);
		}
	}
	return 	isExist;
}

//输入关键字
int InKeyWord(PBTree PB,int *KW)  
{//两个功能：1、输入一个关键字，2、输入的关键字在树中是否有
	int haveSameKWord;
	printf("请输入关键字（整数）：");
	fflush(stdin);
	scanf("%d",KW);
	haveSameKWord=KWordIsExist(PB,*KW);
	return haveSameKWord;
}

//输入结点数据
ElemType InData(PBTree PB)  
{	ElemType AData;
	int haveSameKWord;
	//关键字输入
	do
	{	haveSameKWord=InKeyWord(PB,&AData.KeyWord);
		if(haveSameKWord==TRUE)
			printf("关键字已有，关键字不能重复，请重新输入。\n");
		else
			break;
	}
	while(TRUE);

	//数据输入
	printf("请输入1个字符：");
	fflush(stdin);
	do
	{	AData.ch=getchar();
	}
	while(AData.ch==10);
	return AData;
}

//输入父结点
PNode InPNode(PBTree PB)  
{	int Empty;
	int isHaveKeyWord;
	int KWord;
	PNode pn;
	Empty=IsEmpty(PB);
	
	if(Empty==TRUE) //空树，不用询问用户了，一定是根节点
		return NULL;

	//要求输入的关键字必须在树中一定有
	do
	{	printf("请输入父结点关键字。");
		isHaveKeyWord=InKeyWord(PB,&KWord);
		if(isHaveKeyWord==TRUE)
		{	pn=GetNodeFromKWord(PB,KWord);
			return pn;
		}
		else
		{	printf("输入错误，请重新输入。\n");
		}
	}
	while(TRUE);
}

//确定选择的是左儿子还是右儿子
int InChildNode(PNode pn)  
{	int ChildNodeNo;
	do
	{	printf("请输入结点");
		OutNode(pn);
		printf("的子结点（1表示左儿子，2表示右儿子）:");
		scanf("%d",&ChildNodeNo);
		if(LChild==ChildNodeNo || RChild==ChildNodeNo)
		{	break;
		}
		else
		{	printf("输入错误，只能输入1或2，请重新输入。\n");
		}
	}
	while (TRUE);
	return ChildNodeNo;
}


//输出结点
void OutNode(PNode pn)  
{	if(pn!=NULL)
	{	printf("[");
		printf("%d",pn->DData.KeyWord);
		printf(",");
		printf("%c",pn->DData.ch);
		printf("]");
	}
}

//初始化为一棵空二叉树
void Initiate(PBTree *PB) 
{	*PB=NULL;
}

//产生一个结点空间
PNode CreateNodeSpace() 
{	PNode pn;
	pn=(PNode)malloc(sizeof(struct Node));
	if(pn==NULL)
		printf("申请空间失败！\n");
	
	return pn;
}

//将根结点放入树中 
void PutRootIntoPBree(PBTree *PB,ElemType AData)
{	PNode pn;
	pn=CreateNodeSpace();  
	if(pn!=NULL)
	{	pn->DData=AData;
		pn->LLink=NULL;
		pn->RLink=NULL;
		*PB=pn;
		printf("根结点插入成功！\n");
	}
	else
	{	printf("根结点插入失败！\n");
	}
}

//将结点数据以左（右）放入树中 
void PutNodeIntoPBree(PBTree *PB,PNode *ppn,int LR_Child,ElemType AData)
{	int isHaveThisChild;
	PNode pn;
	if(LR_Child==LChild)
		isHaveThisChild=isHaveLeftChild(*ppn);
	else
		isHaveThisChild=isHaveRightChild(*ppn);
	
	if(isHaveThisChild==TRUE)
	{	OutNode(*ppn);
		if(LR_Child==LChild)
			printf("结点已有左儿子，不能插入！\n");
		else
			printf("结点已有右儿子，不能插入！\n");
		return;
	}
	
	pn=CreateNodeSpace();
	if(pn!=NULL)
	{	pn->DData=AData;
		pn->LLink=NULL;
		pn->RLink=NULL;
		if(LR_Child==LChild)
			(*ppn)->LLink=pn;
		else
			(*ppn)->RLink=pn;
		printf("根结点插入成功！\n");
	}
	else
	{	printf("插入失败！\n");
	}
}

//销毁一棵二叉树
void  Destory(PBTree *PB)  
{//采用后序遍历算法销毁一棵二叉树
	PNode pn;
	if(*PB!=NULL)
	{	pn=*PB;
		if(pn!=NULL)
		{	Destory(&(pn->LLink));
			Destory(&(pn->RLink));
			free(pn);
		}
		*PB=NULL;
	}
}

//判断一棵二叉树是否是空
int IsEmpty(PBTree PB)  
{	if(PB==NULL)
		return TRUE;
	else
		return FALSE;
}


//获取指定结点的父结点
PNode GetParent(PBTree PB,PNode pn)
{//按前序遍历的思路找父结点
	PNode ppn;
	if(PB==NULL)
		return NULL;

	ppn=PB;
	if(ppn->LLink==pn || ppn->RLink==pn)
	{	return ppn;
	}
	else
	{	ppn=GetParent(ppn->LLink,pn);
		if(ppn==NULL)
			ppn=GetParent(ppn->RLink,pn);
		return ppn;
	}
}


//求二叉树中关键字对应结点的父节点
void Parent(PBTree PB,int KWord)  
{	PNode pn,ppn;
	pn=GetNodeFromKWord(PB,KWord);
	if(pn==PB)
	{	printf("因为该结点是二叉树的根节点，因此没有父节点！\n");
	}
	else
	{	ppn=GetParent(PB,pn);
		if(ppn!=NULL)
		{	printf("该结点的父节点是：");
			OutNode(ppn);
		}
		else
		{	printf("因为不存在这个结点，因此没有父节点！\n");	
		}
	}
}

//求二叉树中结点是否有左儿子节点
int isHaveLeftChild(PNode pn)  
{	if(pn!=NULL)
	{	if(pn->LLink==NULL)
			return FALSE;
		else
			return TRUE;
	}
	else
	{	printf("该结点不存在。\n");
		return -1;	
	}
}

//求二叉树中结点是否有右儿子节点
int isHaveRightChild(PNode pn)  
{	if(pn!=NULL)
	{	if(pn->RLink==NULL)
			return FALSE;
		else
			return TRUE;
	}
	else
	{	printf("该结点不存在。\n");
		return -1;	
	}
}

//以输出方式访问结点
void visit_OutNode(PNode pn)
{	OutNode(pn);
}


//前序遍历，按广义表形式输出
void BeforeTraverse(PBTree PB)  
{	PNode pn;
	pn=PB;
	printf("(");
	if(pn!=NULL)  
	{	visit_OutNode(pn);
		printf(",");
		BeforeTraverse(pn->LLink);
		printf(",");
		BeforeTraverse(pn->RLink);
	}
	printf(")");
}

//中序遍历，按广义表形式输出
void InTraverse(PBTree PB)  
{	PNode pn;
	pn=PB;
	printf("(");
	if(pn!=NULL)  
	{	
		InTraverse(pn->LLink);
		printf(",");
		visit_OutNode(pn);
		printf(",");
		InTraverse(pn->RLink);
	}
	printf(")");
}

//后序遍历，按广义表形式输出
void AfterTraverse(PBTree PB)  
{	PNode pn;
	pn=PB;
	printf("(");
	if(pn!=NULL)  
	{	
		AfterTraverse(pn->LLink);
		printf(",");
		AfterTraverse(pn->RLink);
		printf(",");
		visit_OutNode(pn);
	}
	printf(")");

}

//根节点 第一个就是根节点
void TreeRoot(PBTree PB){
	PNode pn;
	pn=PB;
	visit_OutNode(pn);
}

//二叉树的叶子结点数量
int count = 0;
//统计二叉树的叶子结点数量
void visit_CountNode(PBTree PB){
	PNode pn;
	pn=PB;
	if(pn!=NULL)  
	{
		int l = isHaveLeftChild(pn);
		int r = isHaveRightChild(pn);
		if(l == FALSE && r == FALSE){
			visit_OutNode(pn);
			count++;
		}	
		visit_CountNode(pn->LLink);
		visit_CountNode(pn->RLink);
	}
}
 
int visit_CountNodeHeight(int LChildHeight,int RChildHeight)
{	if(LChildHeight>RChildHeight)
		return 1+LChildHeight;
	else
		return 1+RChildHeight;
}

//求树的高度
int CountTreeHeight(PBTree PB)  
{//采取后序遍历的算法
	int LChildTreeHeight,RChildTreeHeight,TreeHeight;
	PNode pn;
	if(IsEmpty(PB)==TRUE)
	{	TreeHeight=0;
	}
	else
	{	pn=PB;
		LChildTreeHeight=CountTreeHeight(pn->LLink);	
		RChildTreeHeight=CountTreeHeight(pn->RLink);
		TreeHeight=visit_CountNodeHeight(LChildTreeHeight,RChildTreeHeight);
	}
	return TreeHeight; 
}

LinkBTreeUse.c

#include "LinkBTree.c"
#include "stdio.h"

//输入一个结点
void InPutNode(PBTree *PB)
{	ElemType AData;
	PNode ppn;
	int LR_Child;
	int ParentKW;
	int ParentKWisexist;
	AData=InData(*PB);
	if(IsEmpty(*PB)==TRUE)
	{	PutRootIntoPBree(PB,AData);
	}
	else
	{	do
		{	printf("请输入父结点的关键字，");
			ParentKWisexist=InKeyWord(*PB,&ParentKW);
			if(ParentKWisexist==TRUE)
				break;
			else
				printf("输入的父结点不存在，请重新输入父结点的关键字！\n");
		}while(TRUE);
		ppn=GetNodeFromKWord(*PB,ParentKW);
		LR_Child=InChildNode(ppn);
		PutNodeIntoPBree(PB,&ppn,LR_Child,AData);
	}
}

//前序遍历二叉树
void BeforeTraverseAct(PBTree PB)
{	printf("前序广义表：");
	BeforeTraverse(PB);
	printf("\n");
}

//中序遍历二叉树
void InTraverseAct(PBTree PB)
{	printf("中序广义表：");
	InTraverse(PB);
	printf("\n");
}

//后序遍历二叉树
void AfterTraverseAct(PBTree PB)
{	printf("后序广义表：");
	AfterTraverse(PB);
	printf("\n");
}

//找结点的父结点
void ParentAct(PBTree PB)
{	int KWord;
	int KWordIsExist;
	printf("请输入本结点的关键字。");
	KWordIsExist=InKeyWord(PB,&KWord);
	if(KWordIsExist==TRUE)
		Parent(PB,KWord);
	else
		printf("请输入的关键字没有对应的结点。\n");
}

//求二叉树的高度
void CountTreeHeightAct(PBTree PB)
{	int TreeHeight;
	TreeHeight=CountTreeHeight(PB);
	printf("树的高度是：%d\n",TreeHeight);
}


//销毁一棵二叉树
void DestoryAct(PBTree *PB)
{	Destory(PB);
	printf("销毁完毕！\n");
}


void main( )
{	PBTree PB;
	int SelNum;
	Initiate(&PB);
	do 
	{	printf("\n\n               菜  单\n");
		printf("**********请根据功能输入菜单编号**********\n");
		printf(" 1:插入一个结点\n");
		printf(" 2:求输入数据结点的双亲（父）结点\n");
		printf(" 3:按前序遍历二叉树\n");
		printf(" 31:按中序遍历二叉树\n");
		printf(" 32:按后序遍历二叉树\n");
		printf(" 33:求二叉树根节点\n");
		printf(" 34:统计二叉树的叶子结点数量\n");
		printf(" 4:求二叉树的高度\n");
		printf(" 0:退出\n");
		printf("\n请输入功能编号:");
		scanf("%d",&SelNum);
		switch (SelNum)
		{	case 0: printf("谢谢使用！\n");
					break;
			case 1: InPutNode(&PB);
					break;
			case 2: ParentAct(PB);
					break;
			case 3: BeforeTraverseAct(PB);
					break;
			case 31: InTraverseAct(PB);
					break;
			case 32: AfterTraverseAct(PB);
					break;
			case 33: TreeRoot(PB);
					break;
			case 34: visit_CountNode(PB);
					printf("二叉树的叶子结点数量:%d\n",count);
					break;
			case 4: CountTreeHeightAct(PB);
					break;
			default:printf("输入有错！请重新输入。\n");
		}
	}
	while (0!=SelNum); 
	Destory(&PB);
}

阅读全文

函数的形参改变，能改变实际参数吗？

湖二师寒暑假安排

没有更多推荐了 [去首页]

luolei

累行的博客

文章

376

原创

293

转载

翻译

访问量

183411

喜欢

粉丝

码龄

7年

资源

实验五：二叉树存储结构的实现 原创

文章目录

实验五：二叉树存储结构的实现原创