数据结构之树和二叉树---二叉树的基本操作

灰太狼 2022-08-03 12:53 229阅读 0赞

问题：二叉树的基本操作函数，主要内容为二叉树的数据结构，初始化二叉树，销毁二叉树，创建二叉树，求二叉树深度，二叉树双亲节点，二叉树左孩子，二叉树右孩子，二叉树左兄弟，二叉树右兄弟，根据名称查找二叉树节点，插入节点及删除节点

//二叉树数据结构

typedef struct BiTNode
    {
    	TElemType data;
    	struct BiTNode* lchild, * rchild;
    }BiTNode, *BiTree;

//初始化二叉树

FILE* BTEF;
    BiTree InitBiTree()
    {
    	BiTree bt;
    	bt = NULL;
    	BTEF = fopen("BiTreeElem.txt", "r");
    	return bt;
    }

//销毁二叉树

void DestroyBiTree(BiTree bt)
    {
    	if(bt)
    	{
    		DestroyBiTree(bt->lchild);
    		DestroyBiTree(bt->rchild);
    		free(bt);
    	}
            fclose(BTEF);
    }

//创建二叉树

//通过文本文件读取二叉树节点信息，空节点以“0”表示，节点顺序为二叉树先序遍历顺序

void CreatBiTree(BiTree *bt)
    {
    	char node;
    
    	fread(&node, sizeof(char), 1, BTEF);
    	if(node==' ')
    		fread(&node, sizeof(char), 1, BTEF);
    
    	if(node=='0')
    		*bt = NULL;
    	else
    	{
    		if(*bt==NULL)
    			*bt = (BiTree) malloc (sizeof(BiTNode));
    		(*bt)->data = node;
    		(*bt)->lchild = NULL;
    		(*bt)->rchild = NULL;
    		CreatBiTree(&(*bt)->lchild);
    		CreatBiTree(&(*bt)->rchild);
    	}
    }

//文本信息样例

/\*A B D 0 F 0 0 0 C 0 E G 0 0 0\*/

//求二叉树深度

int BiTreeDepth(BiTree bt)
    {
    	int leftBTDepth, rightBTDepth;
    
    	if(bt==NULL)
    		return 0;
    	else
    	{
    		leftBTDepth = BiTreeDepth(bt->lchild)+1;
    		rightBTDepth = BiTreeDepth(bt->rchild)+1;
    		return leftBTDepth>rightBTDepth? leftBTDepth:rightBTDepth;
    	}
    }

//二叉树双亲节点

//查找信息的依据是节点名称，返回值为节点指针

BiTNode* BiTreeParent(BiTree bt, TElemType elem)
    {
    	BiTNode* btn;
    	if(bt!=NULL)
    	{
    		if (bt->lchild!=NULL)
    		{
    			if(bt->lchild->data!=elem)
    			{
    				btn = BiTreeParent(bt->lchild,elem);
    				if(btn!=NULL)
    					return btn;
    			}
    			else
    				return bt;
    		}
    		if (bt->rchild!=NULL)
    		{
    			if(bt->rchild->data!=elem)
    				return BiTreeParent(bt->rchild,elem);
    			else
    				return bt;
    		}
    	}
    	return NULL;
    }

//二叉树左孩子

BiTNode* LeftChild(BiTree bt, TElemType elem)
    {
    	BiTNode* tbn;
    	if(bt!=NULL)
    	{
    		if(bt->data==elem)
    			return bt->lchild;
    		else
    		{
    			tbn = LeftChild(bt->lchild, elem);
    			if(tbn!=NULL)
    				return tbn;
    			return LeftChild(bt->rchild, elem);
    		}
    	}
    	return NULL;
    }

//二叉树右孩子

BiTNode* RightChild(BiTree bt, TElemType elem)
    {
    	BiTNode* tbn;
    	if(bt!=NULL)
    	{
    		if(bt->data==elem)
    			return bt->rchild;
    		else
    		{
    			tbn = RightChild(bt->lchild, elem);
    			if(tbn!=NULL)
    				return tbn;
    			return RightChild(bt->rchild, elem);
    		}
    	}
    	return NULL;
    }

//二叉树左兄弟

BiTNode* LeftSibling(BiTree bt, TElemType elem)
    {
    	BiTNode *tbn;
    	if(bt==NULL)
    		return NULL;
    	if (bt->rchild!=NULL)
    	{
    		if(bt->rchild->data==elem)
    			return bt->lchild;
    		else
    		{
    			tbn = LeftSibling(bt->rchild, elem);
    			if(tbn!=NULL)
    				return tbn;
    		}
    	}
    	 return LeftSibling(bt->lchild, elem);
    }

//二叉树右兄弟

BiTNode* RightSibling(BiTree bt, TElemType elem)
    {
    	BiTNode *tbn;
    	if(bt==NULL)
    		return NULL;
    	if (bt->lchild!=NULL)
    	{
    		if(bt->lchild->data==elem)
    			return bt->lchild;
    		else
    		{
    			tbn = RightSibling(bt->lchild, elem);
    			if(tbn!=NULL)
    				return tbn;
    		}
    	}
    	return RightSibling(bt->rchild, elem);
    }

//根据名称查找二叉树节点

BiTNode* SearchNode(BiTree bt, TElemType elem)
    {
    	BiTNode *tbn;
    	if(bt==NULL)
    		return NULL;
    	if(bt->data==elem)
    		return bt;
    	else
    	{
    		tbn = SearchNode(bt->lchild, elem);
    		if(tbn!=NULL)
    			return tbn;
    		return SearchNode(bt->rchild, elem);
    	}
    	return NULL;
    }

//插入节点

//插入节点时，需要插入节点或子树指针，插入节点双亲名称，及作为双亲节点的左孩子还是右孩子

int InsertChild(BiTree bt, TElemType elem, int LR, BiTree child)
    {
    	BiTNode* pn;
    	if (!child||!bt||(LR!=0&&LR!=1))
    		return -1;
    	if (LR==0)
    	{
    		pn = LeftChild(bt, elem);
    		if(pn==NULL)
    			SearchNode(bt, elem)->lchild = child;
    		else
    			return -1;
    	} 
    	else
    	{
    		pn = RightChild(bt, elem);
    		if(pn==NULL)
    			SearchNode(bt, elem)->rchild = child;
    		else
    			return -1;
    	}
    	return 0;
    }

//删除节点

int DeleteChild(BiTree bt, TElemType elem, int LR)
    {
    	BiTNode* pn;
    	if(!bt||(LR!=0&&LR!=1))
    		return -1;
    	if(LR==0)
    	{
    		pn = LeftChild(bt, elem);
    		if(pn!=NULL)
    		{
    			DeleteChild(bt, pn->data, 0);
    			DeleteChild(bt, pn->data, 1);
    			free(pn);
    			if((pn=SearchNode(bt,elem))!=NULL)
    				pn->lchild = NULL;
    		}
    	}else
    	{
    		pn = RightChild(bt, elem);
    		if(pn!=NULL)
    		{
    			DeleteChild(bt, pn->data, 0);
    			DeleteChild(bt, pn->data, 1);
    			free(pn);
    			if((pn=SearchNode(bt,elem))!=NULL)
    				pn->rchild = NULL;
    		}
    	}
    }