用C语言实现二叉树的结构和常用操作

￡神魔★判官ぃ 2022-05-20 05:42 97阅读 0赞

二叉树结构，和一些基本操作：

#include<stdio.h>
    #include<stdlib.h>
    
    
    typedef float ElemType;
    typedef struct BiTNote
    {
    	struct BiTNote* parent;
    	struct BiTNote* lchild;
    	struct BiTNote* rchild;
    	ElemType data;
    
    }BiTNode;
    
    /***********************函数定义函数定义定*****************************/
    //
    /**统计总结点数**/
    int NodeCount(BiTNode *root)
    {
    	int Count=0,LCount=0,RCount=0;
    	if(root==NULL)
    		return 0;
    	/*递归方法统计*/
    	LCount=NodeCount(root->lchild);//左子树结点数
    	RCount=NodeCount(root->rchild);//右子树结点数
    
    	Count=LCount+RCount+1;//左子树+右子树+根结点
    	return Count;
    }
    
    //
    /**向二叉树中插入结点**/
    void InsertIntoBitTree(BiTNode **root,ElemType data)
    {
    	/*创建新结点保存待插入的data*/
    	BiTNode *newNode=(BiTNode*)malloc(sizeof(BiTNode));
    	newNode->data=data;
    	newNode->lchild=NULL;
    	newNode->rchild=NULL;
    	//考虑到 当输入是空树时 需要改变根结点（BiTNode *root）的值，所以这里要求输入根节点的地址（BiTNode **root类型）
    	if(*root==NULL)//说明是空树
    		{
    			*root=newNode;//将新结点的指针newNode赋值给根结点的指针
    			(*root)->parent=NULL;
    			(*root)->lchild=NULL;
    			(*root)->rchild=NULL;
    		}
    	else if((*root)->lchild==NULL)
    	{
    		/*左子树为空 则将新结点newNode的指针赋值给左子树结点的指针*/
    		(*root)->lchild=newNode;
    		(*root)->lchild->parent=*root;//左子树的父节点为根结点
    		
    	}
    		
    	else if((*root)->rchild==NULL)
    	{
    		/*右子树为空 则将新结点newNode的指针赋值给右子树结点的指针*/
    		(*root)->rchild=newNode;
    		(*root)->rchild->parent=*root;//右子树的父节点为根结点
    	}
    	
    	/*如果根节点、左右子树都不为空 递归向左子树插入data*/	
    	/*这样构造的树的特点是：根结点的右子树只有一个结点*/
    	else
    		InsertIntoBitTree(&((*root)->lchild),data);
    	
    }
    //
    /*向二叉树中有序插入数据满足：根结点的数据域大于左结点并且小于右结点*/
    void OrderInsert(BiTNode **root,ElemType data)
    {
    	/*创建新结点保存待插入的data*/
    	BiTNode *newNode=(BiTNode*)malloc(sizeof(BiTNode));
    	newNode->data=data;
    	newNode->lchild=NULL;
    	newNode->rchild=NULL;
    	//考虑到 当输入是空树时 需要改变根结点（BiTNode *root）的值，所以这里要求输入根节点的地址（BiTNode **root类型）
    	if(*root==NULL)//说明是空树
    		{
    			*root=newNode;//将新结点的指针newNode赋值给根结点的指针
    			(*root)->parent=NULL;
    			(*root)->lchild=NULL;
    			(*root)->rchild=NULL;
    		}
    		
        	else//不是空树
    	{
    		BiTNode *node=(BiTNode*)malloc(sizeof(BiTNode));
    		BiTNode *parent=(BiTNode*)malloc(sizeof(BiTNode));
    		//BiTNode *node,*parent;
    		node=(*root);
    		parent=(*root);
    		while(node!=NULL)
    		{
    			parent=node;
    			if(node->data==data)
    			{printf("data to insert aleady exist");exit(-1);}
    			if(node->data>data)
    				node=node->lchild;
    			else
    				node=node->rchild;
    		}
    		
    		if(data>parent->data)
    			parent->rchild=newNode;
    		else
    			parent->lchild=newNode;
    			
    	}
    		
    }
    
    
    
    //
    /*先序遍历并输出:根结点 左 右*/
    void PrePrint(BiTNode *root)
    {
    	if(root==NULL)
    	{
    		printf("invalid PrePrint");
    		exit(-1);
    	}
    	printf("%f\t",root->data);
    	if(root->lchild!=NULL)
    	PrePrint(root->lchild);
    	if(root->rchild!=NULL)
    	PrePrint(root->rchild);
    	  
    }
    
    //
    /*中序遍历并输出：左 根结点 右*/
    void MidPrint(BiTNode *root)
    {
    	if(root==NULL)
    	{
    		printf("invalid MidPrint");
    		exit(-1);
    	}
    	if(root->lchild!=NULL)
    	MidPrint(root->lchild);
    	printf("%f\t",root->data);
    	if(root->rchild!=NULL)
    	MidPrint(root->rchild);
    	
    }
    
    //
    /*后续遍历并输出：左 右 跟结点*/
    void PostPrint(BiTNode *root)
    {
    	if(root==NULL)
    	{
    		printf("invalid MidPrint");
    		exit(-1);
    	}
    	if(root->lchild!=NULL)
    	PostPrint(root->lchild);
    	if(root->rchild!=NULL)
    	PostPrint(root->rchild);
    	printf("%f\t",root->data);
    	
    }
    
    //
    /*统计叶子结点数*/
    int LeafNodeNum(BiTNode *root)
    {
    	int num=0;
    	if((root->lchild==NULL)&&(root->rchild==NULL))//说明该结点是叶子结点
    		++num;
    	else if((root->lchild!=NULL)&&((root->rchild!=NULL)))//分别对左、右子树递归操作
    		{
    			num=num+LeafNodeNum(root->lchild);
    			num=num+LeafNodeNum(root->rchild);
    		}
    	else if (root->lchild!=NULL)//左子树递归操作
    		num=num+LeafNodeNum(root->lchild);
    	else 
    		num=num+LeafNodeNum(root->rchild);//右子树递归操作
    	
    	return num;
    }
    
    //
    /*从左到右输出叶子结点 返回叶子结点个数*/
    int LeafNodePrint(BiTNode *root)
    {
    	int  num=0;
    	BiTNode *p=root;
    	if((p->lchild==NULL)&&(p->rchild==NULL))//说明该结点是叶子结点
    	{
    		printf("%f\t",p->data);
    		++num;
    	}
    	else if((p->lchild!=NULL)&&((p->rchild!=NULL)))//分别对左、右子树递归操作
    	{
    		num+=LeafNodePrint(root->rchild);
    		num+=LeafNodePrint(root->lchild);
    	
    	}
    	else if( (p->lchild!=NULL))
    		num+=LeafNodePrint(root->lchild);//左子树递归操作
    	else
    		num+=LeafNodePrint(root->rchild);//右子树递归操作
    	return num;
    }
    
    //
    /*统计高度*/
    int Height(BiTNode *root)
    {
    	int lh=1,rh=1;
    	if(root==NULL)
    		return 0;
    	lh+=Height(root->lchild);
    	rh+=Height(root->rchild);
    	return lh>=rh?lh:rh;
    	
    	
    }
    
    //
    /*销毁树*/
    void destory(BiTNode *root)
    {
    	if((root->lchild==NULL)&&(root->rchild==NULL))//free叶子结点
    		free(root);
    	else if((root->lchild!=NULL)&&((root->rchild!=NULL)))//分别对左、右子树递归操作
    	{
    		destory(root->lchild);
    		destory(root->rchild);
    		free(root);//销毁根结点
    	}
    	else if(root->lchild!=NULL)//左子树递归操作
    		{
    			destory(root->lchild);
    			free(root);//销毁根结点
    		}
    	else						//右子树递归操作
    		{
    			destory(root->rchild);
    			free(root);//销毁根结点
    		}
    
    }
    
    /*******************************************下面是主函数***********************************************/
    int main()
    {
    		BiTNode *MyTree=NULL;//定义根结点 初始化为空
    		/***向二叉树中插入子节点***/
    		InsertIntoBitTree(&MyTree,1);
    		InsertIntoBitTree(&MyTree,2);
    		InsertIntoBitTree(&MyTree,3);
    		InsertIntoBitTree(&MyTree,4);
    		InsertIntoBitTree(&MyTree,5);
    		printf("node numbers: %d\n",NodeCount(MyTree));//输出已构造二叉树的结点数
    		printf("height:%d\n",Height(MyTree));//输出已构造二叉树的高度
    		printf("PreOder Ouput:\n");
    		PrePrint(MyTree);//按前序访问顺序 输出树的结点
    		printf("MidOder Ouput:\n");
    		MidPrint(MyTree);//按中序访问顺序 输出树的结点
    		printf("PostOder Ouput:\n");
    		PostPrint(MyTree);//按后序访问顺序 输出树的结点
    		printf("Leaf Node %d:\n",LeafNodeNum(MyTree));
    		LeafNodePrint(MyTree);
    		destory(MyTree);//释放树的内存 销毁树
    		return 0;			
    }